Shooting Through Things (2003)

Shooting Through Things

Introduction

It has happened to every Doom player. A monster is getting too close for confort. You shoot at it, and miss. If you are unlucky, the monster kills you. But you were so sure that you were pointing right into the monster, that so close as you were you couldn't have missed. Perhaps it was the chaingun playing up, shooting all the bullets off to one side. Perhaps the game was written by a bunch of losers who failed their high-school geometry. Or perhaps, in the heat of the moment, you really did miss; nobody's perfect.

Well I have good news. You can blame your tools. It is all someone else's fault. The engine really does get it wrong. In fact, it does it all the time, and we have been so polite about assuming it must have been our aim that was off, when in fact it really has been Doom's fault all along.

No… please. Not the Barrel!

Ok, so may I assume that everyone here has played Barrel, by Cameron Newham? If anyone has not, now would be a good time to go and do so. Partly because it's an excellent level, full of cunning tricks (particularly with barrels, hence the name) and some tough fights. Barrel is one of the classic early Doom PWADs (released May 1994), and while it shows its age in the architecture and texturing, it has got some great puzzles and fights (it is a puzzle level though, so is probably not to everyone's taste). More importantly, it is the first level where I experienced this bug, and is the only level I know where it is hard to avoid noticing this bug.

Let's set the scene. You have only the pistol, and not much ammo for it, and the chainsaw. You are looking down into a dark room, with a ramp in front of you reaching halfway across the room, towards an alcove at ground level on the far side containing a keycard. There are spectres either side of the ramp. You advance out along the ramp, and it lowers into the room. The corners of the room are rounded off, so you're surounded with no defensible spot to fight from — except the far alcove. So you dive into the far alcove, turn and start chainsawing the spectres that come at you. And you get slaughtered.

Now the chainsaw can be a little tricksy at times, and certainly in those days I was not a particularly good player. But this fight seemed particularly hard; the chainsaw just wouldn't stick, and desite the narrowness of the opening it seemed to be missing the spectres a lot. After a few tries I got through with an acceptable, if high, loss of health, played on and forgot about it.

A few years later I was writing Doom reviews for my site, and decided to replay the level. And I got hammered by this fight again. This time, I was convinced that it was not just me having a bad day; there was really something about this room that was messing me up. Loading the level in an editor revealed no trickery, however, just a simple room. So I wrote it off again.

Armchair Demonstration

Now, I'm sure there are a few armchair critics reading this article who would rather see the bug demonstrated for them. Either because you are too lazy to load up the level, or because you were put off by the description as a puzzle level. The more shrewd critics will be thinking that I'm talking about a PWAD, and an unusual one at that — Barrel is a puzzle level after all, and just because the chainsaw room trick was beyond my wit does not mean that it isn't really all a trick somehow.

Anyway, here's another demonstration. It's not even by me, so you can't blame it on my poor Doom skills. And it's at one of the original levels, so you cannot blame it on a PWAD author. Try this demo of Deepest Reaches (TNT: Evilution MAP16). The simple summary is: the player pins in a sergeant, and shoots at him — but the shots pass through the sergeant and hit the wall behind.

The Blockmap

So, I think there is something wrong in the code for line attacks. By line attack, I mean any attack that Doom handles as an instantaneous hit-first-object-in-a-straight-line attack, including bullets and BFG traces (as opposed to projectile attacks like rockets, which spawn a slow-moving object that inflicts damage by contact or explosion) Note that the chainsaw — like all biting, clawing and other melee attacks in Doom — is implemented as a very short-range line attack. It seem to be missing targets that should be hit. There is something rotten in the line-to-thing collision detection code.

Time to get technical. Collision detection in Doom is handled with the aid of a structure called the blockmap. This is one of the simplest of the data structures in a WAD: it breaks the level up into a grid of 128 by 128 squares (called blockmap blocks, or just blocks). The BLOCKMAP lump lists the linedefs (walls etc) present in each block. 128x128 is the size of 4 teleport pads, which is an arbitrary but convenient size for collision detection. During the game, Doom keeps not only this list of lines for each block, but also a list of all the things in the level currently stood in that block.

