• Id Tech 1

{{lowercase}}
{{Infobox Software
| name = id Tech 1
| logo = 
| screenshot = 
| caption = 
| collapsible = 
| author = 
| developer = [[id Software]]
| released = 
| latest release version = 
| latest release date = 
| latest preview version = 
| latest preview date = 
| frequently updated = 
| programming language = [[C (programming language)|C]]
| operating system = 
| platform = 
| size = 
| language = 
| status = 
| genre = [[Game engine]]
| license = [[GNU General Public License]]
| website = 
}}

'''id Tech 1''',<ref>[http://www.firingsquad.com/games/id_software_rage/ id Tech 5 First Look]</ref> formerly known as the '''''Doom'' engine''', is the [[game engine]] that powers the [[id Software]] [[video game|games]] ''[[Doom (video game)|Doom]]'' and ''[[Doom II]]''. It is also used by ''[[HeXen]]'', ''[[Heretic (computer game)|Heretic]]'', ''[[Strife (game)|Strife]]'' and ''[[Doom WAD#Total conversions|HacX]]'', and other games produced by licensees. It was created by [[John Carmack]], with auxiliary functions written by [[Mike Abrash]], [[John Romero]], [[Dave D. Taylor|Dave Taylor]] and Paul Radek. Originally developed on [[NeXT]] computers, it was [[porting|ported]] to [[DOS]] for ''Doom'''s initial release and was later ported to several [[game console]]s 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.<ref>[ftp://ftp.idsoftware.com/idstuff/source/ The ''Doom'' source code] - released in 1997, now under the [[GNU General Public License]] from Id Software's FTP Site</ref><ref> [http://www.3ddownloads.com/showfile.php3?file_id=7430 The ''Doom'' source code from 3ddownloads.com] - released in 1997, now under the [[GNU General Public License]]</ref>
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. In its time, ''Doom'' was revolutionary in its ability to provide a fast [[texture-mapped]] environment that passed for 3D.

==Doom level structure==
<div style="float: right; margin: 0 0 1em 1em; padding: 0.5em; background: #fffff4; border: 1px solid #ddddbb; width: 250px;">
A simple setup demonstrating how ''Doom'' represents levels internally

[[Image:Doom mapformat map.png|240px|thumb|Map view in editor]]
[[Image:Doom mapformat screen.png|240px|thumb|In-game view]]

</div>

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 [[vertex (geometry)|vertex]], which represents a single 2D point. Vertices (or "vertexes" as they are referred to internally) are then joined to form [[line (mathematics)|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.

===Sectors===
Each sector contains a number of properties: a floor height, ceiling height, light level, a floor [[Texture mapping|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). 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 is really a very clever way of sorting 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 wasted drawing objects that are not visible and as a result maps can become very large without any speed penalty.

==Rendering==
===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 (video game)|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 [[Row-major order#Column-major order|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 fill]]-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 the exact 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 the message, "No more visplanes!" 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.

===Things ([[sprite (computer graphics)|sprite]]s)===
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 Id Tech 1 engine ==
Though the Id Tech 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" Id Tech 1 engine games are [[Doom (video game)|Doom]], [[Heretic (video game)|Heretic]], [[Hexen]] and [[Strife (video game)|Strife]].
* Games that were built directly on the Id Tech 1 engine.
** ''[[Doom (video game)|Doom]]'' (1993)
** ''[[Doom 2]]'' (1994)
** ''[[Heretic (video game)|Heretic]]'' (1994)
** ''[[Hexen]]'' (1995)
** ''[[Strife (video game)|Strife]]'' (1996)
* Games that were based on the ''Doom 1/2'' code
** ''[[Doom WAD#Total conversions|HacX]]'' (1997)
** ''[[Chex Quest]]'' (1996)
** ''[[Chex Quest 2]]'' (1997)

== See also ==
{{Portal|Free software|Free Software Portal Logo.svg}}
{{Portal|Video games|Gamepad.svg}}
*[[List of game engines]]
*[[First person shooter engine]]
*[[id Tech]]
*[[Quake engine]]
*[[Quake (series)]]
*[[List of first-person shooter engines]]

==References==
{{Reflist}}
* [http://www.faqs.org/faqs/graphics/bsptree-faq/ BSP Frequently Asked Questions]
* [http://glbsp.sourceforge.net/specs.php GL nodes specification]
* [http://www.doomworld.com/classicdoom/utils/editors.php Utilities to edit Doom and Doom2]
* [http://fabiensanglard.net/doomIphone/doomClassicRenderer.php Doom engine code review] by [[Fabien Sanglard]]

== External links ==
* {{Wikia|doom|Doom Wiki|Doom engine}}
* {{Wikia|doom|Doom Wiki|Doom rendering engine}}
* [http://www.uvlist.net/groups/info/doomengine Doom engine full games list]

{{DOOMgames}}

[[Category:Doom (franchise)]]
[[Category:Free game engines]]
[[Category:1993 introductions]]

[[da:Doom-motor]]
[[de:Doom-Engine]]
[[es:Doom Engine]]
[[fr:Id Tech 1]]
[[it:Doom Engine]]
[[hu:Doom-motor]]
[[pl:Id Tech 1]]
[[ru:Doom engine]]
[[fi:Doom-pelimoottori]]
[[sv:Doom (datorspelsmotor)]]
[[zh:毁灭战士引擎]]