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.

8 comments:

  1. Hello Mr Patel,
    May I just say excellent blog. I had a question which I was hoping you could shed some light on.

    I was hoping to begin development of a simple simulation game. A cross between cataclysm dda and europa universalis 3. Where the premise is a simulation of a small isolated community is influenced by the decision of the player.

    The problem is I have no idea where to even begin. I am happy to spent the time learning programs. I just dont know which programs are suitable for what I would like it to do.

    I would appreciate any advice.

    many thanks
    M

    ReplyDelete
  2. Hi Matthew,

    I've just seen this, as a notification didn't pop up of your comment (something I'll need to look into) but I'm glad you like my blog.

    Regarding developing a simple simulation game, I'm not sure what your knowledge level is in terms of programming.

    If you don't know C++, I'd recommend getting upto speed with it before venturing into game development. If you're confident with that, you can start by using game engines to get a feel for how games are made. They will provide the core functions for you to get started building a game. I've mentioned a few in my previous post i.e., Unity (this is based on C#), Quake, Unreal, as well as Irrlicht.

    I've personally used Irrlicht, and found it a pretty good start. I would recommend you give some or all of them a try. They all have tutorials which should give you a good feel, you can start with the one you then feel comfortable with. All of these engines should do the job for you.

    After that, it depends on how deep you want to get into writing your own core functions at a later stage. This would involve getting into exactly what I've discussed in this post.

    Hope that still helps, albeit a month later. Any more question, don't hesitate to ask. I'll try sorting out notifications for the comments.

    Ateen

    ReplyDelete
  3. Good day Mr Patel,
    We're a group of four Computer Science students creating proposals for our thesis. One of our proposals center around creating a crowd simulator for one of our university buildings for emergency management. While we got a lot of information about existing crowd simulators from around the Web, including your most informative blog, one thing worries us the most about this proposal.


    Our inquiry would be, from your experience, how difficult is it to create a crowd simulator from the ground up? We're planning to use C# as our programming language as have a good grasp of the basics of programming in C#. Our chairperson expressly forbids us from using APIs in our proposed crowd simulator. We also have around 5-6 months to develop it.

    ReplyDelete
  4. Hi Joseph,

    In my case, it involved a lot of work, as I wanted to achieve the simulation in both 2D and 3D in addition to running two different types of crowd simulation models, along with other features, so I had to think about my system design carefully.

    However, in your case, you mention that you want to create a crowd simulator for emergency management for one building, the requirements are therefore, limited. I assume the crowd model itself will be an agent-based model, so as you are a group of four, I would reckon that it is possible to achieve your goals of creating a crowd simulator from the ground up.

    Sticking to 2D will make it easier within the time frame you have. If you need to make it in 3D, also consider a 2.5D approach, so that when agents are on stairs, you reduce the velocity, given the average speed of pedestrians on stairs. You can find this by searching for Fruin's level of service for pedestrian flow.

    Here are a few pointers for designing your system, in terms of what you may require:
    1. An Euler or Runge-Kutta integrator to update your simulation
    2. An agent based model that interacts with the obstacles. Typically, store the obstacles as lines by storing x,y positions for the start and end.
    3. A method to initialise agents throughout the building area.
    4. A technique to import the university building, i.e. to convert the walls, stairs and so on, into obstacles and entry / exit points. (Doesn't necessarily have to be extracted within your application, you could do it externally, and store the walls as lines, and then import it as a CSV file, for example.)
    5. A database or even a simple data structure to store the positions of agents at each time step, so that you can output the data to analyse it, such as the density at any given point in time, or over time (if that forms part of your project aims).

    Hope this helps. Feel free to ask, if you have any more questions.

    ReplyDelete
    Replies
    1. Hello again Mr. Patel,

      I would like to report that our thesis evolved from creating a crowd simulation for one of our university buildings to creating an application that uses Helbing and Molnar's Social Force Model to detect anomalous pedestrian movement on residential CCTV camera systems. The first half of our thesis was approved by our defense panel with minor revisions. The next part of our thesis involves developing the software itself. We have already determined that the Histogram of Oriented Gradients is the best way of detecting humans in a CCTV video feed.

      One of the hurdles we're facing right now is turning the Social Force Model equation into program code. We interpret the equation is essentially similar to the force vector problems that we have solved in our General Physics and Math subjects. Are we correct in this assessment?

      Delete
    2. Hi Joseph,

      Yes, that's correct. It is indeed similar to the force vector problems that you have encountered in Physics and Maths.

      I do not quite understand how you intend on using the Social Force Model to detect anomalous pedestrian movement once you retrieve the Histogram of Oriented Gradients, unless you are using it to compare and contrast the trajectories of pedestrians, once you detect something in the video to be a pedestrian.

      However, in terms of simulation, you would use the equations with an integrator to update the positions and velocities at every time step, where information on this link (http://gafferongames.com/game-physics/integration-basics/) can be used as a basis. Hope that helps.

      Delete
    3. Hi again Mr. Patel!

      On this point:
      "compare and contrast the trajectories of pedestrians, once you detect something in the video to be a pedestrian." - Patel, 2016

      That is correct. We intend to use the Social Force model as a set of rules to track the trajectories of pedestrians detected by private residential CCTV systems. The system sends out an alert if a tracked pedestrian starts getting close to a virtual line or enters an area designated by the user. It sends out a different kind of alert if the tracked pedestrian enters a virtual area or crosses a virtual line designated by the user. Another kind of alert is also issued if the tracked pedestrian stays in a camera's FOV for extended periods.

      Essentially, we're trying to create a way the CCTV to warn the user that there's a pedestrian seen by their system. Most of the time, private residential CCTV don't have dedicated operators manning them.

      We also noted that even though the pedestrians the video camera see move in 3D space, the trackers move in 2D space on the screen.

      Delete
  5. Hello Mr. Patel,

    Within the next couple of months I intend to create a general purpose crowd simulation engine (similar to the one present in Recast's Demo: https://github.com/recastnavigation/recastnavigation)

    I found this post very interesting and was wondering if you could follow up with the detailed tutorial you mentioned. It would be very much appreciated.

    ReplyDelete

ShareThis