Suppose Doom wants to test whether the player has collided with a solid object. Doom first makes a list of all the blockmap blocks that the player overlaps with (usually only one, but could be as many as four if the player is standing right on the corner of a block). Doom then goes through the list of objects contained in each block, and tests each of them to see if the player is touching it. By using the blockmap, Doom knows that it only has to test those objects that are contained in nearby blocks: this is clearly much faster than testing against every object in the level.

Hawk-eyed readers might have spotted a mistake in this algorithm, however. The player may overlap several blocks, and so Doom checks all of them; but other objects can also overlap into several blocks. Suppose the player is entirely contained in one block, but a mancubi is standing just over the edge in the next block; the mancubi will overlap both blocks, and so we must check the player against both. Doom compensates for this by adding a fudge factor to the radius of the object when working out the list of blocks to check. This fudge factor is called MAXRADIUS, and is set to 64 units (for comparison, this is the width of a teleport pad). The idea is that MAXRADIUS should be greater than the radius of any thing in the game, so that if we add MAXRADIUS to the radius of a thing, we should have an outside bound for the area containing objects that might be obstructing it[1].

Now let us consider the other case: testing what a line (a shotgun pellet, for instance) collides with. In this case, Doom works out a list of all the blockmap blocks that the line crosses[2], and steps through them (in order) testing all the objects in each block until it finds one that is hit by the line. Once again, Doom saves itself a lot of work by only testing objects that are in blockmap blocks which the line passes through.

Again we have the problem of obstructing objects — let's call them targets — standing on the edge of blocks. Specifically, a target standing on the edge of a block that is not crossed by the line, but overlapping a block that is crossed by the line. Doom needs to check whether the line hits this target, even though it is not standing in a crossed block. We need an equivalent to the MAXRADIUS hack, but lines do not have a radius; the closest equivalent would be to imagine drawing a wide line, like drawing with a wide brush stroke in Paintshop Pro. But this would be a lot more work than drawing a thin line, and much less elegant code. Whatever the reason, the Doom programmers ignored the problem: Doom does not allow for objects overlapping several blocks in the line collision code.

Since we have a real example, let's see how this works in practice. Consider the scene from that demo in Deepest Reaches, with the player and sergeant standing toe-to-toe. The bottom-left of the blockmap in Deepest Reaches is at (-2666,-2440), the sergeant is standing at (-608,1272), and the player is standing at (-645,1274). We want to work out where they are relative to the blockmap, so we subtract the blockmap origin from the coordinates of each object and divide by 128 (the blockmap block size). Actually, we are not so much interested in which blockmap cell they are in, as in where they are inside that blockmap cell: we want to know the remainder of the division.

Sergeant

Block (16,29), offset (10,0)

Player

Block (15,29), offset (101,2)

So they are in adjacent blocks, which is reasonable since they are right next to each other. More importantly, the sergeant is right on the edge of his block (offset (10,0), so he is dead on the south edge of the block). The player is also near the edge of a block, and will be shooting parallel to that edge. If the player shoots straight east, his shot will cross into block (16,29) and hit the sergeant; if the player shoots just a little to the south/right then the shot will go into block (16,28) instead, and because it does not go into (16,29), it will miss the sergeant. And if you look at the screenshot earlier, you will see that the player is angled a little to the south.

See the diagram to the right. The player and sergeant are both on the east-west blockmap line that divides (15,29) and (16,29) from (15,28) and (16,28). If the player hits the part of the sergeant above the line, Doom will register a hit. If the player hits the part of the below the line, it will be a miss. Effectively the player has a 50:50 chance of missing with any one shot. Using the shotgun, the natural spread of the weapon improves these odds a little, but there is still a good chance of most or all of the pellets falling below the line.

Here is an enlarged diagram of our other example, the Barrel red-key room. Again the player is green, the monster is red, and this time I have shown the line of the player's chainsaw attack. I have added the walls in black, and the blockmap cell borders are drawn in blue. The attack passes into the cell to the right of the player, but the demon is in the cell below that one, so the attack misses.

Other Details

This bug is more important when the player and target are close together. At long distances it is still there, but the natural spread of the shotgun, and random element in the chaingun and pistol, will spread the shots more, so there is less chance of consistently missing on one side. At long ranges, some pellets will miss but not all; at close ranges, it is all or nothing.

