DOOM Collision Detection

In the DUNSHIRE DOOM launch announcement, I mentioned collision detection was an obstacle every time I’ve tried to work on 3D graphics. This time - whether it was from helpful links and blogs, reading the DOOM source code, or just sheer luck and experience - I actually managed to build a working collision detection system. I’d like to talk about what I learned along the way and also point out interesting differences in DUNSHIRE DOOM compared to the original DOOM.

A little warning: this post is dense with details. It was challenging for me to organize my thoughts and present them in a coherent way. The process of building and writing about collision detection has certainly been educational for me. I hope the write up is fun or educational for you.

Terminology

Before getting into the details, it’s important to understand some common DOOM map and collision detection terms.

At a high level, DOOM maps are a collection of 2D polygons called sectors. A sector has a floor height and ceiling height and the walls of the sector are defined by linedefs. A linedef can be single sided (a solid wall) or double sided when it joins two sectors. For rendering, Sectors also have a light level and linedefs also have a sidedef with texture information but these values do not effect collision detection. For collision detection, we need to know the start and end of a line, whether it is single sided or double sided, and if it’s double sided, we need to know the difference between floor and ceiling height of the two sectors it joins. If the ceiling of the sector we are entering is too low, we cannot enter. Similarly, we cannot enter if the floor is too high.

When I talk about collision detection, I’ve actually got two things in mind: detection and response. Collision detection is determining when and where objects collide and collision response is deciding how the objects respond. In the code, these things are generally separate. There is a block of code for detecting collisions and several different blocks for responding to the collisions. For example, a bullet hitting a wall is different from a player hitting a wall or a bullet hitting a player. This is collision response, detection is just figuring out if and where those things collide.

One more thing. For performance, collision detection happens in two phases: broad and narrow. In the broad phase, we are quickly finding objects that are candidates for collision or, to put it another way, we are eliminating objects we know cannot collide. It can be expensive to figure out if the objects actually collide so we want to eliminate as many candidates as possible in the broad phase. Once we have the candidate list, we run a the narrow phase with detailed calculations to determine if the objects collide and where.

A Journey in Collision Detection

My implementation was a journey. I changed approaches as I went and learned. This section tries to capture the key points in that journey. The journey has been slow because I’ve mostly been working alone. This is one of those times where, working with a team or at least having a peer close by to bounce around ideas can save a bunch of time. The first chapter of the book, Team Geek, has several great examples of this idea. Software development is best done with a team. Without a team, it’s easy to get stuck or go down the wrong path and waste time.

My journey with collision detection started without broad phase detection. I knew this would never scale for large maps but I wanted to start simple and get something working. I started by testing if the player (represented by a circle) hit any linedefs in the map. A little background: DOOM used “discrete” collision detection. Rather than move the player their whole velocity, DOOM moved the player a small step multiple times and checked for collisions at each step. This works for low velocity objects but small steps for high velocity objects means either lots of intermediate checks or large steps that may miss collisions. For my own interest, I wanted to try out continuous collision detection so I found a nice little article for circle-line collisions. Why circle-line? The size of a DOOM object is determined by its radius so representing objects as circles seemed like a good place to start. It took some debugging to get the implementation right but it worked well enough.

I extended the code a little bit to also test circle-circle collisions to test collisions between the player and other objects.

Next step was to add in broad phase collision detection. DOOM used a 2D grid called a block map for broad phase collision detection. Each cell in the block map contains the objects and linedefs that touch the cell. When a player moves, we find the cells they are touching and run detailed tests on only those objects. I loaded up the DOOM block map and used it and, for slow moving objects like a player or monster where we cross one or two blocks, it seemed to work. There were little problems here and there because objects on the edge of a block would be touching multiple blocks but I knew DOOM had some quirks with collisions and I figured I could clean it up later somehow. For bullets though, it got more complicated. Bullets could cross ten or twenty blocks and how do we find those blocks? With a little googling, I came across the Amanatides-Woo algorithm for fast voxel traces with an assist from stackoverflow on initializing the values.

Although this worked, I wasn’t happy with the implementation. I ended up with three ways of scanning the block map: one for movement (moving object with radius), one for bullets (line trace), and one I haven’t mentioned which was for explosions (non-moving point with radius). Can’t we just have one that works for everything? I started to think and realized we could do this using parameters for radius, movement, and starting position:

• Finding cells for a bullet would be scanBlockMap(point, movement, radius=0)
• Finding cells for a player or monster would be scanBlockMap(point, movement, radius)
• Finding cells for an explosion would be scanBlockMap(point, movement=0, radius=0).

