Wednesday, 31 December 2014

Leaving the London Eye New Years Eve Celebrations area in double-time

Everyone is getting ready for New Years celebrations, I for one go to see the London Eye Fireworks almost every year. However, as the Mayor has decided to charge £10 to see the fireworks and the requirement of buying it in advance has put me off this year. No doubt I will still be watching it, albeit from a distance. However, if you're one of those lucky ones that have managed to purchase a ticket, and are looking forward to the fireworks, trust me, it's quite a view, and if you go in early enough, you'll get a good spot, when I say early, it's about 8pm. Especially the embankment area, it gets cordoned off after that (well, used to until they started charging), so the number of people is just about right.

The atmosphere is great with everyone in a celebratory mood, London turns into this extremely friendly place, where one feels part of this huge family that has come together to celebrate bringing in the New Year. You get to meet all sorts of people from around the World. When the countdown begins, there's a massive display on the Shell Tower block counting down the seconds until Big Ben strikes midnight, the lights around the London Eye start flashing, and off with a bang go the fireworks timed with music blurring through the speakers along the embankment. The pictures show last year's theme.

Sweet Flavoured theme in 2014
London Eye Fireworks 2014
However, once the fireworks and celebrations are over, you need to head back home or to another party, this is when it becomes a little difficult. The crowd, oh my, the crowd, if you've had a good spot on the embankment, it can take an hour or more to get to the exit at Trafalgar Square along Whitehall due to the number of people trying to get to the stations and back to wherever they want to go. The police generally use a pedestrian traffic management system allowing a certain number of people along Whitehall at a time with a number of break spots. There is also a final barrier at the end of WhiteHall into Trafalgar Square, where people can only exit from the middle of the barrier. The typical route one would take through the crowd to exit from a spot on the embankment is shown in the top map illustration. What happens here though is that you want to get out the quickest way possible, and instinct dictates that you take the shortest route through the crowd, which is through the middle of the crowd flow, where everyone is walking through and you follow the person in front, due to the herding effect, as I explained in my previous post. This is shown in the first picture. However, we don't want to use instincts here, we want to use a better approach to getting through and exiting as quickly as possible. How do we do that?

Typical exit route from the embankment
Exit route skirting the crowd flow (map via Open Street Maps)
We go against our instinct of getting through the dense crowd in the quickest possible way, that is, walking through the middle. Now that most people will be walking through the middle, what we want to do is look at the crowd flow, as long as it's a homogeneous flow, the density of the crowd is the greatest at the middle, so we want to avoid that area, and walk in the areas of least density that is moving in the direction of our exit. The area of least density in our case is the edge of the crowd flow, so as long you skirt the edge of the crowd flow, you will get through to the exit in the quickest possible way. It's only a small change from your typical way of walking in a crowd, just stick to it, and don't let your instincts take over, especially at the end point when you see the barriers, walk around it as shown in the figure. From personal experience, I got through the crowd with my friends to the exit in a little less than half an hour last year. Although I'm aware of this solution as part of my research, I still couldn't help my instincts telling me to go through the middle as well, especially when we were so close to the exit barriers, so it's an innate human trait I suppose, but I had to fight it off. There you go, a simple and effective way that not only works on New Years Day, but in other situations of dense crowds flowing in a homogeneous manner.

Now, hope you all have a really great New Year Celebrations, and hope the New Year is filled with joy and happiness.

Saturday, 27 December 2014

Getting through Boxing Day Shopping: A form of self organisation

Boxing Day is a great day to go shopping, you can grab yourself bargains that you could not grab throughout the year, navigating your way through the thousands of bargain shoppers. A few years ago, I decided to brave Boxing Day shopping and became one of those bargain shoppers on a mission, on the most crowded shopping street in Europe, Oxford Street is what I'm talking about. The street that all Londoners try to avoid until hell freezes over, well, not quite, but you know what I mean, if you want to avoid crowds even on a normal day, you avoid Oxford Street.

Boxing Day 2011, Oxford Street
Boxing Day is a whole other occasion. It's an interesting place on Boxing Day, especially if you go in with a determined focus, you can get out of it unscathed by the evening, with bags full of things that you don't really need, but you just end up buying (I'll let other experts explain that behaviour: here and here).

If you just take a step back, and look around at what is happening, people start flocking to shops to spot bargains. In order to get to these shops, they navigate the thousands and thousands of people on the street. You have a shop (or many shops) in mind, and you want to get to each shop as quickly as possible so that you don't miss out on those bargains of the year. In order to get to the next shop in the quickest possible way in a crowd, you start mimicking behavour, humans are indeed great social creatures that navigate the social world through mimicry. We like to copy others, in order to be socially accepted, and at the same time, we like forming our own unique identity, and we work by balancing these conflicting interests.

In this context, we find ourselves mimicking each other whilst navigating crowds. Due to the sheer number of people in our path, we can't normally see our destination clearly, but we know the direction we want to go. For example, I want to walk to Selfridges  through the Boxing Day crowds to grab that sought after bargain (yes, that's where we all want to go on Boxing Day, considering they had an estimated turnover of £2 million in one hour yesterday). How do I get there?