Monsters are affected by this bug as well as players. The Deepest Reaches example shows that it tends to affect players more. This is not for any reason in the code, but for a human reason: players make consistent mistakes. If you miss a monster by aiming a fraction to the right, you will tend to fire in the same place next shot, if you believe it will hit. The monsters aim poorly too, but this is simulated by a random number generator; each shot for the monster starts out being perfect, but is disturbed by a random offset, a different random offset each time. So the monster will make a different aiming error with each shot, and so won't consistently miss on the same side.

Finally, I should note that the original node builder, idbsp, has another blockmap quirk. Instead of setting the origin for the blockmap at the westmost and southmost coordinates in the level, it adds an offset of (-8,-8) to this, effectively adding a margin of 8 units around the level. This means that the blockmap origin for the original levels is offset by 8 units south and west. To the best of my knowledge, no modern node builder adds this safety margin, and it is not needed. I just mention it so people examining the original levels will know why the blockmap is strangely aligned.

Applications

Before we leave this subject, let us see whether this bug can be put to any positive use. Doom is, after all, one piece of software where the bugs really are features — at least, everyone seems to treat them that way. So can we make use of this bug, as Barrel did? Well, that question answers itself, but what uses?

Suppose we want to design a level that makes it easy for the player to miss their shots. We have said that the bug is more effective when the player is facing north, south, east or west, so we put the player in a network of passages aligned with the grid. Make sure all the passages are arranged such they they are either along the bottom of, or up the left side of, the grid when set to 128x128. Then, add a dummy sector off the bottom-left corner of the map, with its bottom-left corner at (-96,-96); this fixes the origin of the blockmap. You can end up with every passage in the level split in half by the blockmap. When the player shoots, if they aim to one side when the monster is standing to the other, they will miss, even if the shot ought to hit. Then I suggest you publish and be damned. Actually, I would take out life insurance and change your address, because there will be a lot of Doom players out there who will hate you forever.

Any other uses for this bug? Well, it has been suggested that players in deathmatch games could learn where the blockmap lines are in a level, and plan routes and places to stand such that they are on the edge of blockmap blocks. But play tends to be more frantic in deathmatch, so I suspect players spend less time shooting in line with the axes than in single play, where the monsters come on much slower. The projectile weapons are not affected by this bug, and BFG traces are so numerous and well spread that even partial protection is unlikely to save a player. So while it would offer a bit of extra protection, I doubt it is as effective as just keeping on the move.

And let us not forget the main use for this bug: you can blame Carmack when you miss a vital shot and get wasted! :-)

One interesting question remains: did Cameron Newham intentionally use the blockmap bug in Barrel? This level makes use of a lot of clever Doom tricks, such as barrels teleporting and triggering linedefs. But it seems too early in Doom's history for such an obscure bug to be actively exploited. That's not to say the level isn't designed for it, though; it's hard not to notice the bug playing the level, so he would certainly have noticed it in testing, and without being able to explain it he would have left it as it was and calibrated the difficulty accordingly. I think we can say he used the bug, but probably without understanding it.

Source and Credits

Thanks to Bahdko for the very simple demo illustrating this at an original level. And thanks to Cameron Newham for the excellent Barrel, of course.

Research and write-up by Colin Phipps, 2003/08/17.

Footnotes

1. In practice, several things have larger radius than MAXRADIUS (spiderdemons and arachnotrons, I believe). id chose not to correct this, probably because increasing MAXRADIUS causes Doom to do more work in collision detection (although the work is so insignificant compared to the time spent on other tasks like rendering and line-of-sight calculations, it appears a strange choice of optimisation to me). Incidentally, this may explain why the physics do not always feel right when the player collides with a spiderdemon: MAXRADIUS being smaller than the radius of spiderdemons means that the collision detection will let objects closer to the monster than it should in some cases (although the sprite not taking up the full area of the object in the game may be a better explanation for the "feel" being wrong).
2. I am simplifying here: Doom doesn't actually make a list first, it steps through them in order using a simple stepping algorithm (similar to the classic Bresenham line rastering algorithm for any computer graphics types reading this).

from Hacker News https://ift.tt/1qOm4HI