Modelling: Use a Modelling Tool, a 3rd Party Engine, or Create Your Own Game (Simulation) Engine?

So, you've decided to model! In my case, a crowd model. I want to simulate it. What do I do? Create my own engine, or start researching all the engines and tools out in the world, and use one off-the-shelf. Well, there are several factors to consider:

1. What are your requirements?
2. What do the crowd modelling software packages in existence have to offer?
3. What kinds of tools and engines are available?
4. If you do decide to write your own engine, what do you need to know?

Let me try and answer each factor, based on the decisions you need to look at, and how it fits in with your requirements.

User's perspective

First of all, I need to make the distinction between crowd modelling software and the simulation engines. Here, when I say software, I mean crowd modelling software packages, such as Legion, Mass Motion, Massive Insight, STEPS, etc., for one to create pedestrian simulations. The behaviours are defined in a black box, and the algorithms that are used to create the crowd behaviour, and how the pedestrians navigate around the environment are not in the public domain. These software packages are application based, and are for users to create crowd simulations using the developer's own crowd behaviour algorithms. I'm mentioning this as there can be confusion when initially starting crowd modelling, in regards to what these packages actually offer and whether there's any possibility of defining your own behaviours, when compared to using modelling tools and engines. Well, some may very well do, but I'm of the opinion that there is just not enough flexibility, and I like to have choice.

Balance between flexibility and difficulty

Modeller's perspective

Modelling tools

From a modeller's perspective, and for creating one's own crowd model, and defining one's own behaviour for the agents, we need a rather different approach than using crowd simulation software off-the-shelf. Once we've decided we are going to create our own model, there are several different approaches to developing a crowd model. A crowd model can be seen as a complex system, more specifically a multi-agent system. There are tools in existence that provide the individual with a modelling environment for one to define and create behaviours to simulate complex systems like as a crowd. A couple of popular tools are NetLogo, and Repast Simphony. Both these tools are written in Java, and therefore, as Java performs automatic memory management, with garbage collection, the limitation is speed and scalability. If you increase the number of agents in the system, the simulation can considerably slow down. Another limitation is that these tools are generally focussed on a bottom-up design i.e., focussing on the topic of emergence, where micro-level individual behaviour lead to larger group behaviours with macro-properties. Macro level behaviour in and of itself cannot be modelled, as the fundamental modelling paradigms of these tools are micro simulations such as agent based models and cellular automata.

Game Engines

To overcome these limitations of speed, scalability and flexibility in terms of the modelling paradigm, we can take the route of using an existing game engine to create our simulations. Game engines are generally written in C++, as the advantage of using C++ is efficiency. The "zero-overhead principle" is one of the reasons C++ as a language is efficient. Due to the low overhead, and the fact that the programmer has control over managing memory, C++ allows efficient implementations of algorithms and data structures, and makes it useful for creating programs that require a lot of computations. Games need real time input and interaction, and therefore, the fact that game engines are written in C++ starts to bode well.

Now, we come to the question of choosing a game engine, or writing your own. Game engines are mainly intended to make everything regarding developing a game easier. It abstracts away from the low level APIs (Application Programming Interfaces), such as the graphics, audio, input, scene management, collision detection, maths and provide other general utilities that can prove useful. This makes it easy for the modeller / developer to focus on the details of the game, or model in my case. There are plenty of game engines, both commercial and free products, but be aware of the difference between a graphics engine and a game engine. Examples of game engines include Unity, Quake and Unreal, whilst graphics engine examples include Ogre3D and Horde3D.

Writing your own engine

Models can very well be written using a game engine, and people may argue that if you write your own engine, you are reinventing the wheel, but there are advantages of writing your own engine. It provides you flexibility and full control over your engine, and the ability to change any detail with relative ease.

Another important point is that a game engine arises from the needs of a game, in my case the needs of my model. Therefore, when it comes to writing one's own engine, it's important to note that the focus should be on creating the game or model, and the engine should come about by adding features as and when needed. A general purpose engine, on the other hand, can be very heavily bloated.

Another huge advantage of creating your own engine is that you learn a heck of a lot. It offers a lot of learning opportunities, and technical challenges. There are so many features that need to be implemented, and for that, you need a good knowledge of maths, graphics libraries such as OpenGL, C++, physics, etc.,
A very good post about deciding whether to take the route of using an existing engine, or writing your own can be found here.

I've personally taken the approach of creating my own engine, and adding features as and when I need them. Some of the reasons are:

