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
- 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).
- 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).