Thursday, 9 July 2015

Geospatial Data Abstraction Library: Building GDAL from source, and using it within MS Visual Studio

The GeoData Abstraction Library is a very popular library for converting and processing raster and vector data. It is used by popular GIS software such as the open source QGis, and can be used in proprietary software such as Esri's ArcGis. It can also be used within your own application to import and work with vector and raster data in different formats.

GDAL supports over 200 raster and vector formats, as well as provides tools and utilities for processing the data being imported, by reading / writing, transforming, converting, and so on. This makes it a very powerful and flexible tool for manipulating such data in one's application. One such example, specific to a crowd simulation software, is the ability to import geo-referenced real-world maps as raster (eg, geotiff files) and vectors (eg, shape files) in order to map the crowd based on real-world urban maps in the application. In the case of a grid based crowd model, the cell values in the raster data can be used to define the walkable areas for the agents. On the other hand, vector data can be used to provide the location of walls for an Agent Based Model.

That is an aside, coming back to GDAL, it is a library that can be used from a stand-alone command-line terminal, or it can be incorporated into one's own software for handling and manipulating georeferenced data by the software itself. In order to use GDAL into one's own software application, it's web page provides many tutorials on importing GDAL, however, the tutorials and files are split into several different parts, and it can be difficult to get to grips with obtaining the correct compiled libraries for use within your application. Alternatively, we can also build the library directly from the source files. For those who want to obtain the correct files and use it in your application, I thought it may come in handy to use obtain and use it using an example, so here are the steps for building GDAL as well as obtaining the compiled source files directly, and including the correct header and library files in an application.

Option 1: Building the files from source - latest version 2.0.0

This option requires you to build the files yourself, but thankfully it's a fairly easy process. You can download the latest source files as a zip file from the GDAL website by going to the 'Building GDAL from Source' link, and clicking on 'Download from source', alternatively, by clicking here. I downloaded version 2.0.0's zip file. Now in order to build from source, we follow the steps below:

  1. Extract the downloaded source zip files to a convenient location, as a working example, I'll use 'C:\gdal200'.
  2. Open your Visual Studio Developer command prompt. For Visual 2013, it's called 'Developer Command Prompt for VS2013', and will be of a similar name for previous versions of VS Studio.
  3. Type 'vcvars32.bat' and press Enter, in order to set up the appropriate environment variables. Note: for 64-bit builds, the instructions are slightly different. Refer the 'Building from Source' section here.
  4.  Change the directory to the GDAL folder, eg by typing 'cd C:\gdal200\gdal-2.0.0' and enter. You can copy the folder location by opening it in Windows Explorer and copying the text in the location bar if you don't want to type it all.
  5. To set the location of the resulting library and header files, you can optionally edit 'nmake.opt' in the gdal folder, and set 'GDAL_HOME' to an appropriate location, eg 'C:\gdal200\gdal-2.0.0\bld', or leave it as default at "C:\warmerda\bld"
  6. Type 'nmake /f' and press Enter. Wait around 5 to 10 mins for it to finish building. 
  7. Type 'nmake /f devinstall' and press Enter. Wait for it to finish.
We are all done, we've built from source and have obtained the lib and dll files for GDAL i.e . 'gdal_i.lib' and 'gdal200.dll' in the 'C:\gdal200\gdal-2.0.0' folder. Note: The dll version name willl defer depending on the version you are compiling.

The include and lib folders will be in the GDAL_HOME location, eg in 'C:gdal200\gdal-2.0.0\bld'.

Now, we have our library and header files, we can skip to the section on using GDAL in Visual Studio.

Option 2: Obtaining the compiled header and library files - version 1.11.1

