Навигационный граф - специальная структура, которая формируется для каждой границы и состоит из набора ребер разного типа и треугольников, образованного ребрами, в которых возможно движение людей.
Навигационный граф используется для определения расстояния до границы и направления движения, в котором необходимо двигаться человеку, чтобы по кратчайшему пути добраться до границы.
Ребра навигационного графа бывают следующих типов:
- Препятствия (обозначаются красным цветом). Человеку запрещено пересекать такие ребра. Если область неограниченная, то границы области также представляются препятствиями.
- Ребра свободного движения (обозначаются синим цветом). Люди могут пересекать такие ребра.
- Ребра-выходы (обозначаются зеленым цветом). Формируются элементами сцены “Выход” и обозначают области, достигнув которые, человек считается эвакуировавшимся.
Для каждой вершины навигационного графа рассчитывается её вес - расстояние по кратчайшему пути до границы, для которой этот навигационный граф сформирован.