Nodegraph

A nodegraph is used to aid real-time NPC navigation. It is created by the mapper at design-time. When an NPC attempts to move to a point farther than the local navigation limit (600 units in HL2), it will use the nodegraph; complex or very small (e.g. doorways) areas will also require a graph for NPCs to move around efficiently. Unlike GoldSrc, NPCs can move off a Source nodegraph - it is mostly used in only a general sense.

The nodegraph is built into an AIN file on map load, if changes are detected or if no AIN exists. During the build the AI system draws links between all nodes near to each other and with a straight path between. 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 building the graph. The resulting AIN files are stored in <game>\maps\graphs.

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

Components

The following entities are used to create nodegraphs:

Land

info_node

info_node_hint

info_node_climb

Air

info_node_air

info_node_air_hint

Link control

info_node_link

info_node_link_controller

Construction

Node placement

Valve's nodegraph for the penultimate Episode One map.

As a rule of thumb, node density decides NPC intelligence, and the likelihood of an NPC navigating in an area. Many nodes will create a very dynamic AI environment, while none will leave NPCs stranded and unable to do much more than perform static actions (i.e. shooting, acting). You can exploit this by placing few or even no nodes in areas where you do not want NPCs to enter or remain.

The upshot of this is that the pattern of your nodes should follow the pattern of landmarks in your map. A grid of nodes across an empty room won't hurt, but won't do much to help either. A better solution, depending on the size on complexity of the room, would be a node in each corner.

A more complex room with static objects would follow the same pattern as the room itself: one at each landmark (e.g. corner). There doesn't have to be a node at every slight incline, but so long as you have a collection of nodes that create paths through and around, the graph will perform well.

The actual density with which to place nodes is up to you. Too many and you will start to lose performance, but too few and NPCs will be inhibited. You can use the image to the right as a guide to the numbers you should be aiming for. Note how the graph on top of the building to the extreme right of the image is less detailed than the graph down on the ground, where the NPCs will be interacting as opposed to merely moving.

Debugging the graph

TODO

Hints

TODO

Usage by NPCs

When an NPC attempts to build a route, it accesses the nodegraph to follow these 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, 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.

TBD

Good nodegraph 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.