Alternatively, GISInternals maintain compiled header and library files for use in your application. We can download compiled header and library files from the GISInternals website. We need to be aware of two things:

  1. Deciding what type of build we want, i.e. development, stable or release. These are basically different branches in the repository. In my opinion, it would be best to choose the release version, as it is the most stable of the three branches and can be used in production code. Heading to the 'Stable Releases' link, we find several more options, as I'm building a 32 bit version, I head to the 'release-1800-gdal-1-11-1-mapserver-6-4-1' in order to download the appropriate files. Here, we download the 'Compiled binaries in a single .zip package' ( and 'Compiled libraries and headers' ( in order to include GDAL in Visual Studio.
  2. In terms of selecting the appropriate Visual Studio Version that you are using, it also depends on  the type of application you are building i.e a 32-bit or 64-bit one (this doesn't depend on the bit version of your Visual Studio IDE). 
Now that we have downloaded the binaries, libraries and headers:
  1. Extract the compiled binary files to an appropriate location, as a working example, I'll use 'C:\release-1800-gdal-1-11-1-mapserver-6-4-1'
  2. Extract the compiled library files to the root folder of the binary files, i.e. the folder above.

Now, we have the 'gdal_i.lib' in ''C:\release-1800-gdal-1-11-1-mapserver-6-4-1\lib' folder, and 'gdal111.dll' in ''C:\release-1800-gdal-1-11-1-mapserver-6-4-1\bin' folder

First of all, lets look at the final folder structure for the above two options, they're quite different

               Option 1: The library built from source - version 2.0.0.

Folder structure for gdal built from source

Option 2: The library downloaded from GISInternals - version 1.11.1

Folder structure for gdal obtained from GISInternals

Using the GDAL library within Visual Studio

For completeness, to use the GDAL library within Visual Studio, we need to follow these steps:

1. Include GDAL's 'include' and 'lib' directories that we extracted above in the Project - Properties - VC++ Directories, i.e. Add GDAL's 'include' folder, in the 'Include Directories' path, and the 'libs' folder in the 'Library Directories' path.

Option 1: The library built from source - version 2.0.0.

Include and Library paths for gdal built from source

Option 2: The library downloaded from GISInternals - version 1.11.1

Include and Library paths for gdal obtained form GISInternals

2. Go to Project - Properties - Linker - Input - Additional Dependencies. Add the full path of the 'gdal_i.lib' file here, eg: 'C:\release-1800-dev\gdal\gdal_i.lib'

Option 1: The library built from source - version 2.0.0.

Adding gdal_i.lib file in the linker

Option 2: The library downloaded from GISInternals - version 1.11.1

Adding gdal_i.lib file in the linker

3. Copy the 'gdal200.dll' or 'gdal111.dll' file (depending on the version obtained) to the root of your Visual Studio solution folder, where the 'dll's' of other libraries are normally copied to.

You should now be up and running with GDAL in your application, and be free to start with the GDAL API tutorials within your application, as found here.

Thursday, 4 June 2015

Walking on Wembley Way - The FA Cup Final Arsenal vs. Aston Villa 2015 Gathering

Wembley Stadium. It has a proud history, some may say. It sure is an occasion, to go to Wembley for any event, but of all events, the FA cup final is probably the biggest event on the Wembley Stadium Calendar.

As fans travel to the Stadium from all across the country, the majority arrive at Wembley Park Station, making their way along Wembley Way, as it's traditionally called by fans. The official name being 'Olympic Way' of course, as if you didn't know. I'll be using 'Wembley Way' and 'Olympic Way' interchangeably in this post.

Note: As this is a fairly long post, you may want to check out the videos first before going ahead, they're interesting.


Lets start with a little background, about this little 600m (approx.) stretch of land from Wembley Park Station towards Wembley Stadium. Fans would know it as a pedestrianised easy access route towards the stadium. It never used to be that way. The Wembley Stadium area started to be formalised during the Empire Exhibitions of 1924, later being redeveloped for the 1948 Olympics. In fact, the famed route towards the stadium comes from the labour of German prisoners of war during this time, shocking, I know. It was re-built in 1948 during redevelopment work around the stadium to host the 1948 Olympics, hence the name 'Olympic Way'. The Wembley area, hasn't remained static, and over the years, it has evolved fairly consistently. It has been through several phases of development, and has also been fully pedestrianised, where at one time traffic used to be allowed. Today, the experience that unravels when walking along Olympic way towards the view that is presented of the centrepiece Stadium and it's iconic arch, is what makes the experience unique to Wembley, and one of the many reasons why this Stadium has become as recognisable a destination as it is.

The Arch of Wembley Stadium (Source)

The FA Cup Final

The FA Cup Final, that's what we are here for. It's Arsenal vs. Aston Villa, the culmination of months of tournaments, the build up, the excitement, the emotions are all here to be displayed, with a few fans being asked to tone down by the police, and as the crowds arrive, just standing there, you can't help but be drawn into the build up. Fans, both of Arsenal, and Aston Villa, chanting, the Wembley chants. Oh my, it's exhilerating. Sadly, I'm not going to be in the Stadium, I'll be watching the crowds arrive, afterall, this is a blog about crowds, but it's hard for the excitement not to rub off on you.

Crowds Arriving

It's 3pm, as I arrive along Bridge road, as the name implies, is a bridge that stands over the station edge of Olympic Way, and gives a direct view of Olympic Way, with the Stadium in the distance. You can use the embedded google map above to zoom in, and see it from a satellite view. The fans are already arriving for the 5.30pm kick-off, and a constant stream of people arrive until kick-off time, with a few late ones running along the way. It's time for me to take some videos and photos of the crowds, as we shall see, it would be great to observe the behaviour as crowds arrive, the pedestrian traffic management employed by the police, as well as any other nuances that can be extracted from the crowd flow. We'll also observe the crowds leaving later on, don't worry.

Crowds Arriving along Olympic Way (View from Bridge Road)

As the trains arrive at the station, there's a surge of people arriving, walking down the stairs of the station, and along Olympic Way, it gets really busy, I mean really really busy. Here's a video below of what it looks like around 3.30pm to 4.05pm, that has been hyperlapsed.

Hyperlapse is a technique that takes into account both temporal and spatial features, so in a sense, it's a time-lapse with video stabilisation. I'm using Hyperlapse software by Microsoft Research, that approximates the user-specified video speed-up, and provides a smoothly moving camera. Useful, when you're recording by hand. As an aside, if you're interested in the background of how they're created, Microsoft are presenting a paper at SIGGRAPH 2015, as well as one they presented in 2014. In my case here, it really helps with the camera shakes as the videos were taken by hand.

Anyways, coming back to the actual video, the nice thing about the hyperlapse, is that it has the unintended consequence of slightly slowing down the video when there are abrupt changes in the crowd flow, such as bi-directional lanes forming, or changes in flow. There are several crowd phenomena that can be observed, especially as this is a fairly unique set of circumstances coming together, such as the culmination of an event, a direct route, a singular flow i.e. almost a procession along a very wide pavement, along with a very large number of people, given that Wembley Stadium has a 90,000 seating capacity. It makes it easier, to extract phenomena and behaviours in the crowd at individual stages. We will see how our individual decision making behaviours emerge, blending and transition into something bigger, than any one individual.

Emergent Behaviour

First of all, due to the unique set of circumstances, almost everyone in the crowd has similar sets of desires i.e. to start at Wembley Park Station, walk along Wembley Way, and enter the Stadium. 

Due to the common set of desires, individuals tend to give up their decision making power, and lose their will to the will of the crowd, or as described by social psychologists, de-individuation, where one becomes part of the crowd, this is the nicer version, of the term mob mentality. There are several sub-processes that take place in the process of de-individuation and becoming part of the collective, that is, the crowd. Although, I've briefly explained some of the emergent behaviours in a previous post, I'm going to go into a bit more detail here, and also discuss it in the context of the crowds on Olympic Way.

 Herding (Following)

As people arrive around 3pm, the crowd is fairly sparse, as shown in the beginning of the video, individuals have a much better view of the surroundings, they have an idea of their goal, and are able to take their own decisions of where to go. However, as time goes by and the density of the crowd starts to increase, it becomes difficult to be fully aware visually of what lies ahead of you, this is the first stage, and the clearest stage where one can actually observe how the behaviours transition from the individual to the crowd. As I mentioned earlier, a unique set of circumstances have come together, the fans in the crowd have a common goal, and as the density increases, the individuals will transfer control of their actions and behaviour over to others in the crowd, specifically to the person in front of them, if their destination lies in front of them, and in a similar direction. Aha, you say, yes, this event works really well for that, as the goal is Wembley Stadium, and it's a common goal in the same direction, although the eventual goal, is the goal of the football (bad joke!). Moving on, the passing and transfer of the decision-making to others and following their lead is termed as social contagion (see also here and here for more info). As you can see, each person in the crowd similarly starts to follow the individual in front of them that is travelling in a similar direction, leading to conformity. This conformity is termed as herding behaviour, which starts to emerge. In essence, we become a herd. Here, you're not making your own decisions anymore, and there's a bigger power that no one person is in control of, making these decisions for you. I know, we all like to be in control, but sadly, as much as we like to believe, we're in fact, not.

The Zipper-effect

We're done with herding, now what? Well, it's time to zip your jacket, no I'm not joking. What happens now is that, as the crowds arrive, the density increases, the herding behaviour is still in tow, where each person (or group of people) in the crowd, are following individuals in front of them. This herding behaviour leads to multiple layers of pedestrian flow forming, travelling in the same direction, and starting to cover the width of Olympic Way, as you see further into the video. These layers are compacted like a zip. Let me try and explain, the typical width of each layer, it has been noted, is approximately 45cm. However, the approximate width of a person is 55cm. What happens here is that, as each individual is fed through in a densely packed crowd, for example, if I were walking through the crowd, typically I wouldn't walk exactly behind the person in front, but in the middle of two people in front of me (presumably in order to see ahead, and fill the gap between the two people), the people behind me are doing the same, creating an almost zig-zag pattern, just like the layers of a zip, with me being one of the zipper teeth. Hence the term, the zipper-effect.

Lane Formation

Through the zipper-effect and herding, we lose control of our decision making, and put a lot of trust in the individuals in front of us in order to guide us, as the people in the video do. These zipped layers, lead to lanes forming that we wouldn't be fully aware of, whilst walking through the crowd. These lanes are not constant, but break and merge to adapt to the environment the crowd sees itself in. It may not seem completely obvious from the hyperlapsed videos, so I've also motion blurred time-lapse photos in the video below. You see how, there are several multiple layers of flows during the arrival of people walking along Wembley Way as they walk towards the stadium. The multiple layers are also known as stripe formation.

You can actually see the breaking and merging of these lanes in the motion-blurred video. During the 1 hour period, some fans stop to take pictures, as it's a good place to frame a shot with the Stadium in the back-drop. When these fans stop, within the motion-blurred video, they start to stand out. In the context of the crowd flow, they take the place of temporary obstacles. Now, in order to avoid the obstacles, some of the flow lanes break and merge, in order to navigate around the fans that play the role of temporary obstacles.

These standing people also have a secondary purpose, they actually funnel the crowd flow, although not necessary for the flow in this case, it actually helps to ease the pressure in the flow if it is building up, as it breaks up the flow. We'll see how this phenomena is used for a much more practical purpose, when the crowd are leaving.

Other Observations - Crowd Flow Control

In addition to the hand-held video shown earlier, I was able to use a DSLR on the railings (sadly my tripod turned out to be too short for the railings). Anyways, managing to take photographs over 1 hour at 2 second intervals, until kick-off time, the pictures have been cropped to focus on the police line, and have been stitched together in order to create a time-lapse video. However, the intervals didn't seem short enough, so it was necessary to motion-blur them, again to bring out features that wouldn't be too obvious otherwise. The video is still not very clear, as the upload caused a loss in quality, but hopefully it will work for now.

Police Spine Ramp Funnelling

The cropping has allowed the video to be zoomed in to observe the role of the police, as the crowd approaches the stadium, and the motion blurring help in extracting the changes in the flow. The line of police standing in the middle, serves an important purpose. As we all approach the stadium, it becomes exciting, or as some fans put it, the atmosphere is electric, the sign boards just above the police line display the direction to head towards based on the type of tickets purchased (as shown in the image below), in order to get to their respective seats. If there was no police line, the lane formation I described, will start to form, break and merge constantly, typically along the middle length-wise, as each of us try to go towards the ramp in the direction the sign boards direct us. This breaking and merging would increase the interaction between individuals as we tend to collide whilst trying to change directions, and in turn, the collisions start to slow the crowd.

The signs showing 'Aston Villa Collections' direction along the right ramp

The police line doesn't necessarily stop the crowd flow lanes from changing direction. However, the police line serves as a form of resistance to changes in the flow, and hence funnelling the crowd flow on each side of the line towards the ramps on their respective sides.

Why is the presence of the police line successful in creating a resistance, despite the gaps present for individuals to pass? Well, it's a cost / effort ratio. There are two conflicting sets of desires. We can see it from the individual point of view, as well as the flow point of view. As an individual in the crowd, say if I'm on the left side, I see the sign directs me to go towards the ramp on the opposite side (just as the Aston Villa sign in the image above does). I see the police line, and I see the direction of the crowd flow going in parallel to the police line. Is it worth trying to work my way through the crowd in order to get to the ramp on the other side in addition to getting through the additional narrow gaps created by the police line, against the momentum of the crowd flow that is leading me to the ramp on the left which will eventually get me to my seat anyway, probably not? Unless, I'm really determined, but what is the point?

From the crowd flow point of view, most individuals allowing the momentum of the crowd flow to direct them leads to parallel flow lanes appearing. In addition, the police line breaks the flow along it's width into two at the middle, leading to the flows on either side funnelling to the ramps on their respective sides. One point to notice though, is that the flow lanes near the police line have a smaller resistance due to the gaps in between the policeman. As those lanes don't need to fight against the other flow lanes, and where the gap between two individual policemen is greater (specifically in between two poles, the gap present between the last policeman and the pole), the effort required to change sides is much less than at any other point. The consequence is that you tend to see the flow lanes changing in these areas of broader gaps, which is not a big deal, where the important job of funnelling the crowd towards the two ramps, evenly distributing the crowd flow has been achieved.

Natural Crowd Surge Control

This is an interesting one. The crowd pressure is actually controlled, quite naturally. There are regular surges in the crowd flow at certain intervals coming from the station and going towards the stadium. Yes, you guessed it, controlled by the train timetable. As the trains arrive, the crowd flow surges, before dying down. These regular stop-gaps in the arrival helps in distributing and dispersing the crowd as they arrive, and it can be safely assumed that there won't be any unusual spikes in the crowd flow. This is really helpful in ensuring that pressure doesn't build up in the flow, helping to prevent any tragic events that have occurred in other situations, where other phenomena, such as Stop / Go Waves, and Turbulence can occur as pressure builds up (see here for more info). We'll see a similar stop-gap situation as crowds leave, but one that is artificially created.

During the FA Cup

Now that we've assessed and observed the crowds arriving, it was time to go to a bar in the Stadium retail area where I asked a friend to meet me, enjoy a beer, and watch the match from there. It was great even if it was just watching it from a bar, as you can actually hear the crowds roaring as goals are scored, well, mainly the Arsenal fans, as we know what happened. Well, during this one-sided match, as the last 10 mins approached with the score at 3-0 to Arsenal, it was time to leave, as I sensed that the Aston Villa fans would be leaving. As I was briskly walking along Olympic Way, becoming part of the crowd, following those in front of me and forming lanes (that I couldn't see), I heard another roar from the Stadium, as Arsenal put the final nail in the coffin with a 4-0 lead, and on their way to becoming the FA Cup Champions. If you want to watch the trials and tribulations of some fans, you can watch a BBC program 'Truly, Madly, Wembley' available on the iPlayer for another 6 days (UK viewers only, I'm afraid).

Crowds Departing

This time, as I approached Bridge Road, the stairs leading to Bridge Road were blocked off by the Police, so I had to go under it, and over to the other side, and get onto the road from the Wembley Park station area. The Police were standing on Bridge Road, so wouldn't allow me to take photos from the railings. Having to stand back and take the videos without any support, you can see the camera shaking as I get pretty tired towards the end. It's a video taken over approx. 90 mins. The hyperlapse video below has around a 20 min segment cut off from the middle, as it didn't show anything different to what can be seen.

Observations - Crowd Flow Control

Arsenal winning the match

In the video, as can be predicted, you see the Aston Villa fans leaving first. Until Arsenal lifts the FA cup within the stadium, the majority of fans leaving are Aston Villa supporters, followed by a few spots of yellow and red with Arsenal fans starting to leave, with the majority at the end being Arsenal fans. In a sense, the events of the match has implicitly controlled the departure of the crowd towards the station. 

It's only a limited control, but helps, however, the departure of fans is pretty constant, and as the match finishes, the departure rate of the crowd can cause pressure to build up as they head towards the station, with the rate of departure of the trains being slower than the rate at which the fans leave the stadium. There is no other natural stop-gap departure rate that we had during the arrivals, such as the one provided by the train timetables.

Stop / Go Simulation 

Crowd management staff are therefore employed to control the crowd flow towards the station. They serve the purpose to control the crowd by employing Stop / Go signs. As Wembley Park station gets congested, the staff switch the 'Go' signs to 'Please Wait'. Hence simulating a stop-gap departure rate that provided natural crowd surge control, provided by the train timetable during arrivals earlier in the day.


There's a consequence of the crowd management staff regulating the crowd flow. They start providing a secondary purpose - funnelling the crowd flow. This funnelling actually helps in decreasing pressure in the flow, when the density is high, and could potentially help in an evacuation scenario. As it has been known to show that narrow obstacles can actually improve the flow at an exit by preventing pressure building up in a flow. I may be wrong, as it's not exactly an exit. The video above doesn't show the funnelling quite as well as another source I found from a reddit thread that I attach.

The video sourced from the redditt thread, shows a time lapse loop, with police horses in control of the crowd management, on different event.

Staircase blocking 

Crowds tend to flow towards their destination, and try to find the path that requires the least amount of effort. Especially in our case here, everyone wants to go home, the match is over, and they want to get back home as quickly as possible. As pressure builds up along Olympic Way, the crowd flow will try to find other openings or gaps that would allow it to reach it's destination i.e Wembley Park Station. These gaps are the staircase that leads onto Bridge Road, and across towards Wembley Park Station. You can see the staircases on the right and further down on the left in the video (a google street view looking towards the station from Olympic Way with Bridge Road overhead has also been attached below). This has the potential to cause chaos on the road, as vehicular traffic tries to pass at the same time, causing traffic jams. Therefore, the police block these staircases, and form a path of resistance that doesn't allow the crowd onto the stairs, unless, some people get a bit unruly of course, then that resistance can break down. The crowd here were pretty well behaved.

Over the 90 mins, these four processes help a generally smooth exit for all the fans towards the Station and on their way home without any chaotic effects. The only downside is that they have to wait. Afterall, the Stadium has a 90,000 seating capacity, out of that say 80,000 were occupied, and another 20,000 to 30,000 went home by other means, that still leaves around 50,000 to 60,000 fans taking Olympic Way towards Wembley Park Station. Based on the capacity and safety measures taken, it's reasonable to wait 20 to 30 mins in order to get home safely.

The last trickle of fans leaving Wembley

The Analogy with Fluids

I've talked a lot about the crowds in terms of density, pressure and flow. It almost sounds like a fluid flow. Do crowds behave as fluids? Well, to a certain extent they do, however, humans are sentient beings, able to perceive and feel things. I talked about the properties of emergent behaviours, and how individuals transition from taking their own individual decisions to then passing on control to the flow of the crowd. The individual in the crowd is guided by many different desires and factors as well as the emotions that are brought out whilst in the crowd flow. They pass control, and they take back control depending on the situation that presents itself. We see how fans stopping to take pictures with Wembley Stadium in the back-drop in order to create memories that will last a lifetime. This ability to take our own decisions is where the analogy with fluids breaks down, where we stop being particles, and become human. We can try to look at a crowd flow as dispassionately as possible, however, there is still a human element to it, and we need to be aware of that. Every individual has a different history that guides them to do what they do, conflicting between wanting to be in control, standing out from the crowd, and being part of the collective. This is what makes predicting crowd movement such a difficult problem, and so difficult to simulate. However, simulation is a simplification of reality, and if we try to draw an analogy with fluids being aware of the limitations, we can use it to a certain extent in addition to other techniques to predict the flow and movement of crowds.

Self-organising Behaviour

There's another phenomena I want to discuss. Looking at crowds with a naiive eye makes it look rather chaotic, or we can replace it with the word 'complex'. I've talked about emergent behaviours within a crowd, where the individual behaviours lead to a collective crowd flow. This transition between the individual person to a collective flow pattern, transitioning from herding to zipping to lane formation and back to the individual, with lanes forming and merging, and the crowd trying to fill gaps in its route with the minimum effort sounds like a 'system' doesn't it, where if you think about it, the flow is fairly well organised, without having to control it much. Just ensuring it's guided in the right way as the police and crowd management staff do, the crowd flow will form naturally without much effort, self organising itself for the situation that is presented. This leads us to observe that complex individual behaviours driven by the human mind leads to a system that self organises itself given the environmental / urban sitation at hand. Something that we can now call, 'a complex system'. Isn't that interesting?

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.