Pathfinding

Written by Fidcal

For information on using path entities, see Path Nodes. For pathfinding after teleport, see Teleporting entities.

Introduction

This tutorial covers AI pathfinding. By 'AI' is meant any non-player character in the game such as a guard, spider, belcher, etc.

Plain worldspawn brush terrain (not assigned to entities) is collidable and also correctly affects pathfinding so AI 'recognize' it either as a barrier to avoid or as a surface on which they can walk. But all patches as well as brushes and models that are assigned to entities are not recognized by AI as a barrier and they will walk mindlessly forever against such obstacles unless diverted. Nor can they walk over their surface (although the player can.) This is because pathfinding does not take such surfaces into account so will not guide AI around or over them. Yet AI will collide with them so an AI may try to walk right through a model pillar but refuse to walk over a solid bridge made of static entity brush. This can be put to good use (see Preventing and Reducing Pathfinding in selected locations) but first we shall look at assisting pathfinding...

Enabling and Improving Pathfinding in Select Locations

The mappers' most important AI pathfinding control is monster_clip - it is essential in good map building. monster_clip is an invisible material used to guide AI around obstacles and over surfaces they otherwise could not traverse. It is not applied directly to existing terrain but placed invisibly around it on its own brush.

monster_clip is a texture; find it in the entity inspector under:

Media > textures > common > monster_clip

• It must ONLY be applied to a worldspawn brush
• It must NOT be applied to an entity.
• It must be applied to ALL surfaces of the brush.

The monster_clip-textured brush is then placed around an entity brush or model to either guide AI away from it or let them walk upon it. It can also be used on its own as an invisible collidable vertical barrier or as an invisible surface to walk upon.

Although substantial to the AI, monster_clip is completely invisible and intangible to the player so the player can pass right through it and be unsupported by it. For an invisible barrier or bridge for the player (but not to AI) use player_clip (also in textures > common.) player_clip is also useful to cover areas where the player might tend to get stuck.

monster_clip : Vertical Barriers to AI Pathfinding

All entity-based terrain and models that lie in the path of AI should be surrounded with a brush wholly textured with monster_clip or the AI are likely to just blunder into them. They might slide off if there is an angle but they are just as likely to get stuck walking blindly against such a barrier forever. Examples are pillars, statues, railings, anything that is assigned to an entity and is not a plain worldspawn brush should be considered. This does not apply to everything wholesale; anything that will not be in the path of AI should not be surrounded by monster_clip or it will make pathfinding more complex than it needs to be (see Preventing and Reducing Pathfinding in Select Locations.)

monster_clip brushes around vertical barriers should fully surround them or they might not work properly. In the case of irregular shapes then extend the monster_clip brush to include the outermost protrusions. In fact in some cases you might wish to be extra generous and make the monster_clip signficantly bigger if you want the AI to steer well clear for any reason.

monster_clip brushes can also be used completely on their own as invisible barriers to obstruct or divert AI for whatever reason you wish though obviously you need to keep in mind how the AI's behaviour will look to the player. Remember, the player can move freely through these invisible barriers.

monster_clip : Adding AI pathfinding to Horizontal Surfaces

To enable AI to move over horizontal entity surfaces - whether brush or model - you need to surround the object with monster_clip or the AI will refuse to go there.

• The monster_clip brush should vertically surround the object but just below the surface and no more than roughly 16 units below (not tested, some say 48) else they may fail to pathfind over it. Note that if top of the monster clip is above the surface it will still work but AI footstep sounds will be stone no matter what the surface so generally keep below.
• When walking over a monster_clip brush surface, AI may stray up to around 18 units out of the 'corridor' of monster_clip. It may be that the edge is calculated for the centre of the AI and not its outer width. For this reason you should reduce the horizontal width by around 18 to keep the AI pathfinding away from the edges where appropriate. For example on a bridge without side rails or walls, if an AI is to turn left or right at the end it will likely move over to one side or other of the bridge as it walks across and is likely to have one leg over the edge! By reducing the monster_clip width you will keep the AI in a corridor down the middle. If there were a side rail or wall of course then that would have its own monster_clip so that would keep them on the straight and narrow.
• AI walking over a lone monster_clip brush that has no entity core will sink into it by about 28 units. This means that if you make an invisible AI-only bridge of monster_clip then it needs to be 28 units higher than where you want the AI's feet to touch. So a channel with side walls with top surfaces at 100 will need a bridge whose top surface is at 128 in order for the AI to walk smoothly across flush with the side walls. Because 14 to 16 is the maximum step height for an AI you will need a short step of monster_clip at the entrance and exit for the AI to get on. So this step might be 14 units high but can and should be very shallow - even one unit deep is enough for the AI to pass smoothly on to the main bridge.

monster_clip : Systematic Method for Adding Pathfinding to Uneven Terrain

See Systematic Method for Adding Pathfinding to Uneven Terrain for an approach to covering larger areas which have irregular surfaces.

Preventing and Reducing Pathfinding Complexity in Select Locations

In areas where there are a great many entity surfaces at about the same level for the AI to walk upon then one large monster_clip brush can be exended around the lot (see all about monster_clip in the Enabling and Improving Pathfinding in Select Locations section.) This will simplify pathfinding and make it more efficient.

