Monster Code

[Amelie Robertos]

Iwas curious about how the monsters in Doom calculate how to reach the player. I'm reasonably sure that Doom doesn't use true pathfinding code, given the processing power they had to work with, and how you don't have to lay out paths in the levels.

I was watching a video that explained the basics; it finds the eight-way direction closest to the target, it moves in that direction until it hits something or runs down its move counter and then it recalculates it's direction.

The video shows it walking the length of a wall and says that it turns around when it gets to the end of the wall. How is it determining that it had reached the end of the wall? And then what does it do at that point? Is it trying to move to the other side of the wall? In the video there is a gap in the wall, and if the pinky moved forward just a little bit to try to continue following the wall it would get around the wall and be able to reach the player, but if it just recalculates the angle closest to the player then it would turn around and walk the length of the wall again. And if the wall was very short then the pinky would get stuck perpetually walking a very small obstacle unable to cross it.

I'm trying to understand how games programmed such behaviors back in the day. This was before we had modern pathfinding and nav mesh stuff; heck this doesn't even have path nodes like in UT99. I want to understand the logic they used to keep monsters from being stuck by simple obstacles.

basically, in that function the monster checks where its target is, and choosing a new direction to move out of 8 possible directions (i.e. monsters never walk by arbitrary lines, only horizontal, vertical, or diagonal movements are allowed). then the code checks if new direction doesn't require 180 degrees turn (because such turning is forbidden; but see below). if new direction doesn't require a turn, the code checks if the monster can move in that new dir (i.e. simulates a step). if movement is allowed, we're done.

if all new pathes are blocked, the monster finally tries to turn around -- this is the only case when it does 180 degree turn. that's why monsters "run away" from the player in narrow corridors -- they simply cannot turn around.

this is basically it. no complex logic or pathfinding, so-called AI is quite dumb. the illusion of more-or-less smart movement comes from map design, and from the feature of human brains to see patterts of smart behavior everywhere. ;-)

run forward a little. turn a little, if it is possible. run forward a litte. turn a little, if it is possible. keep doing that. never turn 180 degrees until there is no other directions available. add some randomness to the mix.

p.s.: if you want to see how dumb everything really is, turn on object view cheat on automap, and go to Doom2 MAP01. kill all zombies, then quickly run forward, and backward back to where you started. and then watch the imp walking down the corridor, and then unable to get out of that big room. it will wander there, unable to understand that it should go back the corridor it walked. ;-)

First of all, I noticed that if the player is just a little further forward they will manage to navigate through the long corridor all the way to reach the player, which is really what makes the AI "feel" more intelligent, because it (sort of) can navigate through the map to reach the player. If the player is south enough in the first room, then if a monster randomly shambles into the wall at the very tip of the hallway they recalculate which way to turn, and move south to face the player. But if the player is just north enough, when they hit that wall they turn north, and then they follow that wall all the way around and find their way to the first room.

I also noticed that when a monster finished following a wall it tries to find the player again, which can produce a little random walking. It will quickly find its way to the next wall and follow it. But the key element here is that it is not actually tracing the whole curved path to the player, just following one wall at a time, which is going to lead the monster to find the next wall.

I also noticed that while the monster randomly shambled around int he big room, sometimes they would bounce off a wall and then walk due east, (the exact opposite direction of the player,) and continue in that path perpetually until they hit another obstacle. They never get triggered by moveCount getting decremented again.

Three, why are monsters sometimes walking due east into perpetuity? Off hand I wonder if they are trying to follow the wall, but since that wall is at an odd angle, they try to follow it moving straight north, bump into it and change their angle, but now are moving away from the wall in a way that they can never detect that they have reached the end of this wall. But this is pure conjecture since I don't understand the first two points I mentioned.

sometimes they would bounce off a wall and then walk due east, (the exact opposite direction of the player,) and continue in that path perpetually until they hit another obstacle. They never get triggered by moveCount getting decremented again.

that is due to "no 180-degree turns" rule. the monster cannot turn around, so the code decides to not take any turns at all. there is a small random chance of slight turns, but most of the time the poor thing will just walk forward until it hits something.

this is basically the one question. the monster is never "following the wall" per se, it is just an illusion. what it really tries to do is check which turn it should take to face the player, and then it checks if it is possible to move into that direction (see also "no 180-dg turns" rule). if it is not possible to proceed in the new direction, the monster keep walking in the old direction. this creates illusion of "following the wall", as the thing tries to turn, bumps into the wall, and cancels the turn.

the only idea of monster movement is: "face the player, then walk forward". this is basically all what AI tries to do. the illusion of "smart" movement is created by "no 180-dg turn rule", and by checking if it is possible to move into the new direction. ah, and some very slight randomness. also, `A_Chase()` is not called on each tic, so the monster keeps walking for some time before re-evaluating its path.

also, as you can see from our experiments, another key thing to make everything work is constant player movement. if the player is standing still, monsters will (mostly) aimlessly repeat their wander actions.

and note that "no 180-dg turns rule" helps monsters to get away from narrow corridors. without that rule, monsters will be oscillating there, but with that rule active, they are forced to walk the whole corridor before trying to change their direction.

Honestly I'm pretty impressed; the one designation of not allowing them to choose a direction opposite of their current movement is such a tiny little thing, and yet it enables them to follow corridors. How did anyone think that up? Or was it just some sort of happy accident...

This is more about the specific code than the general process, but I'm wondering how they determine "second best option," or rather, how they determine that with optimal code. I can't think of how to do that without running a massive series of if statements that check all eight directions.

I think I found the code that does this in P_NewChaseDir. I see it creates an array just called "d" (which it gives an array length of 3 but only uses the second two?) and it sets one to be either north or south and one to be either east or west. (I'm guessing a quick check of player position being greater or smaller in X and Y?) But I don't understand the logic of what it is doing; how it is quickly determining each possible route to the player and whether or not it is viable.

"trying movement" is easy: the code simply calculates new coordinates in the given direction, and checks if that place is not occupied by anything. i.e. it simply simulates a "step", using the usual Doom movement logic.

2) If I use a custom difficulty based on Nightmare with only the respawning disabled, will those 8 ticks be gone? Does it have to have specific name or will this work? I see in the code that it checks specifically if a skill called nightmare is selected. If my custom difficulty has a different name, I assume it won't work?

I've started playing with a custom difficulty a couple of years back as described in 2), because I wanted to get rid of this 8 tick reaction time. But seeing this now, my guess is that really did not work because I named it differently.

Also, just to check. Is the reaction setting an option in directly in GZDoom settings? Or should I just add InstantReaction to my difficulty definition? I'm not at my PC at the moment so can't check. Thanks.

Just tested it. The reaction time is not an option in the GZDoom menu. So you have to make your own custom difficulty to get the proper Nightmare behavior. Just adding InstantReaction to the skill definition in GZDoom 4.6.0 did the trick. Here is the difficulty I am using for it (now updated for GZDoom 4.6.0) that is the same as UV -fast but with the 8 tick reaction delay removed to get a proper Nightmare-like experience if anyone wants it. It's basically just Nightmare definition but with removed double ammo and respawn. I also enabled cheats as I sometimes like screwing around with IDDT, IDCLIP and such and removed the confirmation needed for selecting it. I autoload it every time I launch GZDoom. Makes it much quicker to just be able to select the proper difficulty instead of always checking whether the Fast Monsters is on in the menu on every launch. Copy and paste it into a txt file named MAPINFO and drop it on the GZDoom executable and you should see the difficulty in the new game menu. Rename it to anything you like by changing the "name" parameter. If you are not on GZDoom 4.6.0, remove the InstantReaction line.

3a8082e126