The Doom engine: How to run a 3D game on early 90s computers

Doom is the classic first person shooter game that came out in 1993 where you play as a space marine shooting down demons in order to quickly clear levels. This game is one of the most iconic and classic video games to ever be released as it not only put first person shooters on the map, but introduced many people to 3D video games. It was such a popular game that the games creator, id Software, was making $100,000 per day only with the game sales.

The game was also of utmost importance due to the fact that it was able to run on almost any early 90s computer, which lacked video cards due to them being highly expensive and wheneret even made to use the internet or windows, as those came out during the 1990s. But then how are they able to run so well on such primitive hardware? This is due to the steps the company took to reduce the computational power needed to render 3D environments.

Before we can truly begin talking about the rendering in Doom we must first talk about how Doom structures its level. The game's levels are made in 2D which is the reason none of the maps include a room over a pre existing room. These 2D levels are made up of vertices, 2D points, which are joined together by lines called linedefs, giving a room its specific shape. The areas in between these linedefs are called sectors and they will hold values that determine the level, brightness and textures of the ceiling and floors. Objects in these scenes such as enemies, powerups, the player and scenery are called things and can be placed in these sectors.

Linedefs can be defined as either one-sided or two-sided and each one has its own set of properties. One-sided linedefs are solid walls and are used to determine the outsides of a room. On the other hand, two-sided linedefs are used for a variety of different purposes such as making a room have multiple floor and ceiling or floors and ceiling at different heights, making stairs, doors and elevators. Unlike the one-sided linedefs they can be made up of 3 textures divided into upper, middle and lower or it can even have no textures when you simply want to separate a room in multiple sectors. How Doom categorizes its environments will be extremely important for explaining how it renders them.

To talk about the rendering of the environment itself we must first understand how Doom decides what it has to render and in what order, this is done using binary space partitioning (BSP). Firstly, a root node is determined, which in the case of Doom is the entire level. Then, this root node is divided into sub notes and in the process also divides the linedefs into segs. This process is repeated until we arrive at convex polygons, as dividing it further would be unnecessary, these are called subsectors and will have various segs bound to it. With all this data, a binary tree is constructed, with the trunk being the root node and the leaves being the subsectors. Thus, when Doom goes to render a level it starts at the root node and goes to the child node nearest to the camera, it will then continue through the child nodes until it reaches a subsector and then it will draw that specific subsector. BSP allows Doom to efficiently order its environments and with the simple algorithm they can easily render everything in a level, thus making it easier for computers to run the game. This process is a lot more complex than what has been said above however, if you want to know more further reading is provided at the end of the article.

BSP are extremely useful when rendering walls, as they will be drawn on the segs of each subsector, starting from the closet one. Walls are rendered as vertical strips, due to the camera angle being fixed on the Z-axis making it so all pixels are an equal distance from the camera, making it so less computational power is wasted on re-rendering these walls as perspective changes. Rendered walls are also saved in a list which allows them to be quickly accessed in case a player turns or to be used when deciding to cut off the sprites of a particular enemy.

The algorithm used for floors and ceilings although effective isn't as interesting or complex as the BSP used for walls. Each floor and ceiling is divided into a visplane, which represents the horizontal run of sector at a particular height, light level and texture. If two visplanes happen to be the same they are then merged to help lessen the computational power needed, as instead of the computer having to run the algorithm twice to accomplish the same thing it will only do it once. The rendering of a visplane happens by simply filling in the sector they are currently in and cutting off when they come into contact with another visplane. Unlike wall floors and ceilings are rendered as horizontal strips, as it provides the same benefits as rendering walls as vertical strips, since it allows them to maintain the same distance and perspective from the fixed camera.

Finally, objects have only a few interesting techniques used to help lower computational power needed, as they are a lot lighter to run than the huge environments present in Doom. In terms of rendering they are done fairly similar to any other object present in a 3d game, however unlike them the characters have an infinite z axis. This was done to prevent enemies or players from stacking on one another, since this would cause the processing power needed for the computer to rise exponentially. It is also important to note that although players can't pass over enemies, bullets can, since the way that they are coded is to simply move in a relatively straight line until they hit a wall or a target.

Doom has taken various steps in order to make the game playable on all PC’s. This is especially true when we take into account the lengths taken in order to save computational power when rendering the environment such as using a BSP to determine the order of each sector and the limits of cameras and character stacking which decrease the needed computational power to render a level. This allowed the game to be playable on these simple computers and showed the world the potential of 3D games and the popularity of first person shooter games which can still be seen today through the popularity of games like Call of Duty.

Further reading:

https://arstechnica.com/gaming/2019/12/how-much-of-a-genius-level-move-was-using-binary-space-partitioning-in-Doom/2/

References

"How Much Of A Genius-Level Move Was Using Binary Space Partitioning In Doom?". Ars Technica, 2019, https://arstechnica.com/gaming/2019/12/how-much-of-a-genius-level-move-was-using-binary-space-partitioning-in-Doom/2/.

"Doom Rendering Engine". Doom Wiki, https://Doom.fandom.com/wiki/Doom_rendering_engine.

Gershgorn, Dave. "The Game That Kicked Off A Video Game Revolution Turns 25 Today". Quartz, 2018, https://qz.com/1490069/Doom-the-game-that-kicked-off-a-video-game-revolution-turns-25-today/.

Pearson, The. "1990'S Computers From The People History Site". Thepeoplehistory.Com, https://www.thepeoplehistory.com/90scomputers.html.