First of all, I can't see my way due to the amount of people present, so I observe the person walking in front of me going in the direction of Selfridges, and I start following them. What I'm actually doing here is I'm passing my decision making power to the person in front as I can't see the path, and I'm trusting that person to take me in the direction I want as quickly as possible through the crowd. There is a term for this kind of following behaviour, known as herding. This is the first step I take in order to get me to my bargain. The transfer of power itself is known as social contagion.

Now, if I take a step back (not literally), and look around, I start to see every one of us is following a person in front of us in order to help us get through the crowd. The herding behaviour leads to multiple layers of people flow forming travelling in the same direction, especially due to the number of people on the street. We can look at this from  an analogy of car traffic on a motorway. On a motorway junction, before entering the motorway, at the slip road, two roads merge into one. Similar merging happens when I'm walking through the crowd, the merging of people travelling in the same direction. This gives rise to our second phenomenon, known as the zipper effect . It's pretty much like zipping your jacket, where each zipper tooth is layered over the other, similarly you're the zipper tooth, and you start zipping against other pedestrians travelling in the same direction.

There's a lot of trust we put in the person in front to get us to our destination. This trust we put in each other leads to our third phenomenon, the emergence of lanes formed of the 'zipped' multiple layers through the crowd. These lanes can be in both directions, and there may be more than two lanes at the same time. Due to the herding behaviour, these lanes generally become homogeneous, and we are unconsciously giving up a part of our identity to become part of this homogeneous flow. This may or may not seem obvious, but the observance, and dissection of these individual steps that lead to these phenomena help us explain the way crowds behave. How we transfer our own identity to the identity of the crowd, leading to the emergence and disappearance of flows and lanes, gives us an understanding of our own identity within a crowd. There is also a term for these types of flows, not a creative name, but one that makes the meaning clear, it's known as lane formation. These lanes are ever changing, and they adapt to people in the crowd just standing, the existence of bus stops, street lamps, etc. along the street. It's interesting to see how we as people are adaptable, and this adaptability also works really well at a macro-scale, the flow lanes adapting to the environment present to us.

Being a part of these lanes, and flowing amongst it then gets me close to my destination, that is Selfridges. This gives me the flexibility to again take control of my decision making and I walk towards it and enter this multi-million pound department store in order to grab that well sought after bargain. Before I know it though, I've again passed part of my decision making to the marketers that get me to buy items that I don't really need. Again, I leave that to the other experts I've linked to, to explain how that's done.

Boxing Day 2011, Oxford Street (showing the emergence of Lanes)
Why am I talking about this? Well, in addition to the fact that this is a blog on crowd simulation and to understand how crowds form and behave, it was one of those things, where I was walking along Oxford Street on Boxing Day a few years ago, I decided to take a picture of the crowd at the time and post it on one of our current social media platforms. However, observing the photo closer, you start to distinguish the lanes that have formed through the crowds, which I thought was quite interesting to observe in my natural environment outside my normal research realm. As you can see with the photo overlaid with the lanes. Also, the current timing seemed quite fitting, as I decided I didn't want to brave it again this year.

Other than that, hope you've all had a great Christmas, have a better understanding of what you do when you go out shopping on Boxing Day, but most importantly, found yourselves some good bargains that you actually do need.

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.

Friday, 11 May 2012

Social Forces Model with Human participants on the BBC

The BBC's science series 'Bang goes the Theory' recently had an episode on crowd behaviour. It shows a fascinating way of getting plenty of research out there into the public eye, using very short clips of research taking place based on certain themes. Anders Johansson, who still works with CASA, ran an experiment based on the 'social forces' model.

To give a heads up, the social forces model is an agent based model that simulates the microscopic movements of pedestrians. The motion of these pedestrians are described by subjecting them to 'social forces'. These forces are exerted by the pedestrians personal environment, as well as the interactions with other pedestrians in this context.

The movement of these pedestrians governed by these social forces are defined by the equation below:

If you'd like more details on the paper, it can be found here

An example of a social forces simulation model can be seen running in this video below:

Now, with this BBC episode, you can check out this model in a real world example with the help of an experiment with human participants, where you can see the effect of jams during an evacuation in a potential real world situation, and how a very simple solution of placing an obstacle at the exit can actually improve the flow of people through a door when evacuating a building. Although, your intuition I'm sure would say that it would not make sense. Actually, as this obstacle separates the flow of people, it prevents a jam occuring at the door, and therefore, creates a smoother flow through the door. Have a look, it's available for another 10days, and the experiment runs from around the 24 min mark, UK users only I'm afraid:

BBC Bang goes the Theory S6 Ep 4