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 awaking him..

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, behing the sergeant). This is unusual for two reasons:

1. The line is behind the sergeant, not between it and the player.
2. 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:

1. Are the end points of line 1 on opposite sides of line 2?
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 fo 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 things 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 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

I'm afraid I don't have a demo of this one, but I've described how to see the bug. I don't know of any Compet-n demos where the bug is visible; pacifist MAP02 is the most likely candidate but apparently no-one has accomplished that - yet. There are plenty of demos which desync if this bug is fixed - 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.