Tuesday 3 September 2013

Best Practice for Software Development Version Control

This post is slightly off-topic, but when developing it's important that software development needs to be managed on an ongoing basis. One of the best ways to do this is by using version control.

Version control, briefly explained, is the management of changes to documents, computer source or anything that has large collections of information. Version control systems take snapshots of these collections, and any changes to these can be tracked. In terms of software engineering, revision control takes the form of keeping a track of source code, which is my focus when developing my model.

There are three popular version control systems, git, mercurial and subversion. I'm not going to dwell on comparing these. If you need more information on these, just click on the links. Personally, I use git for my version control purposes. What I want to focus on is managing the snapshots. Taking snapshots regularly will allow us to save every change that has happened, but how do you keep track of these changes once your software system grows. What can be done to save the feeling of despair further on in the software development process when the tracking of changes potentially becomes unmanageable.

Here's a good guideline for version control written by Tom Proston-Werner, who is the co-founder of GitHub. He calls it "Semantic Versioning", which provides a simple, yet efficient set of rules and requirements to state how version numbers are assigned. The full post is here, for further details on these guidelines. Quoting from the post directly:

Given a version number MAJOR.MINOR.PATCH, increment the:
  1. MAJOR version when you make incompatible API changes
  2. MINOR version when you add functionality in a backwards-compatible manner, and
  3. PATCH version when you make backwards-compatible bug fixes. 
These simple set of rules makes is really easy to see when you've added different types of changes to your source code and go back and forth between them, if necessary. This works for collaborations, or individual development in my opinion.

Monday 10 June 2013

Creating your own game (simulation) engine: Choosing your multimedia library

To create my own engine, I need to focus on what my model's needs are. A crowd model as I explained in an earlier post, can be seen as a multi-agent system. A multi-agent system (MAS), according to Wikipedia, is a 'computerised system composed of multiple interacting intelligent agents within an environment'.These agents can be divided into different types, passive agents, active agents or very complex agents with a lot of complex calculations.

In my model, the passive agents themselves do not make decisions, but can be guided by an underlying flow field, whilst active agents are based on Agent Based Models (ABM), and have individual behavioural properties through the environment.

Simulation vs Game

At this point, I feel it's important to point out the similarity between a simulation and a game, and you will see why a game engine can be used for the purposes of both a game and a simulation. Both progress in time, and respond to user input through the keyboard or mouse, creating an interactive experience. A simulation is several states of a model that is updated over time. A model can be defined by various parameters and equations, with the model being at a particular state, at any given time. A simulation, on the other hand, is a model's state that continuously updates over time in discrete steps, through the use of a timer. This creates the simulation, and the illusion of the model changing over time.

I appreciate that this can be a bit of a mouthful, so let's take another view, such as a car racing game. A game can also be seen as several states of a car and it's interaction with the environment, that is updated over time. Again the state of the car is defined by physics equations and various parameters. Now, say you have a car accelerating in that car racing game. If you pause the game, that is the state of the game. Unpause the game, and that state of the game is updated every few milliseconds. Based on the acceleration, the car keeps moving forward, and you see the updated state on the screen in continuous time, creating the illusion of the car speeding in the game. This is similar to the model's state changing over time, you seeing the updated state of the model in continous time, and hence the simulation. One such simulation, is the continuum crowds simulation.

Media Library

Now, to get to grips with creating your own simulation engine, you need a good grasp of C++. If you've never done programming, it'll be a very steep learning curve and I wouldn't personally recommend it as an introduction to programming, but if you're up to the challenge, I would personally recommend two excellent books, 'Accelerated C++: Practical Programming by Example' followed by 'Efficient C++: 55 Specific ways to Improve your programs and designs'. They are excellent in terms of teaching you the foundations of C++ through uses in applications, and I believe that it is one of the best ways to learn. You start by writing robust programs straight away, and that will give you a sense of achievement which will keep you motivated to carry on and learn much of the lower level complex language features such as memory management, in context, which sits better, rather than learning the language features without knowing where it will be applied. Afterall, programming is more about problem solving, than the features of the language for it's own sake.

That was a slight tangent, so bringing us back to the issue of creating our own simulation engine, we first need a library that would provide us with a framework to work around. Something that would provide low level access to the keyboard, mouse, 3D hardware, and finally an application window within which our model can sit. To get an idea what this would look like, the image below shows a game 'Freeciv' sitting inside an application window.

Freeciv screenshot

Having an application window, allows us to provide keyboard and mouse interactivity, and visualise the model (something I will talk about in a future post). Now, if you're using Windows, Mac or Linux, it is always possible to use the native libraries such as the Microsoft Foundation Classes (MFC) in Windows, or use other cross platform media libraries that allow the user to use any Operating System.

Using cross platform media libraries can be considered as a little cheating, so to speak, if you're talking about creating your own engine, but it makes some aspects of the development easier, and there's still a lot of programming to do. It's a "grey" area though. Besides, there have been popular game engines, such as Allegro, actually written using a cross platform media library (SDL), so case in point.

Looking at cross platform media libraries, there are various options, such as SDL, SFML, openFrameworks (which I've talked about in a previous post), and libCinder. The latter two are fairly new libraries, with the focus on creative coding, it's the C++ equivalent of Processing in Java.

SDL on the other hand was first developed in early 1998 by Sam Lantinga. There have been many commercial games written with it, such as Neverwinter Nights, Second Life, and Unreal Tournament 2004 (Linux version), which makes it a good choice, as it's proven it's worth in a stability and online support point of view.

SDL as described, has a thin, cross-platform wrapper that provides the 2D pixel operations, sound, file access, event handling, timing, threading, and more. It can be complemented with OpenGL, which I have done, but I'll talk about that in a future post, along with providing mouse and keyboard input. It also provides several separate official libraries with more functionality, such as
SDL_image (dealing with image files), SDL_ttf  (True Type Font library).

As it's a media library, it abstracts away from the low level interaction between operating system and hardware, here's a figure that shows the abstraction:

SDL Abstraction Layers

I chose SDL as a library due to the popularity and support available online (the current stable version being v1.2, although v2.0 is expected to be out soon). To put it in context, it will provide the main framework for my model, and everything will be built within it.

If you would like to know how to use it, a good set of tutorials are available here. Don't forget the official SDL website.
In a future post, I will detail the next steps.

Sunday 19 May 2013

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.

Saturday 11 May 2013

Future Posts

I've been using this blog on and off over the years. A big reason is the type of content I wanted the blog to focus on. The title of the blog can create an expectation of what you may find. Giving you, the readers, an idea of what I would like the blog to focus on would be a good start.
Over the coming months, I'll try and post once or twice a month on average.

Some of the topics I want to focus on are:
  1. Current State-of-the-Art research in the field
  2. Technical aspects of creating a Crowd model, including programming and Computer Graphics.
  3. Creating your own simulation / game engine to run your model.
  4. Crowd simulation tools that are already available.
  5. Any other topics that I feel are related.