1. I couldn't use the modelling tools in existence, as I wanted to research hybrid modelling techniques, agent based models were not my only focus. I wanted to focus on other macroscopic behaviours of crowds, such as modelling pedestrians using concepts from fluid dynamics and gas.
2. Some game engines provide their own algorithms for path finding for agents, collision detection, local avoidance. My main aim of research is working on these very same algorithms that define and compute the paths for agents.
3. Like I've already mentioned, you get to learn a lot and in a way that can't be taught, including the inner workings of an engine and it's interactions with hardware, in addition to the flexibility you can achieve, that in the long run, make it all worthwhile.

 
The graphical illustration above gives you a visual sense of the balance of flexibility and the difficulty of development when deciding which route you would like to take. Just remember, there are always tradeoffs, and it just depends on your requirements, and how much time you are willing to spend on the engine vs your model.

I'll detail in future posts, steps I have taken to create my own engine, so that it can give you an idea of places one can head to, in order to start. This will include choosing your multimedia library, graphics library, image library, writing your math algorithms, modelling design paradigm considerations, etc., It might seem like a lot of detail, but one step at a time, and it all works out. I didn't start with all these libraries all at once, it was a slow build up, and I'll try detailing the steps, so that you can see what my model requirements were, and how I made the choices I made, it will hopefully not seem as daunting that way. There's also a lot of material on the web to help you along the way.

Netlogo to 3D Max: Code

Based on the pseudocode for the Netlogo to 3DMax implementation, I have now decided to post a short tutorial on exporting the Netlogo traffic simulation to 3DMax. This tutorial will mainly cover the output of the turtles and visualising it in 3DMax.

Netlogo (traffic grid simulation):

For the turtles, I output during runtime, therefore, open the file at the first tick, keep writing, and close the file at the last tick, depending on how many ticks you would want to output, in my case 500.

if ticks = 0 [file-open "myfile.txt"]
ask turtles [
              file-write xcor file-type " " file-show ycor
            ]
if ticks >= 500 [file-close]

This will output in the form:

-12 (turtle: 2) 11
-17 (turtle: 0) 5
-4 (turtle: 1) -8

I didn't find a simple way just to output only the turtle id number, so I manually delete the brackets and text using find and replace, giving me an output as seen below:

-12 2 11
-17 0 5
-4 1 -8

Now our next step is to import it into 3DMax. Once the output file has been stored, the script below can be run, and on clicking the 'Make' button, locate the output file, and it will create the animation.

The code works by importing the Netlogo output file into an array. It can be found here.

I have commented the code in order to explain what is happening at each step.

Running this script will result in the animation shown in my previous post. To get the road patches, and traffic lights in 3DMax, the code can be extended further to store the patches and traffic light states in arrays for each frame, once imported from the Netlogo output.

Update: As pointed out by a reader, there is actually a simple way to output only the turtle id number using the command:

ask turtles [print who]

Therefore, the Netlogo output above can be obtained by using the following command

ask turtles 
[
file-type word xcor " " file-type word who " " file-print ycor
]

Netlogo to 3DMax: Pseudocode

As mentioned in an earlier post that I will be posting a pseudocode for a Netlogo to 3DMax implementation.
This pseudocode is mainly for the Netlogo traffic simulation, but I will try and make it as general as possible in order to use in other models.

Netlogo:
For each tick:
1. Output to file - x coordinate, turtle id, y coordinate

Please note, that when the data is exported into a text file, it will have other test such as 'turtle id:', all text needs to be deleted, and should leave you with 3 numbers. An example for 3 turtles (1 tick) can be seen below:



This creates a file that has the turtle id and locations for each tick. Now, our next step is to import it into 3DMax, but this time each tick represents a frame. I did this by creating a script that would store the data in an array for each frame.


3DMax:
1. Initialise an object (eg, box), for each turtle in the output file
2. Read in netlogo output file, and store xy coordinates for each object per tick in an array. (I stored the array in a 2D form [object id][xy coordinates])
3. Initialise positions of each object for first frame
4. While not end of array
5. Advance frame, and update object position corresponding to the object id in the array
6. Keep repeating step 5 till end of file is reached.
7. Render final animation

Same process for traffic lights, where each traffic light is a turtle in netlogo.

Netlogo to 3D Max: Visualisation

The first few posts will be a catch up of what has been done so far. The first piece I worked on was a Netlogo to 3D Max implementation. This implementation is for a street level scale of a city. Although, 3D Max is used for crowd and particle simulations, in order to model these complex systems, an external package like Netlogo is used. Through the use of loose coupling with 3D Max, it allows us to easily visualise these systems.

The movie below was first posted on the Digital Urban blog. This was my first step to export a basic traffic model from Netlogo to 3D Max. The movements of the cars were first output into a file, the second step was to write a 3DS script to import these movements and animate them in 3D Max.

NetLogo to 3D Max - Proof of Concept from digitalurban on Vimeo.


I have noticed quite a few comments asking how this import was done. I will be posting a pseudocode soon, and will try and give a summary for each step.