The Sleepingwalking Sergeant of MAP02
Introduction
Last week I came across an
unusual bug in the original Doom. At Underhalls (Doom 2 MAP02), the second room
the player enters is a small stone room with a few computer panels and two
switches, one behind red bars. The other switch, the first the player hits in
the level, is guarded by a sergeant. This sergeant is completely blind before
he's woken up by a shot (hence I would say he's sleeping, but since he is
standing and walking in the manner of all Doom sprites before they are
awoken, I have to say sleepwalking). Although there are several possible
causes of blind monsters, this is the only instance of the particular bug I
will be describing which I know of.
The reason this isn't immediately obvious in play is that he is only blind, not deaf. Since there are two troopers in the central part of this room which the player has to pass first, they have usually fired a shot and woken him before they see him, and certainly before he sees them. However, if you quietly walk past the troopers (or, more patiently, draw them through the doorway and shoot them outside while the door is shut, so the sergeant cannot hear), then you can walk right up to the sergeant without waking him.
See this demo by Ledmeister for a demonstration of the bug.
I'll describe how I came across the bug briefly, because it doesn't relate
to the original engine at all. In MBF an optimisation was introduced in the
line of sight checking, which basically said that lines that don't enter the
bounding box of the line of sight being checked, can be ignored without going
through laborious geometry calculations. It was an obviously correct
optimisation, but for some reason it caused demos to go out of sync. This was
the first demo bug I squashed in the preparation for PrBoom v2.1.0, which was
causing a lot of demos to go out of sync at MAP02. But until recently I never
investigated why such an obviously correct bit of code should cause demos to
fail (30nm4048 was my test demo at the time).
Blindness
There are various known tricks or bugs in Doom that can cause a monster to be blind. Firstly, the REJECT table can be deliberately or accidentally corrupted - this table is a fast lookup used by Doom to indicate which sectors can see each other, and if incorrect data is included in it can prevent monsters seeing the player despite having a clear view of him. This occurs in a lot of old Doom 1 levels because a particular editor (DoomEd) used to include a corrupt REJECT lump. But this is not the case at Underhalls, particularly because the sergeant certainly does shoot the player once he is woken up.
Other tricks for blind monsters include glass walls and see-through doors, all instances of special effects where the player can see through a wall but it is solid as far as the Doom game is concerned. id never used this trick though AFAIK, and certainly not here in Underhalls.
So, having exhausted the usual explanations, we don't have much to go on. Since the bug goes away with a trivial optimisation in the line of sight code, the best guess is that it is a bug in that code. So I compiled a copy of the source with some diagnostics in place, working on the principle that all bugs are easy with enough diagnostics.
It turns out that the line of sight is being blocked by line #136 (this is the line in front of the switch, behind the sergeant). This is unusual for two reasons:
- The line is behind the sergeant, not between it and the player.
- It's a two-sided line, which has a large enough opening that it would not block sight even if it were between them.
So. The question now becomes, how does Doom end up mistakenly believing this line is between the combatants?
Analytic Geometry
To determine whether two line segments intersect, the following test is used:
- Are the end points of line 1 on opposite sides of line 2?
- Are the end points of line 2 on opposite sides of line 1?
Note that, if we call the wall line 1 and the line of sight line 2, then question 1 above is true for the test in question - the wall is "in line" with the line of sight, it just happens to be the wrong side of the sergeant. Question 2 should answer no, because the line of sight is not "in line" with the wall. Doom mistakenly answers yes to this test.
So the bug must be in the function that calculates what side of a line a
point lies on (cf p_sight.c:P_DivlineSide). Now this is a pretty
basic operation in analytic geometry and if Doom had got the formula wrong
then absolutely nothing would work right - Doom gets almost all line of sight
calculations right so there can't be anything fundamentally wrong with this
function. However, the devil is in the detail with this kind of code, and
there are always some special cases to deal with. Note that line #136 is an
east-west line - horizontal on the automap and the Doom code also calls such
lines horizontal. To work out which side of a horizontal line a point is on,
you only have to check its Y coordinate, and the speed-concious Doom
programmers did this optimisation:
if (!node->dy)
{
if (x==node->y)
return 2;
if (y <= node->y)
return node->dx < 0;
return node->dx > 0;
}
Here, node refers to the line and (x,y) is the
point being tested. Before I ran the code in a debugger I read it, and it's
immediately obvious where the bug is. The point's X coordinate is irrelevant,
so why does the third line there refer to x? The code is
nonsensical - comparing x to node->y is
pointless, there is no relevant comparison between X and Y coordinates. The
programmer did a copy and paste from the code for vertical lines, and forgot
to change the x to y in the third line.
And that's why you will almost never see this bug anywhere else. It relies
on a wild coincidence - that the X coordinate of the sergeant, who is at
(1200,1232), equals the Y coordinate of the vertex at the end of
the line in question - at (1232,1200). (Yes, the sergeant's Y
coordinate also equals the vertex's X coordinate, another coincidence but not
relevant to the bug). Because of this coincidence, and the coding bug, Doom
thinks the sergeant is actually standing on the line, and so the line is in
the way of his sight.
MBF hid this bug by optimising the line of sight code so that it never bothered to check lines behind the viewer, which was why it caused the sergeant to no longer be blind, breaking demos.
Finally, I mentioned above that the line would not block sight even if it were in the way. However, Doom gets very confused by a line being in the way when it is behind the looker, because it calculates the distance of the wall along the line of sight and finds it to be negative. This then makes all the calculations about slopes and angles (important to determine whether a window frame obstructs a view vertically) give rather opposite results, so it ends up thinking the window is negative in size, and hence does not allow sight. In other words, it's just a knock-on effect of the first error.
Credits
There are plenty of demos which desync if this bug is corrected - I
mentioned 30nm4048 above (thanks Henning - if I had to spend
years getting one demo working, at least it was a good one worth watching
:-).
I first hit this bug sometime in 1999, but didn't investigate the ultimate cause until recently. This research and document are by Colin Phipps, 2002/08/26.
