From Valve Developer Community
A Nodegraph is configured by the Level Designer to aid real-time NPC AI navigation. The Nodegraph consists of a number of manually placed Nodes and a number of automatically generated Links between the Nodes. Each individual Node represents a precise position on the map that NPCs can move to. The Nodegraph Links are generated during Compiling, but can be adjusted using the Link Control entities. NPCs navigating by AI will move from Node to Node via the Links, although not necessarily to the precise location of the Nodes themselves, and not necessarily in a straight line.
- A Node may also be associated with an AI Hint, such as "Crouch Cover", to help NPC AI make the best use of a particular position. See Hint nodes.
- See also Counter-Strike's bot Navigation Meshes.
Nodegraphs are automatically compiled into AIN files when a map loads, unless there is an existing AIN with the correct checksum. During the build process Source's AI system draws straight lines between all nodes less than 720 units apart and calculates which NPC Hull types can travel down each path, if any. Dynamic objects like physics props and doors are ignored during this process. The AIN output is then stored in
There can be two nodegraphs in each map (although both are compiled to the same AIN): one for Flying NPCs ('air'), and one for walking, driving, or otherwise land-locked NPCs. An NPC could switch between the two, but there is currently no known example of such behaviour.
Air nodes are suspended at the location they are placed, but Ground nodes drop to the ground automatically during compile unless specifically told not to through the
Keep editor position flag.
The following entities are used to create nodegraphs:
- Ground Nodes
- Air Nodes
- Link Control
The goal of a nodegraph is to record pathways, and the pattern of your node placement should reflect this. It should be 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, and may even have trouble simply walking around. Provide no nodes at all and NPCs will be practically stranded, unable to do anything more complex than static actions like shooting and acting.
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.
- 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 about the ground, resolving displacement difficulties automatically.
- Main article: Hint nodes
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:
- 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, particularly doorways. Narrow corridors should have a hint of this type at both ends. You may want to place the node slightly 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 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
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.
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
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.