Navigation Graph – a specialized structure generated for each boundary. It consists of a set of edges of different types and triangles formed by those edges within which people are allowed to move.
The navigation graph is used to determine the distance to a boundary and the movement direction a person should follow to reach the boundary along the shortest path.
There are several types of navigation graph edges:
- Obstacle edges (shown in red): These cannot be crossed by people. In unbounded areas, the area boundaries are also represented as obstacles.
- Free movement edges (shown in blue): These can be crossed freely by people.
- Exit edges (shown in green): These are formed by “Exit” scene elements and represent areas that, once reached, indicate a person has evacuated.
For each vertex in the navigation graph, a weight is calculated — the distance along the shortest path to the boundary for which this navigation graph is formed