Doom engine
Encyclopedia
The Doom engine is the game engine
that powers the id Software
games Doom and Doom II
. It is also used by HeXen
, Heretic
, Strife, Freedoom
, and HacX, and other games produced by licensees. It was created by John Carmack, with auxiliary functions written by Mike Abrash, John Romero
, Dave Taylor
and Paul Radek. Originally developed on NeXT
computers, it was ported
to DOS
for Doom' s initial release and was later ported to several game consoles and operating system
s.
The source code
for the Linux
version of Doom was released to the public in 1997 under a license that granted rights to non-commercial use, and was re-released under the GNU General Public License
in 1999.
The dozens of unofficial Doom source port
s that have been created since then allow Doom to run on previously unsupported operating systems and sometimes radically expanding the engine's functionality with new features.
It is not a true "3D" engine, as it is not possible to look up and down properly, and two sectors cannot be placed above and under each other, but it is a fairly elegant system that allows pseudo-3D rendering. The Doom engine was later renamed to "id-tech 1" in order to categorize it in a list of id Software's long line of game engines
.
, which represents a single 2D point. Vertices (or "vertexes" as they are referred to internally) are then joined to form lines
, known as "linedefs". Each linedef can have either one or two sides, which are known as "sidedefs". Sidedefs are then grouped together to form polygon
s; these are called "sectors". Sectors represent particular areas of the level.
and a ceiling texture. To have a different light level in a particular area, for example, a new sector must be created for that area with a different light level. One-sided linedefs therefore represent solid walls, while two-sided linedefs represent bridge lines between sectors.
(BSP). A tool is used to generate the BSP data for a level beforehand. This process can take quite some time for a large level. It is because of this that it is not possible to move the walls in Doom; while doors and lifts move up and down, none of them ever move sideways.
The level is divided up into a binary tree
: each location in the tree is a "node" which represents a particular area of the level (with the root node representing the entire level). At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. At the same time, the dividing line divides linedefs into line segments called "segs".
At the leaves of the tree are convex polygon
s, where further division of the level is not needed. These convex polygons are referred to as subsectors (or "SSECTORS"), and are bound to a particular sector. Each subsector has a list of segs associated with it.
The BSP system sorts the subsectors into the right order for rendering. The algorithm is fairly simple:
The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that no time is used drawing objects that are not visible and as a result maps can become very large without any speed penalty.
The Doom engine renders the walls as it traverses the BSP tree, drawing subsectors by order of distance from the camera so that the closest segs are drawn first. As the segs are drawn, they are stored in a linked list. This is used to clip other segs rendered later on, reducing overdraw. This is also used later to clip the edges of sprites.
Once the engine reaches a solid (1-sided) wall at a particular x ordinate, no more lines need to be drawn at that area. For clipping the engine stores a "map" of areas of the screen where solid walls have been reached. This allows far away parts of the level which are invisible to the player to be clipped completely.
The Doom graphic format stores the wall textures as sets of vertical columns; this is useful to the renderer, which essentially renders the walls by drawing lots of vertical columns of texture.
-like algorithm. Because of this, it is sometimes possible if a bad BSP builder is used to get "holes" where the floor or ceiling bleeds down to the edges of the screen. This is also the reason that if the player travels outside of the level using the noclip cheat
the floors and ceilings will appear to stretch out from the level over the empty space.
The floor and ceiling are drawn as "visplanes". These represent horizontal runs of texture, from a floor or ceiling at a particular height, light level and texture (if two adjacent sectors have exactly the same floor, these can get merged into one visplane). Each x position in the visplane has a particular vertical line of texture which is to be drawn.
Because of this limit of drawing one vertical line at each x position, it is sometimes necessary to split visplanes into multiple visplanes. For example, consider viewing a floor with two concentric
squares. The inner square will vertically divide the surrounding floor. In that horizontal range where the inner square is drawn, two visplanes are needed for the surrounding floor.
This leads to one of Doom' s classic limitations which frustrated many mappers for a long time. DOOM contained a static limit on the number of visplanes; if exceeded, a visplane overflow would occur, causing DOOM to crash back to DOS with one of two messages, "No more visplanes!" or "visplane overflow (128 or higher)" The easiest way to invoke the visplane limit is a large checkerboard floor pattern; this creates a large number of visplanes.
As the segs are rendered, visplanes are also added, extending from the edges of the segs towards the vertical edges of the screen. These extend until they reach existing visplanes. Because of the way this works, the system is dependent on the fact that segs are rendered in order by the overall engine; it is necessary to draw nearer visplanes first, so that they can "cut off" by others further away. If unstopped, the floor or ceiling will "bleed out" to the edges of the screen, as previously described. Eventually, the visplanes form a "map" of particular areas of the screen in which to draw particular textures.
While visplanes are constructed essentially from vertical "strips", the actual low level rendering is performed in the form of horizontal "spans" of texture. After all the visplanes have been constructed, they are converted into spans which are then rendered to the screen. This appears to be a tradeoff: it is easier to construct visplanes as vertical strips, but because of the nature of how the floor and ceiling textures appear it is easier to draw them as horizontal strips. Because of the nature of visplanes, the conversion is fairly trivial, however.
The edges of sprites are clipped by checking the list of segs previously drawn. Sprites in Doom are stored in the same column based format as the walls are, which again is useful for the renderer. The same functions which are used to draw walls are used to draw sprites as well.
While subsectors are guaranteed to be in order, the sprites within them are not. Doom stores a list of sprites to be drawn ("vissprites") and sorts the list before rendering. Far away sprites are drawn before close ones. This causes some overdraw but usually this is negligible.
There is a final issue of middle textures on 2-sided lines, used in transparent bars for example. These are mixed in and drawn with the sprites at the end of the rendering process, rather than with the other walls.
and Strife.
Games that are built directly on the Doom engine
Games that are based on Doom or Doom 2 code
Game engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...
that powers the id Software
Id Software
Id Software is an American video game development company with its headquarters in Richardson, Texas. The company was founded in 1991 by four members of the computer company Softdisk: programmers John Carmack and John Romero, game designer Tom Hall, and artist Adrian Carmack...
games Doom and Doom II
Doom II
Doom II: Hell on Earth is an award winning first-person shooter video game and second title of id Software's Doom franchise. Unlike Doom which was initially only available through shareware and mail order, Doom II was a commercial release sold in stores...
. It is also used by HeXen
Hexen
Hexen is a first-person shooter video game developed by Raven Software, published by id Software, and distributed by GT Interactive beginning on September 30, 1995. It is the sequel to 1994's Heretic, and the second game in the Serpent Riders series...
, Heretic
Heretic (computer game)
Heretic is a fantasy first-person shooter video game created by Raven Software, published by id Software, and distributed by GT Interactive in 1994. It was made available on Steam on August 3, 2007....
, Strife, Freedoom
Freedoom
Freedoom is a free Doom engine based first-person shooter game currently under development. The game is currently in an alpha stage and many features are missing, for example some monsters and other sprites are replaced by placeholder images, some levels are missing, and some levels have no music....
, and HacX, and other games produced by licensees. It was created by John Carmack, with auxiliary functions written by Mike Abrash, John Romero
John Romero
Alfonso John Romero is a game designer, programmer, and developer in the video game industry. He is best known as a co-founder of id Software and was a designer for many of their games, including Wolfenstein 3D, Dangerous Dave, Doom and Quake...
, Dave Taylor
Dave D. Taylor
Dave D. Taylor is an American game programmer, best known as a former id Software employee and noted for his work promoting Linux gaming.In 1993 he graduated from University of Texas at Austin with a Bachelor of Science degree in electrical engineering....
and Paul Radek. Originally developed on NeXT
NeXT
Next, Inc. was an American computer company headquartered in Redwood City, California, that developed and manufactured a series of computer workstations intended for the higher education and business markets...
computers, it was ported
Porting
In computer science, porting is the process of adapting software so that an executable program can be created for a computing environment that is different from the one for which it was originally designed...
to DOS
DOS
DOS, short for "Disk Operating System", is an acronym for several closely related operating systems that dominated the IBM PC compatible market between 1981 and 1995, or until about 2000 if one includes the partially DOS-based Microsoft Windows versions 95, 98, and Millennium Edition.Related...
for Doom
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s.
The source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
for the Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
version of Doom was released to the public in 1997 under a license that granted rights to non-commercial use, and was re-released under the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
in 1999.
The dozens of unofficial Doom source port
Doom source port
A Doom source port is a source port of id Tech 1, the game engine used by the video game Doom. The term usually denotes a modification made by Doom fans, as opposed to any of the official Doom versions produced by id Software or affiliated companies.-Doom source release:The source code for the Doom...
s that have been created since then allow Doom to run on previously unsupported operating systems and sometimes radically expanding the engine's functionality with new features.
It is not a true "3D" engine, as it is not possible to look up and down properly, and two sectors cannot be placed above and under each other, but it is a fairly elegant system that allows pseudo-3D rendering. The Doom engine was later renamed to "id-tech 1" in order to categorize it in a list of id Software's long line of game engines
Id Tech
id Tech is the family of game engines designed and developed by id Software. Prior to the presentation of the id Tech 5-based game Rage, the engines lacked official designation and as such were referred to as the Doom and Quake engines, from the name of the main game series the engines have been...
.
Doom level structure
Viewed from the top down, all Doom levels are actually two-dimensional, demonstrating one of the key limitations of the Doom engine: it is not possible to have "rooms above rooms". This limitation, however, has a silver lining: a "map mode" can be easily displayed, which represents the walls and the player's position, much like the first image to the right.Basic objects
The base unit is the vertexVertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
, which represents a single 2D point. Vertices (or "vertexes" as they are referred to internally) are then joined to form lines
Line (mathematics)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...
, known as "linedefs". Each linedef can have either one or two sides, which are known as "sidedefs". Sidedefs are then grouped together to form polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
s; these are called "sectors". Sectors represent particular areas of the level.
Sectors
Each sector contains a number of properties: a floor height, ceiling height, light level, a floor textureTexture mapping
Texture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
and a ceiling texture. To have a different light level in a particular area, for example, a new sector must be created for that area with a different light level. One-sided linedefs therefore represent solid walls, while two-sided linedefs represent bridge lines between sectors.
Sidedefs
Sidedefs are used to store wall textures; these are completely separate from the floor and ceiling textures. Each sidedef can have three textures; these are called the middle, upper and lower textures. In one-sided linedefs, only the middle texture is used for the texture on the wall. In two-sided linedefs, the situation is more complex. The lower and upper textures are used to fill the gaps where adjacent sectors have different floor and ceiling heights: lower textures are used for steps, for example. The sidedefs can have a middle texture as well, although most do not; this is used to make textures hang in mid air. For example, when a transparent bar texture is seen forming a cage, this is an example of a middle texture on a two-sided linedef.Binary space partitioning
Doom makes use of a system known as binary space partitioningBinary space partitioning
In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
(BSP). A tool is used to generate the BSP data for a level beforehand. This process can take quite some time for a large level. It is because of this that it is not possible to move the walls in Doom; while doors and lifts move up and down, none of them ever move sideways.
The level is divided up into a binary tree
Binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
: each location in the tree is a "node" which represents a particular area of the level (with the root node representing the entire level). At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. At the same time, the dividing line divides linedefs into line segments called "segs".
At the leaves of the tree are convex polygon
Convex polygon
In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...
s, where further division of the level is not needed. These convex polygons are referred to as subsectors (or "SSECTORS"), and are bound to a particular sector. Each subsector has a list of segs associated with it.
The BSP system sorts the subsectors into the right order for rendering. The algorithm is fairly simple:
- Start at the root node.
- Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a Scanline algorithm. This can be found from looking at which side of the node's dividing line the camera is on.
- When a subsector is reached, draw it.
The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that no time is used drawing objects that are not visible and as a result maps can become very large without any speed penalty.
Drawing the walls
All walls in Doom are drawn vertically; it is because of this that it is not possible to properly look up and down. It is possible to perform a form of look up/down via "y-shearing", and many modern Doom source ports do this, as well as later games that use the engine, such as Heretic. Essentially this works by moving the horizon line up and down within the screen, in effect providing a "window" on a taller viewable area. By moving the window up and down, it is possible to give the illusion of looking up and down. However, this will distort the view the further up and down the player looks.The Doom engine renders the walls as it traverses the BSP tree, drawing subsectors by order of distance from the camera so that the closest segs are drawn first. As the segs are drawn, they are stored in a linked list. This is used to clip other segs rendered later on, reducing overdraw. This is also used later to clip the edges of sprites.
Once the engine reaches a solid (1-sided) wall at a particular x ordinate, no more lines need to be drawn at that area. For clipping the engine stores a "map" of areas of the screen where solid walls have been reached. This allows far away parts of the level which are invisible to the player to be clipped completely.
The Doom graphic format stores the wall textures as sets of vertical columns; this is useful to the renderer, which essentially renders the walls by drawing lots of vertical columns of texture.
Floor and ceiling
The system for drawing floors and ceilings ("flats") is less elegant than that used for the walls. Flats are drawn with a flood fillFlood fill
Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining...
-like algorithm. Because of this, it is sometimes possible if a bad BSP builder is used to get "holes" where the floor or ceiling bleeds down to the edges of the screen. This is also the reason that if the player travels outside of the level using the noclip cheat
Noclip mode
In some video games, noclip is a video game cheat command that prevents the first-person player character camera from being obstructed by other objects and permits the camera to move in any direction, allowing it to pass through such things as walls, props, and other players.-Description:The term...
the floors and ceilings will appear to stretch out from the level over the empty space.
The floor and ceiling are drawn as "visplanes". These represent horizontal runs of texture, from a floor or ceiling at a particular height, light level and texture (if two adjacent sectors have exactly the same floor, these can get merged into one visplane). Each x position in the visplane has a particular vertical line of texture which is to be drawn.
Because of this limit of drawing one vertical line at each x position, it is sometimes necessary to split visplanes into multiple visplanes. For example, consider viewing a floor with two concentric
Concentric
Concentric objects share the same center, axis or origin with one inside the other. Circles, tubes, cylindrical shafts, disks, and spheres may be concentric to one another...
squares. The inner square will vertically divide the surrounding floor. In that horizontal range where the inner square is drawn, two visplanes are needed for the surrounding floor.
This leads to one of Doom
As the segs are rendered, visplanes are also added, extending from the edges of the segs towards the vertical edges of the screen. These extend until they reach existing visplanes. Because of the way this works, the system is dependent on the fact that segs are rendered in order by the overall engine; it is necessary to draw nearer visplanes first, so that they can "cut off" by others further away. If unstopped, the floor or ceiling will "bleed out" to the edges of the screen, as previously described. Eventually, the visplanes form a "map" of particular areas of the screen in which to draw particular textures.
While visplanes are constructed essentially from vertical "strips", the actual low level rendering is performed in the form of horizontal "spans" of texture. After all the visplanes have been constructed, they are converted into spans which are then rendered to the screen. This appears to be a tradeoff: it is easier to construct visplanes as vertical strips, but because of the nature of how the floor and ceiling textures appear it is easier to draw them as horizontal strips. Because of the nature of visplanes, the conversion is fairly trivial, however.
Things (sprites)
Each sector within the level has a linked list of things stored in that sector. As each sector is drawn the sprites are placed into a list of sprites to be drawn. If not within the field of view these are ignored.The edges of sprites are clipped by checking the list of segs previously drawn. Sprites in Doom are stored in the same column based format as the walls are, which again is useful for the renderer. The same functions which are used to draw walls are used to draw sprites as well.
While subsectors are guaranteed to be in order, the sprites within them are not. Doom stores a list of sprites to be drawn ("vissprites") and sorts the list before rendering. Far away sprites are drawn before close ones. This causes some overdraw but usually this is negligible.
There is a final issue of middle textures on 2-sided lines, used in transparent bars for example. These are mixed in and drawn with the sprites at the end of the rendering process, rather than with the other walls.
Games using the Doom engine
Though the Doom engine achieved most of its fame as a result of powering the classic first person shooter Doom, it was used for many other games. It is usually considered that the "Big Four" Doom engine games are Doom, Heretic, HexenHexen
Hexen is a first-person shooter video game developed by Raven Software, published by id Software, and distributed by GT Interactive beginning on September 30, 1995. It is the sequel to 1994's Heretic, and the second game in the Serpent Riders series...
and Strife.
Games that are built directly on the Doom engine
- Doom (1993)
- Doom II: Hell on Earth (1994)
- Final DoomFinal DoomFinal Doom is a first-person shooter video game that uses the game engine, items and characters from Doom II. It consists of two 32-level megawads , The Plutonia Experiment by the Casali brothers, and TNT: Evilution by TeamTNT. Final Doom was released in 1996 and distributed as an official id...
- Final Doom
- Heretic (1994)
- Heretic: Shadow of the Serpent Riders
- HexenHexenHexen is a first-person shooter video game developed by Raven Software, published by id Software, and distributed by GT Interactive beginning on September 30, 1995. It is the sequel to 1994's Heretic, and the second game in the Serpent Riders series...
(1995)- Hexen: Deathkings of the Dark Citadel
- Strife (1996)
Games that are based on Doom or Doom 2 code
- HacX (1997)
- Chex QuestChex QuestChex Quest is a non-violent first-person shooter video game created in 1996 by Digital Café as a Chex cereal promotion aimed at children aged 9 and up...
(1996) - Chex Quest 2Chex Quest 2Chex Quest 2 was released in 1997, after the release of the cereal box promotional game Chex Quest, and was available exclusively from the official Chex Quest website...
(1997)
See also
- List of game engines
- First person shooter engine
- id TechId Techid Tech is the family of game engines designed and developed by id Software. Prior to the presentation of the id Tech 5-based game Rage, the engines lacked official designation and as such were referred to as the Doom and Quake engines, from the name of the main game series the engines have been...
- Quake engineQuake engineThe Quake engine is the game engine that was written to power 1996's Quake, written by id Software. It featured true 3D real-time rendering and is now licensed under the terms of the GNU General Public License ....
- Quake (series)Quake (series)The Quake series is a line of first-person shooter video games produced by id Software.-Overview:The Quake series is somewhat unusual in that its focus changes frequently; the story of Quake II has nothing to do with Quake, and Quake III Arena has little to do with either of its predecessors...
- List of first-person shooter engines