Source code - monster behavior - moving around objects

[Marscaleb]

I was 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.

But I don't get what a monster does when it hits an object in its path.

 

If a monster wants to move forward, but it detects that it will hit something, what is it doing to determine where it should go instead?

[1Destro3456]

I think it explains it at some point here

 

 

[Marscaleb]

That video gets right up to it, but I'm missing something there.

If it hits something, it has to pick a new direction.  If the player is still standing where the closest angle to the player moves the monster into a wall or something, what does it do then?

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.

I tried looking at the source code, but I'm more familiar with C# than C++, so I don't quite follow the commands.

[ketmar]

there is nothing really complicated there. just look at `A_Chase()` -- this is where most logic lives.

 

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.

 

now, if the monster cannot move into new direction (or new direction requires a 180-turn), then there is a chance (roughly 70%) for monster to turn left or right (by random, and again, with movement checking).

 

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. ;-)

 

3 hours ago, Marscaleb said:

I want to understand the logic they used to keep monsters from being stuck by simple obstacles.

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. ;-)

Edited June 22, 2021 by ketmar

[Marscaleb]

19 hours ago, ketmar said:

 

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. ;-)

 

I did this, and I noticed several things.

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.

 

So now I am left with wanting to understand these factors:

One, how are they determining to follow a wall?  What makes them decide to follow a wall instead of just trying another (random?) angle that might lead them to the player?

Two, once they are following a wall, how are they tracking this wall?  What are they doing to check if they've reached the end of the wall?

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.

[ketmar]

1 hour ago, Marscaleb said:

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.

 

1 hour ago, Marscaleb said:

One, how are they determining to follow a wall?  What makes them decide to follow a wall instead of just trying another (random?) angle that might lead them to the player?

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.

[Marscaleb]

Okay, I get it now.

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...

 

I'm still a little curious about some other things.

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.

[ketmar]

5 hours ago, Marscaleb said:

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.

it looks quite complicated, but actually is not. ;-)

yeah, `d[0]` is unused, because for some reason whoever wrote that code decided to use 1-based array indexing.

then, `d[1]` set to horizontal direction to the player (EAST, WEST, or NODIR).

`d[2]` set to vertical direction (NORTH, SOUTH, or NODIR).

(yes, this is done exactly by the quick checks you described.)

now, if both `d[1]` and `d[2]` are not NODIR, then we have to try a diagonal movement first (it is taken from lookup table for some reason).

 

"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.

 

if the monster have to perform a diagonal move, and can do it, then we're done.

 

otherwise, the code tries both "axis-aligned" directions (it usually tries the longest distance first; if both are equal, then with probability ~20% it tries vertical first).

 

at each step, the code checks if new direction is not "turn around", and rejects all "turnaround tries".

 

finally, if neither direction succeeds, the code tries all 8 directions (still avoiding turnarounds).

 

and as the last step, the code tries "turnaround direction", because at this stage it means that this is the only possible way.

 

 

[idbeholdME]

On 6/21/2021 at 8:08 PM, 1Destro3456 said:

I think it explains it at some point here

 

Regarding the video at 1:48. The reaction time of 8 ticks unless it's Nightmare. A couple of questions.

 

1) How does this behave on UV-fast? Does it retain the 8 ticks reaction time? I assume yes.

 

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?

 

3) Bonus question. How does the fast monsters option in GZDoom work? Does it keep the 8 ticks or not?

 

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.

Edited June 24, 2021 by idbeholdME

[Shepardus]

33 minutes ago, idbeholdME said:

Regarding the video at 1:48. The reaction time of 8 ticks unless it's Nightmare. A couple of questions.

 

1) How does this behave on UV-fast? Does it retain the 8 ticks reaction time? I assume yes.

 

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?

 

3) Bonus question. How does the fast monsters option in GZDoom work? Does it keep the 8 ticks or not?

 

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.

1) Yes, -fast retains the reaction time. This is the primary difference between Nightmare and UV with -fast and -respawn, besides the double ammo.

2) Not sure what you mean by a "custom difficulty." Vanilla Doom only has a fixed set of difficulties without modifying the source code. If you're talking about ZDoom, see (3).

3) GZDoom used to have instant reaction for both -fast and Nightmare until quite recently. In v4.6.0 fast monsters and instant reaction are separate, and Nightmare enables them both.

[idbeholdME]

6 hours ago, Shepardus said:

1) Yes, -fast retains the reaction time. This is the primary difference between Nightmare and UV with -fast and -respawn, besides the double ammo.

2) Not sure what you mean by a "custom difficulty." Vanilla Doom only has a fixed set of difficulties without modifying the source code. If you're talking about ZDoom, see (3).

