Doom engine

Last updated
id Tech 1
Developer(s) id Software, (John Carmack, John Romero, Dave Taylor)
Final release
1.9 / February 1, 1995;29 years ago (1995-02-01)
Repository github.com/id-Software/DOOM
Written in C, Assembly language
Platform MS-DOS, Windows, Mac, Linux, Android, Amiga, NeXTSTEP, NeXT, Jaguar, 32X, PlayStation, 3DO, Nintendo 64, Saturn, Game Boy Advance, Switch, BSD, Unix, others,
Predecessor Wolfenstein 3D engine
Successor Quake engine
License GNU GPL-2.0-or-later [1]
3DO: MIT [2]

id Tech 1, also known as the Doom engine, is the game engine used in the id Software video games Doom and Doom II: Hell on Earth . It is also used in Heretic , Hexen: Beyond Heretic , Strife: Quest for the Sigil , Hacx: Twitch 'n Kill , Freedoom , 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, [3] it was ported to MS-DOS and compatible operating systems for Doom's initial release and was later ported to several game consoles and operating systems.

Contents

The source code to the Linux version of Doom was released to the public under a license that granted rights to non-commercial use on December 23, 1997, followed by the Linux version of Doom II about a week later on December 29, 1997. [4] [5] The source code was later re-released under the GNU General Public License v2.0 or later on October 3, 1999. [6] [7] The dozens of unofficial Doom source ports that have been created since then allow Doom to run on previously unsupported operating systems and sometimes radically expand the engine's functionality with new features.

Although the engine renders a 3D space, that space is projected from a two-dimensional floor plan. The line of sight is always parallel to the floor, walls must be perpendicular to the floors, and it is not possible to create multi-level structures or sloped areas (floors and ceilings with different angles). Despite these limitations, the engine represented a technological leap from id's previous Wolfenstein 3D engine. 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. [8]

Game world

The Doom engine separates rendering from the rest of the game. The graphics engine runs as fast as possible, but the game world runs at 35 frames per second regardless of the hardware, so multiple players can play against each other using computers of varying performance. [9]

Level structure

A simple setup demonstrating how Doom represents levels internally

Map view in editor Doom-map-format-map.svg
Map view in editor

Viewed from the top down, all Doom levels are actually two-dimensional, demonstrating one of the key limitations of the Doom engine: room-over-room is not possible. 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 vertex, 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 polygons; 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 texture 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 partitioning (BSP). [10] 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". [11]

At the leaves of the tree are convex polygons, 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. [10]

The BSP system sorts the subsectors into the right order for rendering. The algorithm is fairly simple:

  1. Start at the root node.
  2. 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.
  3. When a subsector is reached, draw it. [12]

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.

Rendering

Drawing the walls

All of the 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 coordinate, 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 many vertical columns of textures.

Floor and ceiling

The system for drawing floors and ceilings ("flats") is less elegant [ according to whom? ] than that used for the walls. Flats are drawn with a flood fill-like algorithm. Because of this, if a bad BSP builder is used, it is sometimes possible to get "holes" where the floor or ceiling bleeds down to the edges of the screen, a visual error commonly referred to as a "slime trail". [13] This is also the reason why 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 [ who? ] for a long time. Doom contained a static limit on the number of visplanes; if exceeded, a "visplane overflow" would occur, causing the game to exit 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 trade off: 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.

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

The Doom engine achieved most of its fame as a result of powering the classic first person shooter Doom , and it was used in several other games. It is usually considered that the "Big Four" Doom engine games are Doom , Heretic , Hexen: Beyond Heretic , and Strife: Quest for the Sigil .

Games built directly on the Doom engine

YearTitleDeveloper
1993 Doom id Software
1994 Doom II: Hell on Earth
Heretic Raven Software
1995 The Ultimate Doom id Software
Master Levels for Doom II
Hexen: Beyond Heretic Raven Software
1996 Final Doom TeamTNT
Heretic: Shadow of the Serpent Riders Raven Software
Hexen: Deathkings of the Dark Citadel
Strife: Quest for the Sigil Rogue Entertainment

