Archville Ghosts

Most players will have seen ghosts occasionally in Doom. The common cause of ghosts is archvilles resurrecting crushed monsters, and is quite well understood. I may as well review them here.

When an archville resurrects a monster, Doom simply modifies the monster object in the game to reverse the death process. It sets the monster into its first respawn frame, starting the rise-from-the-dead animation. It sets its health back to its initial value, and it un-reduces the monster's original height (when a monster is killed, its height is divided by 4; so Doom multiplies it by 4 when resurrecting. If the monster's height was not a multiple of 4 then this process loses accuracy).

The problem arises when a monster corpse is crushed, say by a closing door. When this happens, Doom sets the monster's animation to the pool-of-gibs frame, and reduces its width and height to 0 (cf pmap.c:PIT_ChangeSector). The latter is presumably done so the gibs don't get crushed any further.

It all goes wrong if an archville resurrects a crushed corpse. The resurrection code restores its health, but its width and height remain 0. The monster is therefore alive, but unable to collide with anything, or be hit in any line-based geometry calculation (i.e. gunfire). However exposions can still hit the monster (because they work only on the distance from the explosion).

Note that monsters respawning (at Nightmare or -respawn) are never made ghosts by this method. In this case Doom doesn't take the same short-cut; instead it really spawns an entirely new thing and removes the old one.

This bug has occasionally been used as a deliberate feature in PWADs. Probably the most known is Hatred (Requiem MAP23), and the classic Afterlife (Hell Revealed MAP26) also uses them for effect. See the ghost monster FAQ for more information on Archville ghosts.

The All-Ghosts Bug

Ok, so now for something new. The all-ghosts bug is a much stranger, and much rarer event in Doom. If not for demos proving its existence it would probably be considered a myth, because very few players have encountered it in a real game - I know that I never have. In fact I only know of two demos in existence showing the bug, so it is on those that I base my analysis.

So what is the bug? Suddenly, with no obvious trigger, all the things in the game become ghosts. All monsters, and all the players, become ghosts. That pretty much puts an end to any serious game, so it's a hard one to miss when it happens :-).

In the past, this bug has been identified under two different names - SP players call it the all-ghosts bug because all the monsters become ghosts, while DM players have encountered the same bug and called it the DM noclipping bug, due to the effect on players. Because the two groups are looking at different types of game, the impression of the bug is different, and it occurs so rarely that we haven't got around to comparing notes until now. But they can be traced to the same actual bug, as I will do below.

Technical Details

Ok, so what causes the all-ghosts bug? Actually the bug is trivial to locate, but the cause is rather harder to explain, so I'll start by explaining the particular bit of the engine in question and come to the bug last.

One of the basic operations in the Doom engine is the ability to follow a line, and find all the game objects (things and lines) which it crosses. This is performed by p_maputl.c:P_PathTraverse. This function is given a start point and an end point, and it uses the blockmap and some geometry calculations to construct a list, in order, of everything that obstucts the line between these points. The main use of this function is for straight line shots from weapons, but it is also used for the player's use action (i.e. when the player hits spacebar, the engine has to "feel" for doors or switches in front of the player), and also for working out how the player should slide across obstructions.

The list of obstructions, or intercepts as Doom calls them, is stored in an array. Living down to its usual code quality, the Doom engine holds these in a static array with a fixed size limit of 128 intercepts ("MAXINTERCEPTS"). And there is no range checking when intercepts are added to this array - so it can overflow, with various nasty consequences.

But 128 intercepts ought to be enought for anyone, I hear you say. After all, you can't bounce off of more than one wall at a time, can't hit more than one switch at a time, and can't shoot more than once monster or wall with one bullet. The point of intercepts, after all, is that they obstruct whatever you're trying to do, and it goes no further. Of course there are some intercepts that are not obstructions--for example power-ups and corpses will not obstuct shots--but 128 intercepts is still more than generous. After all, doom2.exe freaks out in far more obvious ways with as few as 64 things and 16 two-sided lines on the screen at once.

Well, it should be enough. But having sniped at the poor implementation of the intercept checking, it's time to complain about the poor way in which the algorithm is used. While most of the intercept code is just looking for the first "hit", the trouble is that different bits of code are looking for different kinds of hit. A shot may pass over a line which is in fact a low switch panel, but P_PathTraverse doesn't know whether we're looking for a switch or a hit, so it has to assume it could be looking for either. So it works pessimistically: it lists every intercept between the start and end point, regardless of the fact we are only looking for one particular intercept, because the programmers were too lazy to find a way of telling it what to look for. Each bit of the engine that calls P_PathTraverse gets a complete list of intercepts, and it then read the list until it finds the only obstruction it cares about--and throws the rest of the results away. There is some fast exit code included in P_PathTraverse, but it is never actually used.

extern intercept_t      intercepts[MAXINTERCEPTS];
extern intercept_t*     intercept_p;

Once the intercepts array is overflowed, it corrupts the pointer used for storing new intercepts. The code will begin overwriting memory. Exactly what happens at this point I am not sure. It is not clear if the corruption of intercept_p causes the all-ghosts bug directly, or whether that is an indirect consequence of the memory corruption that occurs afterwards. To answer that question for certain, you would probably need to be able to run the original EXE inside a debugger..


Are these the only ways to get ghosts in Doom? These are the only ones I have hard evidence for after many years of playing the game.

The all-ghosts bug has been known for some time, but I only investigated it when Ledmeister drew attention to it on in July 2001 (cf manorbug.lmp on Google Groups). See his example demos of the bug from his collection of weird Doom demos.

Another piece of obscure Doom research brought to you by Colin Phipps, 2003/02/08.