Linedef deletion

Linedef deletion, and the more general phenomenon of memory corruption on which it is based, is a bug in versions of Doom based on the Atari Jaguar port. When solid objects move outside the bounding box of the blockmap in these versions of Doom, they will begin corrupting zone memory in an arbitrary fashion. Due to the ordering of level loading operations in the function P_SetupLevel, the first data corrupted will usually be the runtime arrays of vertexes and linedefs (called vertexes and lines in the source code, respectively). This causes parts of the map to deform in real time.

Cause

The following difference between the released source code for the Linux version and the Atari Jaguar version of the game is the root cause of the problem (lines in red beginning with a minus sign are not present in the Jaguar codebase):

void P_UnsetThingPosition(mobj_t *thing) { int blockx, blocky; if (!(thing->flags & MF_NOSECTOR)) { /* inert things don't need to be in blockmap */ /* unlink from subsector */ if(thing->snext) thing->snext->sprev = thing->sprev; if(thing->sprev) thing->sprev->snext = thing->snext; else thing->subsector->sector->thinglist = thing->snext; } if (!(thing->flags & MF_NOBLOCKMAP)) { /* inert things don't need to be in blockmap */ /* unlink from block map */ if (thing->bnext) thing->bnext->bprev = thing->bprev; if (thing->bprev) thing->bprev->bnext = thing->bnext; else { blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT; blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT; - if (blockx>=0 && blockx < bmapwidth - && blocky>=0 && blocky <bmapheight) - { blocklinks[blocky*bmapwidth+blockx] = thing->bnext; - } } } }

The removed or originally missing positional bounds check in this function means that when a solid object (one not having the MF_NOBLOCKMAP bitflag set) is ready to move to a new position and unlinks itself from the blockmap cell in which it is currently listed, it does not check if that cell is in bounds with respect to the size of the blocklinks array. It will thus access offsets into that array which are potentially invalid, being before the start or after the end of the memory actually allocated for mobj blockmap links. This causes unrelated memory to be overwritten with pointer values which refer to other instances of the mobj_t structure.

This missing check is restored in the 3DO version of the code, and thus the error does not occur in that version. However, objects moving outside the map still cause various other problems which can slow down and crash the game, for reasons not currently understood.

Common triggers and effects

In the Sony PlayStation version of Doom, the phenomenon is frequently associated with spawning of lost souls outside the boundaries of the map by pain elementals, a bug which was also present in vanilla Doom. Due to the change made to P_UnsetThingPosition detailed above, a lost soul, which is a solid object, will begin writing pointers to its next neighbor within the last valid blockmap cell in which it resided into unrelated memory for every movement step it makes while outside the bounds of the blockmap. This manifests as linedefs skewing outside of their normal position, allowing the player and other monsters to move through them and even outside of the map (potentially triggering further corruption in the process).

This particular cause no longer occurs in the Final Doom port to the PlayStation system, nor in Doom 64, as a check was added to the pain elemental's logic for intervening solid lines when spawning lost souls in both games. This may indicate that Midway Games' developers became aware of the problem themselves after the first game's release.

The following differences in effects have been observed across the affected ports:

• The Jaguar, Sega 32X, and Game Boy Advance ports are more likely to crash during play in the level than the Sony PlayStation or Nintendo 64. This is particularly true for the Sega 32X version, which will frequently stop with a "CPU Bus Error" message visible as soon as memory corruption begins. Presumably, the smaller amount of memory available on these systems is one reason for this.
• Sidedef textures may be corrupted easily in the Jaguar version; they will usually display as the ASH01 texture when this occurs.
• The Game Boy Advance version tends to display corruption in sidedef textures, sector flats, and sector light levels first. Incorrect textures will either display as ASH01 as in the Jaguar version, or will display as tutti-frutti- or Medusa-effect-like garbage.

Corruption of memory may often lead to a black screen or error message after exiting the level, if specific structures on the zone heap are damaged. It is also possible for the game to freeze when sufficiently corrupted.

Deliberate use

Since the player is also a solid object, it is possible to deliberately "delete" certain linedefs by moving to pre-determined coordinates outside the map in order to deliberately corrupt the memory corresponding to that location. Lag clipping may be used in all of the Jaguar-based ports in order to access the void area of the map and trigger the effect. In addition, earlier ports such as the Jaguar version itself allow easy clipping through linedefs by the player simply by firing rockets against walls at the proper angle.

In a technical sense, the linedef is not deleted, and does continue to exist in memory, but the runtime change in its position causes collision operations against it to fail. In Doom 64, this is used in speedruns, in particular to remove a linedef belonging to the exit room of MAP18: Spawned Fear, allowing a significant portion of the level to be skipped.

External links

• YouTube video displaying corruption of MAP30: Threshold of Pain in the PlayStation version of Doom.