Nodegraph

A nodegraph is a special component of a map designed to aid real-time NPC navigation. Nodegraphs consist of manually placed "nodes" with automatically generated links. They are automatically created when a map is loaded into a game which allows NPCs.

Each individual node represents a precise position on the map that NPCs can move to. The game automatically generates "links" between adjacent nodes. NPC navigation uses these links to move from node to node, although not necessarily to the precise location of the nodes themselves, and not necessarily in straight lines.

Note:Bots in multiplayer games use Navigation Meshes rather than the nodegraph.

Compiling

The nodegraph is automatically compiled into an AIN file when a map loads, unless there is an existing AIN with the correct checksum. The AIN output is then stored in <game>\maps\graphs. When the nodegraph is built, a message saying "Node Graph out of Date. Rebuilding..." will display for all players in the server.

Note:When distributing .ain files for a Source game or mod on Steam, please note that the game will recognize the downloaded files as being out of date and rebuild them anyway. This also means every user will experience the aforementioned "Rebuilding" message when first loading each map.

Tip:This can be suppressed by turning on the ai_norebuildgraph cvar, which can be done automatically in CFG files like autoexec.cfg. Keep in mind that this means any changes to the .bsp will no longer automatically update the .ain, so you will have to manually update nodegraphs from your work version to the Steam build.

Components

Nodes

Different nodes exist for different types of navigation. Most NPCs use Ground Nodes, which automatically fall to the ground by default. Air Nodes are used by Flying NPCs and remain suspended in mid-air. Climb Nodes are used by Climbing NPCs and are designed to be used around ledges.

The following entities are used to place AI nodes in Hammer:

Ground Nodes

info_node

info_node_hint

Air Nodes

info_node_air

info_node_air_hint

Climb Nodes

info_node_climb

Links

When a nodegraph is built, Source's AI system draws straight lines between all nodes less than 720 units apart and calculates which ways NPC Hull types can travel down each path. Dynamic objects like physics props and doors are ignored during this process.

Nodegraphs compute multiple types of links based on different types of nodes:

• Ground links connect two Ground Nodes which NPCs can walk/run between. Most NPCs use these by default.
• Jump links connect two Ground Nodes which NPCs can jump between. These links are only calculated between adjacent ground nodes which couldn't create a direct ground connection.
• Climb links connect two Climb Nodes which NPCs can climb between. These are used by Climbing NPCs.
• Air links connect two Air Nodes which NPCs can fly between. These are used by Flying NPCs.

NPCs can be programmed to use multiple types of links interchangeably. For example, npc_fastzombie from Half-Life 2 is capable of using Ground Links, Jump Links, and Climb Links at any time.

The following entities are used to control the way nodes are linked:

info_node_link

info_node_link_controller

info_radial_link_controller

Construction

Node placement

Valve's nodegraph for the penultimate Episode One map.

Note:Maximum amount of nodes in the nodegraph is 1500.

The goal of a nodegraph is to record a very rough approximation of everywhere npcs can, and should, traverse. The pattern of your node placement should reflect this. You've properly noded a map when it's possible to travel anywhere across your map, by tracing a straight line from one node to another. Generally, this means placing a node on each corner of an obstacle. The more detailed an area, the more nodes will be required for NPCs to properly navigate. If you do not provide enough, NPCs will not make use of tactical opportunities like taking cover behind map geometry and props. Provide no nodes at all and NPCs will be practically stranded, they won't maneuver around their enemies, they'll just stay put and shoot!

However, this is not to say you should blast your map into oblivion with an avalanche of nodes. Low-detail areas can be beneficial sometimes, as areas through which you want NPCs to travel but not get bogged down. If you are building a beach assault for example, you will probably want to keep the beach relatively sparse of nodes to ensure that the attacking NPCs keep moving until they reach cover (even if you did add nodes, there would probably be few landmarks for the AI to make use of).

The destination should have a dense nodegraph however, to ensure that the NPCs do not all arrive at the same point and trip each other over.

