People movement simulations can be done because of many reasons, and security issues are the most obvious one of them. Those simulators enable a possibility to check yet during the planning process if used architectural solutions will work out during an evacuation or in a case of a panic.
Thanks to those data and visualisations, it’s possible to adapt building in a way in which it will be as most ergonomic as possible. It’s a crucial thing in a case of public facilities such as stadiums or shopping centres.
However in this article I will focus on another subject – how are those simulators created, what algorithms can we use and how to visualise the whole process by using modern graphic engines.
My adventure with simulators began in 2012 when I was a third-year student of the Computer Science Faculty. The application under the name of CrowdSim was my and my three mates idea for Imagine Cup contest, organised by Microsoft. Since then, I became more interested in the subject of simulations and algorithms, and recently, I came back to work on that project to develop it.
In this article, I will focus mostly on visualisation process with the usage of Unity3D. But before that, a short introduction to crowd behaviour modelling methods is essential to understand where our input data for our visualisation came from.
Cellular automata
A cellular automaton is a model which allows for presenting space in the form of a cellular matrix and by using local transition rules which allow for changing a state of fields. The whole simulation is divided into a finite number of temporary steps, and in every of them, a cellular state is being modified on grounds of environment.
Today, the most popular implementation method is that one invented by John Conway, British scientist – that method is called “Game of Life”. The game is being played on infinite, two-dimensional board divided into small cells in the shape of squares.
At the beginning, the user defines the initial state of cells, and after that, the game goes on without his involvement. Every cell can assume one of two available shapes in particular unit of time – “live” or “dead”. A state of given cell depends directly on states of adjacent cells (every cell has eight neighbours).
Singular cells may have a different shape but definitely, the most common one is the shape of a square. “Game of life” is the simplest example of using automata, which are a very flexible solution and they also can be used to describe more complex processes.
Their two main benefits are moderately simple implementation and small computational complexity. It’s also that kind of the algorithm that is quite easy to parallelise under particular conditions.
Multi-agent systems
But cellular automata are not the ideal solution. It turns out that those simple rules, used by this methodology, are simultaneously too limited to model complex human behaviours by using them. Because of that, we can use many mechanisms used in multi-agent systems to recompense that.
In this approach, we are dealing with many agents representing pedestrians as stand-alone objects with an ability to analyse environment and make independent decisions. We can model human behaviours and recreate decision-making process with great realism by using multi-agent systems.
The agent can also have memory, and thanks to it his moves during simulation will be definitely more smooth and reliable. It’s not ideal approach because the object in programme which represents the agent, has to do a lot of computing which affects high computational complexity of the algorithm and it needs a lot of resources in the form of operational memory.
On top of that, in a case of mass people simulation, agents constantly interact with each other and that limits the possibility of computational parallelization by far.
Taking into account all the pros and cons of above-mentioned solutions, we can come to a conclusion that cellular automata and multi-agent systems supplement each other perfectly. Because of that our goal will be to take out the best from these two worlds.
When it comes to automata, the idea of dividing space in the form of a grid of cells, in which every cell has its own state and also a conception of dividing the whole simulation into a finite number of temporary steps.
In the matter of multi-agent systems, it is worth to use the idea of presenting pedestrians as stand-alone objects-agents. Thanks to that, our algorithm will be much more flexible. In this article, I won’t focus on the details how to implement the algorithm because it would take too much space. I just want to describe what conceptions have been used to build it.
How to convert a vector map to a cellular matrix
Preparing the environment is an important element of such a simulation. Building maps are often saved in vector formats. Our algorithm, on the other side, needs a cellular matrix, which will be a reconstruction of such a map.
In a case of our CrowdSim project, an authorial component of vector map editor has been implemented. Thanks to that, simultaneously with creating vector version, we could update our cell map, and it means, that our map could be created in two formats at the same time. But it is known that professional building plans are being created by using dedicated programs.
And there is a question – how to convert such a map in one of the popular formats to a format, which is friendly to our simulator? We can use ready-to-go libraries. I have used GDAL libraries and vector to raster conversion methods.
Pathfinding
Pathfinding could be the subject of the whole series of articles but I just want to outline the most important conceptions and to explain how I have implemented that element in my simulator. Our map, which is almost cellular matrix already, can be also presented in the form of graph and pathfinding can be just looking for the shortest path in the graph between a start point, where the pedestrian currently is, and an emergency exit.
Without a doubt, Dijkstry algorithm is the best-known algorithm in this category but it assumes “naive” implementation and it will have square computational complexity. We can make that complexity much smaller if we will use the A* algorithm, which is actually an expansion of Dijkstry, and it uses heuristics defined by the programmer.
Another approach to pathfinding is represented by a group of algorithms based on potential fields. In that case, every free/empty cell on the map receives specific numeric value, which represents a potential which defines a distance from a target. That process is done before a simulation start. During that, the pedestrian only has to move from field to field with less and less potential in the next steps.
Visualisation
Now let’s talk about the most exciting part for those who can’t imagine life without vectors, quaternions and shaders. The first step will be to reconstruct our map. But let’s remember that in support of simulation, space is being represented as a grid of cells, and we can present it in that way on our visualisation.
Whole board space, visible in a visualisation, is represented by Maze class, which contains such elements as cells, passages, walls, etc.
Information regarding board structure goes to the visualisation component thanks to a file, in which all the data regarding walls and doors are written. In this file, in every line, there is an information regarding particular cell, and below you can find an entry pattern:
[element type]:[column number]:[row number]:[direction]
In the Maze class there is a method, which loads a file in that format, and later, a proper object is being created in a loop for every line by using CreateCell and CreateWall methods.
In the end, we get fully modelled building map.
Pedestrians are the next, extremely important element of our simulation. In that case, as same as before, the data are being loaded from a file that has been generated by CrowdSim, an application created by me. That file contains movement vector on every line for every single pedestrian. Every element of that vector is responsible for moving pedestrian at the particular temporary step of a simulation.
Pedestrians are moving between the next cells on a map, and they are heading to the exit. Their position on a map is being refreshed in a loop according to the data, loaded from a file. That file also contains information about an overall number of temporary steps of a simulation and a duration of a single step, measured in seconds.
Now, our visualisation is ready.
Of course, there are a lot of elements that we can add or improve in that visualisation but it’s definitely a seed of something I want to develop further. There are some options available: pause, fast forward and fast rewind to any moment we want to, and also there is an option to show movement trajectory of every individual pedestrian.
Colours under the feet show a level of crowd density in that place. The maximal value is marked by red colour and it means that crowd density level is so high that there is a huge risk of panic outburst.
Source code of that visualisation is available on my GitHub: https://github.com/bytebarian/CrowdSimulator