AI will refuse to move over models and brushes assigned to entities unless surrounded by a monster_clip brush so this is a good method of preventing and reducing pathfinding where needed. This reduces pathfinding complexity and stops AI stepping up on to places such as skirting boards (baseboards.) So...

Avoid using plain worldspawn brushwork but instead assign them to func_static or some other entity if that is appropriate on...

• Any area out of reach of AI such as rooftops, balconies, ledges, etc. and especially steep slopes as these can generate complex pathfinding.
• Areas that AI should not or will not walk on such as shallow building trim and decoration, etc.
• And do not surround them with monster_clip brushes.

Dynamic blocking/clipping with func_aas_obstacle

Based on changing conditions you might want an available route to become blocked, or vice-versa, open up later. MonsterClip is fixed, but you may enable and disable a func_aas_obstacle by triggering it. The "start_on" spawnarg will have it active (1) or inactive (0) to begin with.

Note, if you want it to exist on a certain difficulty level, but not another, you have to use "diff_#_change_0" "start_on" with "diff_#_arg_0" "0" to change the start_on spawnarg rather than simply "diff_#_nospawn", as the latter won't remove it without quitting/reloading TDM and cause pathing issues.

Steep Steps, Slopes, and Extreme Pathfinding!

The maximum slope for an AI is approximately 40 degrees from the horizontal but varies upon the situation and the AI. The maximum step height for AI and player is 16 though some AI cannot step up over 14 and perhaps less. But the minimum depth from front to back of a step is only 1 and this can be used to get extreme slopes and very steep steps - even near vertical walls! So, by making a flight of steps each 16 units higher but making each alternate one only one unit deep the overall stair is very steep. The shallow step is near invisible especially if it falls on a join in the texture and anyway it can be made invisible with texture > common > nodrawsolid. Yet AI can step up both this shallow step and the normal step in one convincing motion so this is useful for getting very steep steps where needed. The player can walk up these too with ease and without mantling or jumping.

Taking the above method to great extremes, once can have the entire stair made with shallow steps no deeper than one unit and this looks like a vertical wall. If made invisible it could really be placed against a visible vertical wall if needed. Both AI and the player will shoot up these extreme steps effortlessly. This is not so natural so not easy to think of an application but mappers are very imaginative and no doubt will use it here and there! Most particularly, keep this shallow step idea in mind when you want the player to cross very rough terrain without struggling or getting stuck. The occasional hidden step here and there and the player can scamper over a boulder field or rough debris without having to keep stopping except where mantling makes better sense.

One caveat, I set up some ladder brushes as extreme steps. The AI went up and down the ladder (albeit virtually one huge jump with no animation) BUT pathfinding went strange in another part of the mission. Not conclusive but watch for that. (If you try the ladder thing, when you have made the steps, then tilt the whole lot forward so the steps still form a vertical but jagged wall.)

With all the above, complexity of pathfinding should be kept in mind but mapping is often about balancing the advantage of one thing over another and each situation must be evaluated on its own merits.

AI Pathfinding around dynamic obstacles like dropped crates

There is code for handling pathfinding around dynamic obstacles (such as moveables, crates, etc.) so there should be no need for the mapper to be concerned with those as AI should automatically avoid them.

Viewing Pathfinding

You can view where pathfinding is enabled in-game by binding _impulse27 to a key and pressing it in the game. You can do this in the console as a temporary measure or bind it permanently in Darkmod.cfg.

For example, to bind it to the keypad asterisk key...

bind "KP_STAR" "_impulse27"

When you press the key then the pathfinding areas are shown in wireframe. Press it again and the display will turn off.

The boxes that are drawn are part of the AAS (Area Awareness System). Sections of the map are divided by dmap into clusters, and _impulse27 draws each cluster in a different color. White boxes separating clusters are where the author has placed visportals.

The cvar "tdm_ai_showdest 1" will draw arrows from AI to their intended destination.

Why func_static Brushes Anyway?

If you need to surround static entity brushes with separate monster_clip brushes for AI pathfinding then why not just leave them as plain worldspawn brushes?

Often you do, but if you do convert a brush to func_static...

• You can add the property noshadows = 1 so that it doesn't cast shadows, improving frame rates.
• It avoids creation of millions of polys in certain situations where the engine converts a brush into loads.
• It reduces pathfinding complexity (see Preventing and Reducing Pathfinding Complexity in Select Locations)

Problems, Troubleshooting

If AI are walking on patches and behaving strangely, make sure you have layers of monsterclip or worldspawn underneath the patch.

Another thing to check is whether your path corners are at ground level. If they are too high above the ground or too low into it, AI may refuse to go there.

AI may not properly path to path_corners that are less than 16 units away from worldspawn, including monsterclip.

One mapper reported pathfinding broke down due to some monsterclip penetrating a visportal. Split in two either side cured the problem. There is no known reason why monsterclip should affect visportals, but something to check as a last resort. Broken visportals in general have been known to affect pathfinding.

If AI need to hit a pathnode exactly, you can add the spawnarg "move_to_position_tolerance" "8" to the path_corner. This means the AI must hit the corner more precisely. You can do the opposite if you don't care whether AI hit the path_corner precisely, and use a large number like 20. This can avoid problems with AI circling to find a specific pathnode.