The actual density with which to place the nodes is up to you. You can use the image to the right as a guide to the numbers you should be aiming for. Note how the graph is quite sparse on the building roof to the extreme right, but much denser down on the ground, where the player will be.

map_edit

Main article:  map_edit

Placing nodes in Hammer can become very tedious. To speed the process up, you can use map_edit to place nodes from a first-person perspective at run-time. You can also perform advanced tasks such as manually removing node links. map_edit places nodes ten units above the ground, resolving displacement difficulties automatically.

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.

• Hints nodes will add to the nodegraph like a normal node.
• NPCs will be able to use a hint as a normal navigation node, even if they can't use it as a hint.
• Hint nodes can currently 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:

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 that generally do not jump (e.g. npc_citizen, npc_alyx) can have their behaviour overridden by this hint. NPCs that jump as a part of their basic AI (e.g. Antlion, Fast Zombie) do not need these hints. A start and end jump permission hint are required, and NPCs will not attempt jumps that they cannot make or that would hurt them.

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

Debugging the graph

Main article:  ai_show_connect

Overcoming a bad node link. The maroon line means that HUMAN_HULL NPCs do not have a link here; this is because the doorframe cuts into the projected hull's path. Adding a new node directly in front of the door adds a functional (green) link and allows HUMAN_HULL NPCs access.

Once you have created your graph, making sure it works is the next task. Most of the work is done with the ai_show_connect console command. Its workings are already covered in its just-linked article, and will not be repeated here. The important thing to look for is a green connection of the relevant NPC Hull type. The hull is the bounding box of the NPC, and there are quite a few types. The default is HUMAN_HULL, which applies to all humanoid NPCs. There are various other hull types that you need to get used to as you work out what works for what NPCs - see the NPC Hull for reference.

If there is no link between two mission-critical nodes, or if there is a link that does not fit the NPC hull you need, the next job is to rearrange the nodes in question so that there is. You must consider:

Is the path between the nodes straight?

A node's job is to define straight paths. NPCs then take that information and turn it into curved paths through triangulation if needed.

Create a new node between the non-linking two if you need to round a corner.

Is the path between the nodes big enough for the NPC hull on all axes?

Don't forget the ceiling height! This is especially important for air nodes.

If a node is too near to a wall, links to it will be invalidated, even if the NPC could just stop a little short.

Keep in mind that the path must be big enough in a straight line. There can't be anything poking into the projected hull at any point. Use the maroon line, if there is one, as a guide.

If you have a hull problem at a corner, or the start or end of a corridor, try moving the node out into the open a little. It probably won't make too much difference and will save having to make a second node.

Link control

The info_node_link is a VERY valuable entity. It "forces" a connection between two nodes.

For example, if you are building an elevator and an NPC needs to come along for the ride, it is sometimes difficult to get the info_nodes to work properly since the elevator is a brush-based entity and not a world brush. This can cause a myriad of problems and the NPC will not want to get on the elevator, even if you have a scripted_sequence on it. However, by using an info_node_link you can solve this problem.

Simply place an info_node on the ground and another right above the elevator platform. Now make an info_node_link close to those nodes. Check the properties of the info_nodes and get their NodeIDs. Now go back into the properties of the info_node_link and put the target NodeIDs in the starting and ending node sections. That's all there is to it. You will now have two connected nodes that can be enabled/disabled on command.

Suggested node patterns

Some locations require careful node management. The Valve Developer Community's recommendations for these situations follow:

Optimal node pattern for doors

Main movement targets

Guarantee a nodegraph link by presenting a straight line through the doorframe.

Placed slightly ahead to decrease the likelihood of NPCs stopping too close to the door and causing congestion.

Flank nodes

Create alternate exit points, and are a solid choice for FIND_COVER routines.

Entrance / Exit Pinch

info_node_hint of type Entrance / Exit Pinch.

Ensures that NPCs travelling through the doorway do so one at a time.

Limitation: NPCs that are not using the node (i.e. are not travelling through the door) may still choose to stand on it! This is a bug that should be fixed.

Please help to expand this list with your own findings!

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.

See also

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