[Back]

M. Bruckner:
"Orientation inside of a Pedestrian Flow Simulation";
Poster: ASIM-TCSE Workshop 2012, TU Wien; 2012-02-13 - 2012-02-14; in: "ARGESIM Report", S. Tauböck, F. Breitenecker (ed.); Argesim / Asim, 37 (2012), 8 - 9.

Introduction:
This Abstract discusses algorithms that support virtual entities to navigate through a building which is modelled using an agent based system (AB). The main component of this model is the discrete grid that contains the basic struc ture of the building in its cells.
Each of them can be, for example, a corridor, a wall,astaircase, and
so one. Because it is very difficult to model a 3D building using only one discrete grid, each floor is mapped to its own grid; these grids are connected with special transformation areas at the end of the stairs.
To simplify a student´s life they need a plan how to get from point A to point B using the shortest way possible. Basically we distinguish between two algorithms:
One for the global routing, which supplies a list of intermediate
waypoints and one for the local routing, which directs the entity from one of these waypoint to the next.
Local Routing: For the local routing algorithm a static floor field is used. This is, as the name suggests,a field of static values,which contains the distances to the various waypoints. This field is embedded into the AB. So it is possible to "ask" each cell "how far is it to the door with namedoorLectureRoom8". To determine now the shortest path, the associated cells will be scannedfor each direction
and afterwards the arithmetical average is calculated. So the
direction with the mallest distance is to favor for the next step.
To initialize this data structure, a modified ariation of the Flood Fill algorithm is used. This is a simple procedure from Computer
Graphics, to colorize a bordered area.
The first step is the detection of all waypoint cells which
are in direct neighbourhood from a corridor, or a stair cell. So ea
ch of them is starting oint for the floor fillalgorithm and initialises ith the distance zero. Afterwards the eight neighbourhood cells are visited and the istance value will e pdated if the newvalue is smaller than the current alue. his procedure goe one recursive
so that the distance values fill the whole discrete grid. Global Routing: For the global routing algorithm an un direct ed and weighted graph will be generated with help of
the static floor field. Now, usingthis graph and the Dijkstra's algorithm a waypoint list with the shortest or fastest way will be created. Shortest and fastest way does not necessarilyhave to be always the same, especiallyspecial incase of using elevators. Figure
2 depictures the underlying idea of this graph. It is obviously that in on discrete grid each waypoint is connected with each other and only the change areas give the Dijkstra algorithm the possibility to jump from one grid to another. 
Node: Basically there exist only two types of nodes:doors and change
-areas which include also the elevator-areas. In case of doors only the entrance ofthe lecture-rooms and building-exits are considered.All other doors, such as fire doors or corridor doors are generally disregarded . Even the small est narrowing in a corridor proved to hinder people´s movement ignificantly. The change - areas give the individuals the ability to change the discrete grids, for example at changing floors at the end of a stair or using an elevator  Edges: In every AB each node is connected via edges with every other one, whereby each edge has two weights, the distance in meter and the time needed by an average human to walk this way without obstructions. Routing: Now if a new entity is inserted into the simulation the nodes with normally represent the start and finish rooms are picked out of the graph. Afterwards a storage with all, until now, calculated ways through the building will prompted if the calculating way point list is already deposited. This search needs only a short time but can help to avoid an expansive search process. If the way does not exist already the Dijkstra algorithm calculates and forwards it to the entity and saves it afterwards in the before mentioned storage. In this list the first and the last waypoint are the start and finish rooms. Now it is possible for the entity to start at the grid were the start node is located and "ask" the grid for the second waypoint. If they reach it there are only only two possibilities: the node can be the finish waypoint or it is a change area that transports them to another grid where they, after updating their waypoint to node three, continue moving along. So withthese two algorithms(global and local) it ispossible to reach each target room in a building in the shortest or the fastest way, depending on the selected edge-weight of the Dijkstra's algorithm.