Games based on the Doom or Doom II code

YearTitleDeveloper
1996 Chex Quest Digital Café
1997 Doom 64 Midway Studios San Diego
Chex Quest 2: Flemoids Take Chextropolis Digital Café
HacX Banjo Software

See also

Notes

Related Research Articles

<i>Heretic</i> (video game) 1994 dark fantasy first-person shooter video game developed by Raven Software

Heretic is a dark fantasy first-person shooter video game released in December 1994. It was developed by Raven Software and published by id Software through GT Interactive.

<i>Hexen: Beyond Heretic</i> 1995 video game

Hexen: Beyond Heretic is a fantasy first-person shooter video game developed by Raven Software and published by id Software distributed through GT Interactive on October 30, 1995. It is the sequel to 1994's Heretic, and the second game in Raven Software's "Serpent Riders" trilogy, which culminated with Hexen II. The title comes from the German noun Hexen, which means "witches", and/or the verb hexen, which means "to cast a spell". Game producer John Romero stated that a third, unreleased game in this series was to be called Hecatomb.

<span class="mw-page-title-main">Binary space partitioning</span> Method for recursively subdividing a space into two subsets using hyperplanes

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

<span class="mw-page-title-main">Texture mapping</span> Method of defining surface detail on a computer-generated graphic or 3D model

Texture mapping is a method for mapping a texture on a computer-generated graphic. Texture here can be high frequency detail, surface texture, or color.

<span class="mw-page-title-main">Scene graph</span>

A scene graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games, which arranges the logical and often spatial representation of a graphical scene. It is a collection of nodes in a graph or tree structure. A tree node may have many children but only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes and objects into a compound object that can then be manipulated as easily as a single object.

<span class="mw-page-title-main">Ray casting</span> Methodological basis for 3D CAD/CAM solid modeling and image rendering

Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.

<span class="mw-page-title-main">Hidden-surface determination</span> Visibility in 3D computer graphics

In 3D computer graphics, hidden-surface determination is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden-surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. When referring to line rendering it is known as hidden-line removal. Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.

2.5D perspective refers to gameplay or movement in a video game or virtual reality environment that is restricted to a two-dimensional (2D) plane with little or no access to a third dimension in a space that otherwise appears to be three-dimensional and is often simulated and rendered in a 3D digital environment.

<span class="mw-page-title-main">Build (game engine)</span> First-person shooter engine

The Build Engine is a first-person shooter engine created by Ken Silverman, author of Ken's Labyrinth, for 3D Realms. Like the Doom engine, the Build Engine represents its world on a two-dimensional grid using closed 2D shapes called sectors, and uses simple flat objects called sprites to populate the world geometry with objects.

<i>Kens Labyrinth</i> 1993 video game

Ken's Labyrinth is a first-person shooter for MS-DOS published in 1993 by Epic MegaGames. It was programmed by Ken Silverman, who later designed the Build engine used for rendering in 3D Realms's Duke Nukem 3D (1996). Ken's Labyrinth consists of three episodes, the first of which was released as shareware. An earlier version was self-published by Silverman.

<span class="mw-page-title-main">Shader</span> Type of program in a graphical processing unit (GPU)

In computer graphics, a shader is a computer program that calculates the appropriate levels of light, darkness, and color during the rendering of a 3D scene—a process known as shading. Shaders have evolved to perform a variety of specialized functions in computer graphics special effects and video post-processing, as well as general-purpose computing on graphics processing units.

A first-person shooter engine is a video game engine specialized for simulating 3D environments for use in a first-person shooter video game. First-person refers to the view where the players see the world from the eyes of their characters. Shooter refers to games which revolve primarily around wielding firearms and killing other entities in the game world, either non-player characters or other players.

<i>Quake</i> engine Video game engine developed by id Software

The Quake engine is the game engine developed by id Software to power their 1996 video game Quake. It featured true 3D real-time rendering and since 2012, licensed under the terms of GNU General Public License v2.0 or later.

<span class="mw-page-title-main">Autodesk Softimage</span> Discontinued 3D graphics software

