Node graph
When an NPC attempts to move to a point farther than the local navigation limit (600 units in HL2), it will use the node graph to build a route.
Whenever a map is loaded, the AI system checks the timestamp on the existing node graph for the map. If there is no node graph for the map, or the map has changed, the AI system will rebuild the node graph. Node graphs are stored in the hl2\<modname>\maps\graphs directory.
The node graph is built from a set of level designer placed info_node entities. For each node, the AI system determines which other nodes should connect to it, and for which NPC Hull. The AI system ignores all potentially movable entities (doors, func_trains, etc) when doing this.
Usage
When an NPC attempts to build a route, it follows these general steps:
- Find the nearest node to the NPC's current position.
- Find the nearest node to the NPC's desired movement point.
- Ensure the two points are connected via the node graph.
- Use moveprobes to ensure that the NPC can reach the nearest node.
- Use moveprobes to ensure that the NPC can reach the desired movement point from the nearest node to it.
TBD
Good node graph construction tips.