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, drawing links between all nodes near enough to each other and with a straight path between. Node graphs are stored in the hl2\<modname>\maps\graphs directory.

The node graph is built from a set of level designer placed entities, listed below ('Components'). 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.

There are separate node graphs for flying and land-based NPCs. An NPC could feasibly switch between the two, but there is currently no known example of such behavior.

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, and find the best path between them.
• 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.

Components

The following entities can be used to create a node graph:

• info_node
  • info_node_hint
• info_node_air (Flying NPCs only)
  • info_node_air_hint (Flying NPCs only)
• info_node_climb (Climbing NPCs only)
• info_node_link

TBD

Good node graph construction tips.

• When placing nodes on steep displacements, raise them by around 10 units to ensure a connection.
• Check your graph with ai_show_connect in-game for any bad or missing links.

See also

• ai_show_connect, map_edit
• ai_debug_nav, npc_go, npc_route, ai_moveprobe_debug.