Pathfinding

Written by Fidcal

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 brush terrain is not only collidable but also correctly affects pathfinding so AI 'recognize' it either as a barrier to avoid or as a surface on which they can walk. But models and patches 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 patch bridge. So what is one to do?...

Enabling and Improving Pathfinding in Select Locations

Pathfinding over and around models

The mappers' most important AI pathfinding control is a material called 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 material texture; find it in the entity inspector under:

Media > textures > common > monster_clip

and apply it to ALL surfaces of the brush.

The monster_clip-textured brush is then placed around a 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.

Pathfinding over patches

Normally dmap will not create pathfinding info over patches (there is a special dmap qualifier but I do not know what the repercussions in terms of complexity, performance so will not cover it here.

So, to get AI to move over patches you should create a hidden terrain of caulk brushwork below the patches and then dmap will create pathfinding over that. The AI will still collide with the patches above it so they will not sink through it to the caulk brushwork below. Note you may need to create steps or ramps in the caulk brushwork to get AI to move over sloping patches etc.

monster_clip : Vertical Barriers to AI Pathfinding

All 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, furniture. 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. In the case of low models you probably want the monster_clip to cover the surface so the AI can climb over. Higher obstacles it is probably best to extend the monster_clip to the ceiling or at least far too high for the AI. Medium height models such as tables you probably need to use your judgement on a case by case basis. Sometimes you might want an AI to be able to climb up over a stool and across a table to look natural. In other situations you want to block the AI from the table completely. Generally I extend the monster clip way over such models.

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 model surfaces 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 no more than 16 units above and below else they may fail to pathfind over it.
• 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.

Preventing and Reducing Pathfinding Complexity in Select Locations

In areas where there are a great many 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 because dmap only needs calculate pathfinding for that one large surface instead of many.

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 game. You can do this in the console as a temporary measure or bind it permanently in doomconfig.cfg, eg, 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. This is temporary and the display will time out after a few seconds. It also changes colour but the signifcance of the colours I do not know.