How pathfinding in Doom works?

[JunkerKun]

This is not exactly zDoom related, but I'm interested in how AI and pathfinding worked in the original Doom.

As far as I could get from searching in the internet, enemies don't use any pathfinding algorithm - they just go in zigzags.
But how did Carmak make it so efficient? I mean, checking collision for every enemy would be quite a time-consuming task for PCs at the time.

Is there anyone who knows the answer? (besides Carmak himself )

[cambertian]

I think it has to do with Blockmaps, though I don't understand how those work either. If it's not too technical, a quick fill-in from a (clearly superior) programmer would be appreciated

EDIT: Fixed the link.

[Edward-san]

OT note: Please don't link to wikia. Use doomwiki.org for that.

[Rachael]

Pathfinding in Doom pretty much works like this: Move towards the player in the closest 45-degree direction. Do this until a wall is hit or the monster starts drifting away from the player. Once a wall is hit, go in a random direction for several seconds, then try again.

There really isn't any actual pathfinding code in Doom. The monster just gets lucky.

[JunkerKun]

Huh. Talk about 90's game programming tricks...

Well the question now is - how did Carmak make it work fast enough. Collision checking isn't the most performant task to do... Or do they only check it once in a few seconds?

[ibm5155]

The colision test with monsters (I BELIVE) was quite simple, since every check was in a 2D perspective (on original doom you couldn't be on the top of monsters because you were going to colide with their xy position), and if the monsters know where he's in the block map and also the objects on it, you'll save alot of cpu time...

Actually, that sounds how doom Works, if you noclip, the monsters are going to your direction, the hit the wall, go to a random direction for some seconds and go back to the initial state.
Uh, that's primitive D:

but it does the job for many monsters like "zombies"

EDIT OFF:
Nice talk about PathFinding in Starcraft 1 (since it was a 90's game, it's just nice to see how things took so long for "good" pathfinding

[Rachael]

Don't quote me on this, but I believe that is one of the things BLOCKMAP was used for. Remember, checking to see if your bullet hits the wall is the same performance hit. It was relatively fast with fewer lines to check.

[Kinsie]

The fascinating part about Doom's pathfinding isn't how it worked, but the code's history - it's appeared in almost every Id game, starting in Pascal in Catacomb and continuing until at least Doom 3!

[randi]

how did Carmak make it work fast enough. Collision checking isn't the most performant task to do... Or do they only check it once in a few seconds?

The blockmap is used to restrict collision detection to only a local area instead of across the entire map. And path checking is extremely basic: It doesn't check a path at all. The object is moved to a new position and checked for collision. If the new position puts it on top of something, the move doesn't happen. If the new position is clear, then the move happens. If an object is moving fast enough, it can completely ignore obstacles in its path and travel right through them.

[Hellser]

I was going to post in this thread originally that Doom's only form of 'pathfinding' is to follow the player / surround the player's actor. What Randi said makes sense too.

[Arctangent]

It's notable that going too fast can also impact a monster's ability to go up or down stairs. After all, a monster by default can only go up or down height changes that are 24 units at most, but the fact that they can only move a set distance each step means their only option is to make a move that would cause them to ascend or descend more than 24 units, causing the move to fail. This is especially noticeable with pinkies and normal-sized stairs: due to the combination of their "high" speed and relatively large radius, they'll often be unable to ascend stairs by going up them straight due to the fact that they end up with the tip of their hitbox in a stair step that's 32 or so units higher than their current z position - and since actors can't be below or above a sector, the only logical solution to this is to try to put them at that stair step's height, but whoops, that makes their move attempt to move them up higher than 24 units, and therefore it's invalid.

Going down stairs is significantly less difficult in such situations, actually because of the same reason - since the edge of the pinky's hitbox will let it "hang" on a stair step that isn't more than 24 units lower than its current position, it doesn't matter if its center would otherwise try to move onto a step that is actually that much lower. The actual actor isn't physically trying to move down more than 24 units, therefore the move is perfectly valid.

[Matt]

So that's why having a zero-speed monster that propels itself forward by alternating A_Chase and A_Recoil doesn't work...

(Kinda relatedly: one of the things that bothers me about Doom monster movement is how you have these extremely abrupt changes in movement direction without any kind of momentum. Makes them way harder to hit with a precision weapon than they ought to be and it just looks like ass. Anyone got a good way around that that has a minimum chance of screwing with something else?)

[Graf Zahl]

Why would you screw with the one thing that makes Doom so great to play? Aside from that, no. You'd have to script a completely new movement function once that is possible. The current code is just for the type of movement that's present today.

[NeuralStunner]

Also of note: If it encounters a door it can open or lift it can lower, it will do so and wait until it can pass. There are some great old bugs related to this.

So that's why having a zero-speed monster that propels itself forward by alternating A_Chase and A_Recoil doesn't work...

Partly because A_Recoil is a horrific, antiquated method. (Okay, that really has nothing to do with why it doesn't work. But it's still a horrific, antiquated method.)

Why would you screw with the one thing that makes Doom so great to play?

This is the guy who made Hideous Destructor. It's kind of in the job description.

[kodi]

So that's why having a zero-speed monster that propels itself forward by alternating A_Chase and A_Recoil doesn't work...

It works, but it doesn't handle corners that well without even more checks.
This one chases normally when out of LOS for the sake of simplicity though.

Edit: and here's the decorate:

Code: Select all

actor stormtrooper: zombieman replaces zombieman 
{
	Health 100
	Radius 20
	Height 56
	Speed 5
	painchance 255
	
	
var int user_walkframe;
var int User_make_aimshot;
var int user_make_rageshot;
var int user_chargemultiplier;
var float User_TargetDist;
var float user_maxrange;
var float user_enraged;
	states
	{
		Spawn:
			POSS AB 10 A_Look
			TNT1 A 0 A_setuservar("user_walkframe",0)
			TNT1 A 0 A_setuservar("user_make_aimshot",0)
			TNT1 A 0 A_setuservar("user_chargemultiplier",1)
			//TNT1 A 0 A_setuservar("user_enraged",0)
			Loop

		See:
			TNT1 A 0 A_setuservar("user_make_aimshot",0)
			TNT1 A 0 A_SetuserVar("user_walkframe",0)
			TNT1 A 0 A_JumpIf(user_enraged!=0,"SeeRed")
			TNT1 A 0 A_Chase("AimedShot", "AimedShot", CHF_DONTTURN|CHF_NODIRECTIONTURN|CHF_DONTMOVE)
			POSS ABCDEFGHIJKLMNOPPQ 1
			{
				A_SetuserVar("user_TargetDist",getdistance(1,AAPTR_TARGET));
				A_SetuserVar("user_walkframe",user_walkframe+1);	
				if(A_JumpIfTargetInLos("null",0))//"null" here is irrellevant since  you can't jump out of an if statement anyway
				{
					A_FaceTarget(10.0); //turns smoothly
					A_SetUserVar("User_TargetDist",getdistance(1,AAPTR_TARGET));
					
					if (User_TargetDist > 250.0)
					{
						A_setuservar("user_make_aimshot",1);
					}
					
					if(frandom(0.0,2.0)>1.9)
					{
						A_custommissile("stormshot",80.0,0,frandom(-10.0,10.0),CMF_OFFSETPITCH,frandom(-10.0,10.0));
						A_PlaySound("weapons/blaster1", CHAN_WEAPON);
					}

					if (User_TargetDist <= 250.0)
					{
						A_setuservar("user_chargemultiplier",-1);
					}
					if(User_TargetDist > 500.0 || user_chargemultiplier==-1)
					{
						A_ChangeVelocity(Cos(angle) * (speed*user_chargemultiplier), Sin(angle) * (speed*user_chargemultiplier), velz, CVF_REPLACE);//moves towards player
					}
				}
				else
				{
					A_chase("",""); //moves like a normal doom monster when player not in LOS
				}
				
			}
			TNT1 A 0 A_JumpIf(user_make_aimshot !=0,"AimedSHot")
			Loop
			
		AimedShot:
			TNT1 A 0 A_JumpIf(abs(GetAngle(1))>20.0,"see")
			TNT1 A 0 A_FaceTarget(20.0,20.0)
			TNT1 A 0 A_setuservar("user_chargemultiplier",1)
			POSS A 1 A_settics(random(10,30))
			POSS A 0 A_PlaySound("weapons/blaster1", CHAN_WEAPON)
			POSS A 0 A_custommissile("StormShot2",80.0,0,frandom(-2.0,2.0),CMF_AIMDIRECTION |CMF_OFFSETPITCH,frandom(-2.0,2.0))
			TNT1 A 0 A_Jumpif(GetDistance(1,AAPTR_TARGET)<250.0,"see")
			loop
			
		SeeRed:
			TNT1 A 0 A_SetuserVar("user_walkframe",0)
			TNT1 A 0 A_setuservar("user_make_rageshot",0)
			TNT1 A 0 A_Chase("RageShot", "RageShot", CHF_DONTTURN|CHF_NODIRECTIONTURN|CHF_DONTMOVE)
			TNT1 A 0 A_PrintBold("Waaagh!")
			POSS ABCDEFGHIJKLMNOPPQ 1 Light("blasterimpact")
			{
				A_SetuserVar("user_TargetDist",getdistance(1,AAPTR_TARGET));
				A_SetuserVar("user_walkframe",user_walkframe+1);	
				if(A_JumpIfTargetInLos("null",0))//"null" here is irrellevant since  you can't jump out of an if statement anyway
				{
					A_FaceTarget(12.0); //turns smoothly
					A_SetUserVar("User_TargetDist",getdistance(1,AAPTR_TARGET));
					
					if (User_TargetDist < 500.0)
					{
						A_setuservar("user_make_rageshot",1);
					}
					
					if(frandom(0.0,2.0)>1.9)
					{
						A_custommissile("stormshot",80.0,0,frandom(-10.0,10.0),CMF_OFFSETPITCH,frandom(-10.0,10.0));
						A_PlaySound("weapons/blaster1", CHAN_WEAPON);
					}

					if(User_TargetDist > 250.0 || user_chargemultiplier==-1)
					{
						A_ChangeVelocity(Cos(angle) * (speed*user_chargemultiplier), Sin(angle) * (speed*user_chargemultiplier), velz, CVF_REPLACE);//moves towards player
					}
				}
				else
				{
					A_chase("",""); //moves like a normal doom monster when player not in LOS
				}
				
			}
			TNT1 A 0 A_JumpIf(user_make_rageshot !=0,"rageSHot")
			Loop
			
		RageShot:
			TNT1 A 0 A_JumpIf(abs(GetAngle(1))>20.0,"SeeRed")
			TNT1 A 0 A_FaceTarget(20.0,20.0)
			TNT1 A 0 A_setuservar("user_chargemultiplier",1)
			POSS A 1 Light("blasterimpact") A_settics(random(3,10)) 
			POSS A 0 A_PlaySound("weapons/blaster1", CHAN_WEAPON)
			POSS A 0 A_custommissile("StormShot3",80.0,0,frandom(-8.0,8.0),CMF_AIMDIRECTION |CMF_OFFSETPITCH,frandom(-8.0,8.0))
			TNT1 A 0 A_Jumpif(GetDistance(1,AAPTR_TARGET)>500.0,"SeeRed")
			loop
	Pain:
	TNT1 A 0 A_SetUserVar(user_enraged,1)
	TNT1 A 0 A_ChangeFlag("nopain", 1)
	goto see
	
	death: 
	TNT1 A 0
	stop
			
	xdeath: 
	TNT1 A 0
	stop
	
	}

}

It's inefficient, crude, experimental etc but has some fun concepts. The monster stands still and shoots accurately when at a high range rather than charge in and put itself in harms way, when you get close it backpedals away from you while firing, and it can get pissed off and go into berserker mode where it's fearless and charges you while spraying wildly.