3) GZDoom used to have instant reaction for both -fast and Nightmare until quite recently. In v4.6.0 fast monsters and instant reaction are separate, and Nightmare enables them both.

2)Yes, playing in (G)Zdoom. I took the Nightmare difficulty definition example  https://zdoom.org/wiki/MAPINFO/Skill_definition from Zdoom wiki page on MAPINFO, removed the respawn and double ammo and named it "UV/NMhybrid".

 

But if it is as you say in 3), then it probably behaved the way it should have (0 reaction). And you just told me that it wasn't even necessary :D

 

You say that the reaction time is now an option in GZDoom? Definitely will check that out. My upgrade to 4.6.0 is pretty recent.

 

Thanks a ton.

 

EDIT:

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.

 

EDIT 2:

Scratch that. The latest GZDoom I've been using was 4.5.0. Gonna try the 6.0 now.

 

EDIT 3:

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.

 

skill UVNMhybrid
{
   AmmoFactor = 1
   FastMonsters
   InstantReaction
   RespawnTime = 0
   SpawnFilter = Nightmare
   name = "UV/NM hybrid"
}

 

Edited June 24, 2021 by idbeholdME

[idbeholdME]

Also, one more thing I forgot to mention (sorry for double post) that I found very interesting in the video.

 

Now I know why sometimes, monsters did no react to getting hit. Had no idea it was because the second idle frame makes them oblivious. I've seen it happening somewhat regularly while playing, great to finally have the answer.

 

Would you consider it a bug/oversight? Got me thinking that it could be a new compat option for GZDoom. It has the habit of offering fixes for stuff like this.

[Marscaleb]

On 6/24/2021 at 3:36 AM, ketmar said:

then, `d[1]` set to horizontal direction to the player (EAST, WEST, or NODIR).

`d[2]` set to vertical direction (NORTH, SOUTH, or NODIR).

(yes, this is done exactly by the quick checks you described.)

now, if both `d[1]` and `d[2]` are not NODIR, then we have to try a diagonal movement first (it is taken from lookup table for some reason).

 

What could cause them to be set to NODIR at this point?

[ketmar]

11 hours ago, Marscaleb said:

What could cause them to be set to NODIR at this point?

it basically this:

distance_x = player_x-monster_x;

if (distance_x < -10) dir = WEST; else if (distance_x > 10) dir = EAST; else dir = NODIR;

 

doesn't make much difference, tbh, and can be simplified to something like:

dir = (distance_x < 0 ? WEST : EAST);

[ketmar]

12 hours ago, idbeholdME said:

Would you consider it a bug/oversight?

no, i don't think that it is a bug. i believe than even if it was something done accidentally, id liked it and promoted it to feature. it is one of various random things in the game: "if you're lucky, the monster may not realise who shot it."

[Marscaleb]

13 hours ago, idbeholdME said:

Would you consider it a bug/oversight? 

I would.  It just seems disconnected from the experience people were going for.  Look at it outside of the code itself.  If you were playing any kind of shooting game and you shot an enemy and they didn't react, wouldn't you think it was a bug?

[ketmar]

28 minutes ago, Marscaleb said:

If you were playing any kind of shooting game and you shot an enemy and they didn't react, wouldn't you think it was a bug?

not more than shooting a soldier with a sniper rifle, and their comrades never noticed. ;-)

[Marscaleb]

Something else I've thought of that I don't get about this code.

If an enemy walks past the player, it turns around.  How does it know if it has walked past the player?

I mean otherwise the player could easily walk around in circles around a monster.  Perhaps not perpetually, but often enough the move counter would get set to a high enough value that a simple side-step could have a demon keep walking in the wrong direction for a long time.  So how does the code detect that it has walked past the player?

[ketmar]

it doesn't do anything special, simply choosing the new direction with the code above. in open spaces the monster will turn around in small steps. and in narrow corridoir it is quite hard to run around the monster. ;-)

 

it is forbidden to do 180-dg turns, but doing "axis-aligned" turns are ok. so when the player suddenly becomes unreachable due to required 180-dg turn, the monster will quickly do several smaller turns, and reaim itself. this is why "axis-aligned turning" code is there. the chance that the player will be exactly on the same x or y coordinate with the monster is close to zero, so "axis-turning" will be in effect. in-game it will usually look like the monster quickly turns around in two steps, so it even helps the animation a little. ;-)

[Marscaleb]

So wait, it doesn't actually detect that it has passed the player?

The video made it sound like it could turn before its move counter hits zero.

[ketmar]

no. the monster tries new direction when movecount is zero, or when it cannot move forward. movecount is usually quite small, and there's no need to take any special actions.

 

but note that monster attack sequence usually has `A_FaceTarget()` call, so monsters with ranged attacks can do 180 turns if it is required for their attacks.

[3t0]

Thanks great analysis guys!