Getting this working took several evenings and when it was done, it felt like a hack.

In parallel to implementing and debugging collisions, I was playing around with the renderer and reading about Binary Space Partitioning (BSP). BSP was key in making DOOM possible on early 1990’s hardware although my understanding is that it is not used much in modern games. I won’t try to explain BSP here because this post is long already and there are great articles out there like this one or a video explanations. At a high level, BSP is a binary tree and walking the tree tells you what objects are near you. As I learned more about BSPs though, I kept reading that it could be used for collision detection and I wanted to try that out.

BSP Collision Detection

Using BSP for collision detection was simple and clean once I got comfortable with it. We take a 2D point and traverse the BSP tree to find the sector that contains the point. Once we know the sector, we can find the walls or objects nearby. It’s a little more complicated in practice because the partition lines can divide a wall such that part of a wall is on one side and part is on the other (these are called segs in DOOM). Similarly sectors are divided up by the partition lines into subsectors. These subdivisions actually help because a large sector with lots of monsters or walls will be split into small subsectors and we only need to check for collisions with monsters and walls in the same subsector as the player.

Traversing the tree gets a little more complicated when tracing a bullet (ray) or a moving object but not much more complicated:

• Tracing a point. We take a point and visit either the left or right child based on which side of the partition line the point is on. This is useful to figure out what sector a monster is in to figure out the z position (DOOM used the z-axis for vertical position) and the light level for rendering.
• Tracing a ray. To trace a ray in the BSP, we check what side of the partition the start and end point are on. If the start and end are on opposite sides of the partition, it means the ray crosses the partition line so we recurse both child nodes. If the start and end are on the same side, we recurse only one side, just like we do with a point. Bullets, in DOOM, behave like a ray. Bullet traces take the location of the shooter as the start point and cast a ray 2048 units away in the direction the shooter is facing.
• Tracing a moving object. An object, like a rocket or monster, has a velocity and radius. We treat the object like a ray formed by taking the current position as a starting point and adding velocity and radius to get the end point. Because partition lines extend infinitely, we mostly do not need to worry about the width of the object. I say mostly because the object could start out already sitting on a partition line and if it is, we will need to check both sides.

Tree traversal code is straightforward. The actual code is not as short as the snippet below but it’s not far from it.

function visitNode(node: TreeNode) {
    if (node.isLeaf) {
        if (boundsOverlap(node, point, radius)) {
            processNode(node);
        }
        return;
    }

    // is object sitting on the partition line? If yes, we check both sides
    const traceOnLine = isTouchingLine(node.partitionLine, point, radius);

    // Visit left or right child depending on which side of the partition line the point is
    const side = traceOnLine ? -1 : Math.sign(signedLineDistance(node.partitionLine, point));
    visitNode(side <= 0 ? node.left : node.right);

    // Visit opposite side if start and end are on different sides of the partition line
    const endSide = Math.sign(signedLineDistance(node.partitionLine, endPoint));
    if (traceOnLine || endSide !== side) {
        visitNode(side <= 0 ? node.right : node.left);
    }
}

There also one more suble thing going on in the code above. Partition lines continue infinitely but sectors (and subsectors) do not. Just because you are on one side of a partition, does not necessarily mean you are inside the subsector. Most of the time this doesn’t matter but in E1M7, Imp-43 and Shotgunner-41 are touching the wall of the sector and the neightbouring sector is a lift. Because the trace determins the monsters are in both sectors then they block the lift from moving. Hopefully the diagram below helps clarify what is going on.

To get around this, we check the bounds of the object against the bounds of the subsector. This is why we check boundsOverlap() before processNode() in the sample code above. DUNSHIRE DOOM uses axis aligned bounding boxes (AABB) for these checks so there may still be some false positives because subsectors are not necessarily rectangles but I haven’t noticed any problems yet.

Narrow Phase Refinements

I mentioned above that my initial approach for narrow phase collision detection was circle-line and circle-circle collision tests. Over time, and as I filled in more implementation and did more testing, it became obvious this was the wrong choice. DOOM object size is indeed controlled by a radius property however the radius actually defines the size of the bounding box. If we use radius only, the player will fit through areas they shouldn’t or squeeze past objects that should block their way. You can experience this in E1M1 by trying to walk through a barrel in the starting room. As you walk into the barrel, you’ll feel yourself blocked like you are inside a square box pushing against another square box. As a result, I threw away the circle-line and circle-circle tests and went with AABB tests which wasn’t too hard.