Autodesk Softimage, or simply Softimage was a 3D computer graphics application, for producing 3D computer graphics, 3D modeling, and computer animation. Now owned by Autodesk and formerly titled Softimage|XSI, the software has been predominantly used in the film, video game, and advertising industries for creating computer generated characters, objects, and environments.

<span class="mw-page-title-main">3D GameStudio</span>

3D GameStudio or 3DGS is a pan 3D computer game development system which allows the users to create 3D games and other virtual reality applications, and publish them royalty-free. It includes a model/terrain editor, a level editor, a script editor/debugger and comes with a big collection of textures, models and artwork, as well as a game template system that allows the creation of basic shooter games or RPGs without programming. For complex games or other applications, either the integrated programming language named Lite-C or an external development language such as Visual C++ or Borland Delphi can be used.

Jedi is a game engine developed primarily by Ray Gresko for LucasArts. It is very similar to the Build engine used in Duke Nukem 3D. While not a true 3D engine, it supported a three-dimensional environment with no limitations in the 3rd dimension (Z). In Doom, environments or levels were limited to existing in the X-Y plane only – levels were laid out two-dimensionally: while floor and ceiling heights could differ, areas could not overlap vertically. The Jedi Engine had support for areas or rooms on top of one another, a trait that it shared with the Build engine. In the Dark Forces revision of the engine, the renderer could not display two rooms situated on top of each other simultaneously. This capability was added for Outlaws.

<span class="mw-page-title-main">Pre-rendering</span>

Pre-rendering is the process in which video footage is not rendered in real-time by the hardware that is outputting or playing back the video. Instead, the video is a recording of footage that was previously rendered on different equipment. Pre-rendered assets may also be outsourced by the developer to an outside production company. Such assets usually have a level of complexity that is too great for the target platform to render in real-time.

id Tech Series of video game engines

id Tech is a series of separate game engines designed and developed by id Software. Prior to the presentation of the id Tech 5-based game Rage in 2011, the engines lacked official designation and as such were simply referred to as the Doom and Quake engines, from the name of the main game series the engines had been developed for. "id Tech" has been released as free software under the GNU General Public License. id Tech versions 0 to 3 were released under GPL-2.0-or-later. id Tech versions 3.5 to 4.5 were released under GPL-3.0-or-later. id Tech 5 to 7 are proprietary, with id Tech 7 currently being the latest utilized engine.

<span class="mw-page-title-main">PlayStation technical specifications</span> Overview of the technical specifications of the PlayStation

The PlayStation technical specifications describe the various components of the original PlayStation video game console.

References

  1. "Doom source code, under the GNU GPL". gamers.org. Archived from the original on 31 May 2023.
  2. "Doom3do/LICENSE at master · Olde-Skuul/Doom3do". GitHub . 17 December 2022.
  3. "NeXT Computers - Company - Computing History". www.computinghistory.org.uk. Retrieved 2022-03-29.
  4. Staff (December 29, 1997). "Doom II Source Available". PC Gamer US . Archived from the original on February 18, 1998. Retrieved November 20, 2019.
  5. https://web.archive.org/web/*/ftp://ftp.idsoftware.com/idstuff/source/* ftp://ftp.idsoftware.com/idstuff/source/%5B%5D
  6. Doom source code, under the GNU GPL - Doomworld /idgames database frontend
  7. The Doom source code from 3ddownloads.com Archived February 24, 2004, at the Wayback Machine - released in 1997, now under the GNU GPL v2-or-later
  8. "id Tech 1 (Concept)". Giant Bomb .
  9. Schuytema, Paul C. (August 1994). "The Lighter Side Of Doom". Computer Gaming World. pp. 140, 142.
  10. 1 2 Abrash, Michael. "Quake's 3-D Engine: The Big Picture" . Retrieved 22 August 2012.
  11. Apted, Andrew. "SPECIFICATION for GL-Nodes" . Retrieved 22 August 2012.
  12. Sanglard, Fabien. "Doom engine code review" . Retrieved 23 August 2012.
  13. Slime trail - The Doom Wiki