Game Career Guide is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Get the latest Education e-news
 
  • The AI Of DOOM (1993)

    [06.21.22]
    - Tommy Thompson

  • Sight and Movement

    Now that we know the overall core logic for the enemies in DOOM, next up I want to focus on the SEE state. Which is when an enemy has found a target and then locks in on it. Chasing them around the map and then attacking when they can.

    As mentioned already, 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. There are some extra checks here as to whether the target is shootable, meaning they don't become skittish and hunt down anything that makes a noise. But also, there's... actually, no I'll tell you the other secret in a minute.
    Once the target is established, it moves into the main SEE state from the diagram. This corresponds to a chase function in the codebase, whereby the enemy will begin the hunt and if it's within range for a melee or ranged attack, it will take a shot.

    But wait, let's back up: 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 and quite often there are dozens of enemies running sight checks at once. 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.

    DOOM enemies technically have 180 degrees of vision and have no long-distance vision cut off. If the view between yourself and the enemy is not obscured, they will see you. Plus, height differential doesn't matter. That's because DOOM is a 3D render projected from a two-dimensional floor plan. The line of sight is parallel with the floor, hence you'll notice if you're above or below an enemy, if it's facing you then it will always notice you even if sometimes you can't see them in return.

    MapSectors.png

    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? The trick here is that DOOM's map is broken up into chunks using what is known as sectors, and those sectors are organised courtesy of a binary space paritioning algorithm or BSP. A BSP allows you to organise objects such that they retain spatial information. This is used so that the renderer always knows what parts of the game map it needs to draw, 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, given it saves on performance by ensuring it doesn't try to render the entire level - an issue that modern game engines have now rectified. Now from this, some further optimisations can be made to the AI as well.

    The map being broken up into sectors means that, much like the BSP, you can record information about whether it's possible for one character to see another based on their location. Visibility between sectors is actually precomputed in DOOM courtesy of what is known as the REJECT table. This tells us that if a character is in a given sector, whether they could even potentially see another character in another sector. Like in this example here, it's practically impossible for the character in sector A to see anyone in sectors C and D, but it could in theory see you in sector B. So when they're looking for the player, the game quickly does a check against the REJECT table to see whether it should even bother running the sight test.

    RejectTable-1024x576.png

    Once the player has been seen and a target is acquired, then the monster will start moving toward you. Technically, there isn't any actual pathfinding in DOOM. If there is a direct path towards the player, then it simply moves towards you. If there isn't, then it tries to head in that direction and will bounce off walls changing direction as it goes. In the event there's no possible direct path to you, then it will move around randomly instead. In order to manage all of the enemies (and the player) colliding with the level, all of the collision data is precomputed as well. The BLOCKMAP breaks up the map of the level into a grid that allows it to quickly check if that space is navigable.

    Sound

    So yeah, if an enemy sees you it's going to kick-off and the situation will get a little... tense. But what about when you pop into a room, fire off the shotgun and everything roars in anger at you.

    Well, here's the funny thing. Yes, the enemies in DOOM can hear you, but not in the way you'd think. I mean, one could argue that the enemies actually SEE sound. I mean it literally sets a sound target in the Look() function after all.

    Flood fill of E1M1 for sound propagation. Blocked only by doors (from Sanglard's 'Game Engine Black Book: DOOM')Flood fill of E1M1 for sound propagation. Blocked only by doors (from Sanglard's 'Game Engine Black Book: DOOM')

    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. DOOM has a very simple sound propagation, whereby a flood fill algorithm spreads the sound around the map provided there are no blockers that prevent the sound from dissipating further. A good example of this is in (E2M4) Deimos Lab, given the entrance opens out to a long corridor at the side. As soon as you finish fighting the imps and shotgun soldiers at the entrance, you'll soon be attacked by imps who heard all the commotion hundreds of meters away, given the gunfire propagated through the space.

    Doors between level chunks will block the sound from travelling further, but also level designers could place blockers where they wanted to make sure the sound didn't travel into areas where an ambush was being prepared (more on that in a minute).

Comments

comments powered by Disqus