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 spend too much time. NPCs will be able to cross the area, assuming there is a linked destination on the other side, but will not perform well while interacting within it.

The upshot of this is that the pattern of your nodes should follow the pattern of landmarks in your map. An empty area does not need many nodes as there is little for NPCs to do, but one with many nooks, crannies and points of interaction will need a very dense graph.

There are always some nooks however: even an empty room has the landmarks of its corners, and these are where nodes should be placed. If it is a very large but still empty room, a handful of nodes across the floor might also be beneficial.

A more complex room with static objects would require nodes at each new landmark. If there is a low wall, there ought to be one at each end, and at least one on each long side. There doesn't have to be a node at every slight incline, but so long as you have a collection of them that create paths through and around, the graph will perform well. Remember though, if there is already a node nearby then there is no need to place a new one just because there is a second landmark there.

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.

Hint nodes

Main article:  Hint nodes

'Crouch Cover Low' hints from Half-Life 2's plaza power core scene. Note how every node provides hint data.

Hint nodes are navigation nodes with meaning, presenting NPCs with information about the area in which they are located. Their application is very important for a successful nodegraph.

As their name suggests, hints nodes will add to the nodegraph like a normal node; because of this, NPCs will be able to one as a normal node, even if they can't use it as a hint. Hint nodes can only be used as hints at, to, or from the precise location of the entity.

There are several key hints that you should know about when constructing your nodegraph:

Entrance / Exit Pinch

Forces NPCs to file through one at a time and prevents congestion. You should place one of these anywhere that a wider area narrows into a smaller one, particuarly doorways. Narrow corridors should have a hint of this type at both ends. You may want to place the node slighly before or after the pinch, if there are problems with its links or with NPCs reaching it. It is quite possible to have two hints of this type adjacent to each other if there is enough room.

Crouch Cover Low

Crouch Cover Medium

These two hints tell NPCs that a node is safe to take cover at. While the safety of a node could be calculated off the cuff, placing this hint makes its location more obvious to the AI and lowers processing overhead. NPCs won't use the hint if it can be seen by a hostile.

Override jump permission

NPCs can jump from one hint of this type to another, if they can reach their destination and if doing so will not hurt them. This is the only way to allow NPCs to jump while navigating. Note that it is not required for an Antlion or Fast Zombie to make its leaping attack, but is for them to jump while moving to a location.

There are many more useful hints: for a complete list, see the Hint nodes article.

Debugging the graph

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.