TIL Infinite State Machines in Doom
POSTED ON:
TAGS: fsm videogames ai doom
Today I learned about The AI of DOOM (1993)
The AI itself #
The actual core logic of the enemies is a Finite State Machines: a simple but effective mechanism to state that a character executes a specific behaviour when in a given state, and what the conditions are that will force it to change.
The full diagram is shown here now, and there are some interesting quirks in how it all works, so let's discuss the high-level behaviour and then I will burrow down into individual topics.
It starts by spawning, but stays frozen until it SEE you.
the SPAWN state has the enemy standing around and waiting for something to trigger them. This can happen in one of two ways: either they see an enemy, or they hear them. In either case, it establishes a target for the NPC to head towards.
Then, when it SEEs you, it moves into attack mode of either MELEE/RANGE.
If you hurt it, it goes back to the SEE state and continues the cycle.
Monsters do not always go into the pain state when hurt. Instead, it is influenced by the pain state interrupt probability which in the codebase is referred to as pain chance.
Every time an enemy is hurt by a weapon, there is a probability check to decide whether the enemy will go into the PAIN state, thereby interrupting its movement and any attacks.
The number ranges from 0 to 256 and is configured for each enemy type. So in the case of the imp and shotgun guy, these are 200 and 170 respectively. Meaning that the imp, anytime it is hurt has a 79.3% chance of being put in the PAIN state, while the shotgun guy only has a 67.6% chance. But the trick is that each individual hit from a weapon counts towards this. So while a rocket counts as only one hit, while the shotgun technically has seven
DIE->RAISE is unique attribute because in the game, there's a creature known as the Arch-Vile, which can revive dead enemies in the DIE state.
there's a special case called XDIE, which is used when a monster is gibbed and turns into a pile of goop.
Those can't be revived.
(XDIE)... will only occur if the damage received at the time of death exceeds the remaining health of the monster, plus its original starting health.
for example, Imps start with 60 health points. If it's been shot already and is down to 10 health, then in order to be gibbed, it has to receive a minimum of 71 damage on the next attack. Given the lower starting health values of the likes of the zombieman and shotgun guy (who have 20 and 30 starting health respectively), it's relatively easy to gib them with an exploding barrel, the rocket launcher or even the berserk pack.
Meanwhile, enemies such as the Cacodemon or Hell Knight which have 400 and 500 health at start are practically impossible to gib. That said, you can gib pretty much any monster if you can telefrag them (i.e. by teleporting into them, given that does 10,000 damage). Such as in Perfect Hatred, the second mission of DOOM's Thy Flesh Consumed episode where you can telefrag the Cyberdemon given it only has a meagre 4000 health.
The data structure #
But the actual definition of each enemy in DOOM is actually achieved outside of the codebase. It contains:
- Their internal ID number in the game.
- The amount of health an imp starts with.
- Their movement speed.
- Probability of pain state interrupts
- Their radius and height
- The specific properties of the NPC.
In the case of imps, they are solid objects you can't walk through (MF_SOLID), they can be shot (MF_SHOOTABLE) and damaged and their death counts towards the total number of enemies in the level (MF_COUNTKILL).
How it SEEs and HEARS you #
how do the enemies see or hear you? This is actually a huge chunk of logic for DOOM given it's tied to how the map is designed. Plus, it's also one of the most interesting aspects of how the game is optimised.
In previous videos on games such as The Last of Us, Splinter Cell and Alien: Isolation, we talked about how vision cones are used for enemy vision. DOOM predates all that stuff, but also it's designed for early 90s PCs... Even if all the enemies are in the SPAWN state, then each of them is calling the Look() function in the codebase 35 times a second. So not only does it need to work effectively, it also needs to be optimised.
So how does it ensure that an enemy can see you within its field of view and also navigate towards you in a way that's cost effective?
... by only rendering the current sector and any connecting sectors according to the BSP. This optimisation was added by programmer John Carmack to cut down rendering costs,
When the player fires their weapon, it sets the player as a 'sound target' in the sector of the map that you're in. If an enemy is in a sector where a sound target is created, it will wake it up and hunt the sound target. But that would only work in one sector unless the sound could travel.
Infighting #
How on earth does that work? Well, it's actually quite simple: there's logic in the code that states in the event an NPC is attacked and hurt by another character, then it might assign that character as their new target. Even if it's not the player. Naturally, this means that the demons don't attack one another without cause. So you need to lure one enemy into the line of fire of another, and hope it accidentally causes some friendly fire.
There are some exceptions to this, given Barons and Hell Knights can't hurt each other with their attacks. Pain elementals technically can't get caught in infighting because they hurt other characters by spewing Lost Souls (which will then get targeted instead). And there's a specific edge case coded into the game to stop Arch-Vile's being attacked by other NPCs.
Related TILs
Tagged: fsm