The narrow phase itself performs collision tests against all objects and segs in the subsector (recall a seg is a part of a wall on one side of a partition line). We also test for a collision against the sector floor and ceiling. The hits are then sorted and passed on to collision response. One interesting thing about these tests is that we ignore a collision if the objects are moving apart. This mostly much prevents monsters from getting stuck together and it also allows the player move through solid walls when they move from from outside the map to the inside. I haven’t yet found problems with this, and it helps avoid bugs like the player start spot being stuck to the wall in DOOM II’s MAP03.

As an aside, collision detection does allocate lots of small objects. Someday, I’ll put a test harness in place and see if I can squeeze some performance out of this using a pool of objects.

Collision Response

DUNSHIRE DOOM collision response code is pretty messy in my opinion (example) but I’m still learning. I like to think that someday I’ll look back on this with good ideas for how to clean it up. The narrow phase collision detection tells us when we hit a wall, object, or floor/ceiling therefore most collision response is split into those three pieces. Some functions, like line of sight check only check for walls while functions like radius damage only check for objects.

In general, the collision response code didn’t change much throughout the iterations of collision detection. When a player hits a wall or object they slide along by projecting the direction of movement against the object they hit. For walls, this means projecting the velocity along the wall. For objects, it means projecting along either the x or y axis because all objects are AABBs. There were still a few gotcha though:

(1) If we collide the walls in the wrong order (a farther wall before a closer wall) then the collision response will be wrong. That was solved by sorting collisions in collision detection so nearest happens first.

(2) Horizontal and vertical walls are a special case because objects are axis aligned, a vertical wall can hit the object at the same time as a horizontal wall. We prioritize which wall to hit first based on which wall overlaps with the object. Diagonal walls do not have this problem because they always hit the object on the object corner.

(3) If we collide with a corner then we have two collisions. If we merely project the velocity along the first wall and then along the second we may walk through the first wall. To work around this, we track which walls have been hit during this collision check and zero the velocity if we hit the same wall twice.

DUNSHIRE DOOM and DOOM Differences

DUNSHIRE DOOM collisions are different from DOOM in subtle ways. The differences come from two things: (1) using BSP instead of blockmap for broad phase and (2) using continuous collision detection instead of discrete. If I were aiming for a 100% compatible port, I’d want to fix this but this project was about learning and I have no plans to improve compatibility at the moment (although I’m happy to look at a PR). As a result of the implementation, you can occasionally find maps that may not work, especially if they are taking advantage of blockmap bugs. Some speed running tricks won’t work either but collision detection is only part of that story.

Here are a few specific differences I’ve noticed:

• Walking under monsters: DUNSHIRE DOOM allows the player to walk under monsters. This has a big impact on rooms filled with cacodemons or lost souls. You may even call it a bug.
• Monsters on steps: Take DOOM II’s MAP24 as an example. If you drop into the nukage and go left into the cave with the BFG. The pinkies here are not able to climb the steps. I’ve improved the monsters on stairs checks before but something isn’t quite right yet.
• Platforming: DOOM II MAP12 has a tower with shotgunners to the right of the single player start and it is very hard to climb the steps in DUNSHIRE DOOM. I believe this is due to continuous collision checks but I have not confirmed.

Summary

This was a great learning experience for me and I’m happy with the result. There were so many times I was close to giving up because I would “fix” something and a bunch of other things would break and I couldn’t understand why. Once I understood and used the BSP, the code became simpler. Broad phase collision detection (traversing the BSP tree) is probably about 100 lines and the narrow phase is another 150. It’s not a huge amount of code but it took quite a bit of effort and thought to get there. That is perhaps a fascinating part of software: all the approaches and debugging and failures that most people will never see.

The collision response code works but, like I said above, I hope to someday make it easier to read.

One final note, you may be wondering why I didn’t use an off the shelf library for all of this. Threlte (which I’m using for rendering) even includes support for a nifty physics engine called Rapier. Although I didn’t mention it above, I actually did start out using Rapier. I thought using a physics engine would enable interesting extensions to the game. I ran into several problems and I couldn’t figure out a way to make it fit. I set out to build a DOOM game, written in JS, that felt like the original where you could bring your own renderer (in SVG, ThreeJS, BabylonJS, or whatever). That approach meant that I would be passing Rapier data, declared in the renderer, down to the game logic which felt backward. I do have a few old development branches where I tried this but the player movement never felt right in my attempts. Stepping up on stairs was particularly hard. Lastly, and personally, I really wanted to stretch myself to get collision detection working. It has been years since I tried collision detection and DOOM is mainly 2D collisions with lines and boxes which are simpler concepts compared to 3D meshes and polygons. Mission accomplished on learning so next time I write a game, I would almost certainly start from a library.