Doom Engine

Doom Engine
	Parte de id Tech
Información general
Tipo de programa	software libre
Autor	id Software
Desarrollador	id Software
Modelo de desarrollo	Motor de videojuego
	GNU General Public License, versión 2.0 o posterior; licencia privativa; Licencia MIT;
Información técnica
Programado en	C, Ensamblador
Plataformas admitidas	Mac OS Classic; Commodore Amiga; Super Nintendo Entertainment System; Sega 32X; Sega Saturn; 3DO Interactive Multiplayer; PlayStation; Game Boy Advance; Atari Jaguar; NEXTSTEP;
Serie id Tech
Enlaces
	Repositorio de código
	[editar datos en Wikidata]

Doom Engine o id Tech 1 es el motor gráfico que id Software usó para sus videojuegos Doom y Doom II. Este motor gráfico también es usado por Hexen, Heretic, Strife y HacX, y otros juegos producidos por licenciatarios. Fue creado por John Carmack, con las funciones auxiliares escritas por Michael Abrash, John Romero, Dave Taylor y Paul Radek. Originalmente desarrollado en computadoras NeXT, fue portado a DOS para el lanzamiento inicial de Doom, para después ser portado a otras consolas y sistemas operativos.

El código fuente para la versión Doom de Linux fue lanzado al público en 1997 bajo una licencia que garantiza los derechos de uso del motor mientras no sea para uso comercial, y fue relanzado bajo la licencia GNU en 1999. Las versiones de Doom no oficiales que han sido creados desde entonces ha permitido que el juego corra en sistemas operativos que antaño no eran soportados e incluso mejorando la funcionalidad del motor y agregando en algunas conversiones nuevas características.

No es un verdadero motor "3D", ya que no es posible mirar arriba y abajo adecuadamente, y 2 sectores no pueden ser traslapados, pero es un elegante sistema que permite renderizado en pseudo-3D. En su tiempo Doom fue revolucionario en su habilidad de proveer un ambiente 3D rápido por mapeado de texturas.

Estructura de los niveles de Doom

Una disposición simple mostrando como *Doom* representa los niveles internamente.

Visto desde una perspectiva aérea (de arriba abajo), todos los niveles de Doom son de dos dimensiones, demostrando una de las limitaciones clave del motor gráfico de Doom: no es posible tener "cuartos sobre cuartos". Esta limitación tiene su ventaja: puede mostrarse fácilmente un "Modo Mapa", el cual representa las paredes y la posición del jugador, tal como se muestra en la imagen de la derecha.

Objetos Básicos

La unidad básica es el Vertex, el cual representa un punto en 2D.
Los vértices (o "vertex" como son referidos internamente en el motor) son unidos para formar líneas, conocidas como "linedefs".
Cada linedefs puede tener uno u dos lados, los cuales son conocidos como "sidedefs".
Los sidedefs son agrupados para formar polígonos; estos son llamados "sectors". Los sectores representan áreas particulares del nivel.

Sectors (Polígonos)

Cada sector contiene un número de propiedades: una altura del suelo, altura del techo, nivel de iluminación, la textura del suelo y la textura del techo. Para tener una iluminación diferente en un área particular, un nuevo sector debe ser creado específicamente para esa área con un nivel de iluminación diferente. Los linedefs de un lado representan "paredes sólidas", mientras los linedefs de dos lados representan rectas "puente" entre sectores (o polígonos).

Sidedefs

Los Sidedefs son usados para colocar texturas para la pared; estos están totalmente separados de las texturas del suelo y el techo. Cada sidedef puede tener 3 texturas; estas son llamadas texturas altas, medias y bajas. En los linedefs de un lado solo la textura media es usada para las texturas en la pared. En los linedefs de dos lados la situación es más compleja. Las texturas altas y bajas son usadas para llenar los huecos cuando sectores adyacentes tienen diferente altura con respecto al suelo o al techo: por ejemplo las texturas bajas son usadas para escalones. Los sidedefs pueden tener textura media también, pero la mayoría no lo usan; esta es usada para "colgar texturas en medio del aire. Por ejemplo cuando una textura transparente en barra es vista formando una jaula es un ejemplo de una textura media en un linedef de dos lados.

Cosas

Finalmente, hay una lista de objetos en el nivel que en Doom son conocidas como cosas ("things"). Estas son usadas para situar al jugador, monstruos, powerups, etc. Cada cosa tiene una coordenada en 2D, como ocurre con los vértices. Las cosas son automáticamente colocadas en el suelo o en el techo dependiendo de su tipo.

Esto es solo un vistazo a la estructura básica de los niveles de Doom, la mayoría de las estructuras de datos se cargan con propiedades extra, como por ejemplo, desplazamiento de texturas y propiedades especiales para el modo de juego.

Binary space partitioning (Particionado Binario del Espacio)

Doom hace uso de un sistema conocido como BSP (Binary space partitioning). Una herramienta es usada para generar los datos BSP para el nivel de antemano. Dependiendo del tamaño del nivel este proceso puede tomar bastante tiempo, esto se debe a que no es posible mover las paredes en 'Doom; mientras las puertas y elevadores se mueven arriba y abajo, ninguno de ellos se mueve hacia los lados.

El nivel es dividido en un árbol binario: cada localización en el árbol es un "nodo" el cual representa un área particular del nivel (con el nodo raíz representando el nivel entero). En cada rama del árbol hay una línea divisoria la cual particiona el nodo en dos subnodos. Al mismo tiempo la línea divide los linedefs en segmentos de línea llamados "segs".

Las hojas del árbol son polígonos convexos, donde no es útil dividir el nivel. Estos polígonos convexos son referidos como subsectores (o "SSECTORS"), y están unidos a un sector particular; cada subsector tiene una lista de segs asociados.

El sistema BSP realmente es una forma muy inteligente de ordenamiento de subsectores con el orden correcto para renderizado, el algoritmo es muy simple:

Comienza en el nodo raíz.
Traza los nodos hijo de este nodo recursivamente. El nodo hijo más cercano a la cámara es trazado primero. Esto puede encontrarse mirando en cual lado de la línea divisoria del nodo esta la cámara.
Cuando un subsector es alcanzado, se traza (dibuja).

El proceso está completo cuando la columna completa de píxeles es llenada (no quedan más huecos). Este ordenamiento asegura que no se desperdicie tiempo dibujando objetos que no están visibles, como resultado los mapas pueden ser muy grandes sin degradar la velocidad a la que corre el juego.

Renderizado

Trazado de paredes

Todas las paredes en Doom son dibujadas verticalmente, es por eso que no es posible mirar arriba y abajo adecuadamente. Pero se puede agregar una forma de ver arriba y abajo, por un método llamado "y-shearing" el cual emplean muchas conversiones modernas de Doom. Esto se hace incrementando la resolución vertical, y luego colocando una "ventana" en ese espacio. Al mover la ventana arriba y abajo es posible dar la ilusión de mirar arriba y abajo pero esto podría distorsionar la perspectiva del jugador.

El motor gráfico de 'Doom' renderiza las paredes al igual que el árbol BSP, dibuja subsectores por orden de distancia de la cámara, así que el segs más cercano es dibujado primero. Conforme los segs son dibujados, son almacenados en una lista de enlazado. Esto es usado para unir otros segs más tarde, previniendo trazado de más. También es usado para unir las orillas de los sprites.

En cuanto el motor gráfico llega a una pared sólida (de un lado) en alguna coordenada x en particular, no se necesitan dibujar más líneas en esa área. Para las uniones el motor gráfico guarda un "mapa" de áreas de la pantalla en donde paredes sólidas han sido alcanzadas. Esto da tiempo al motor para unir partes del nivel completamente, lejos del punto de vista del jugador.

El formato gráfico de Doom guarda las texturas de las paredes como sets de columnas verticales, esto es útil a la hora de renderizar, ya que las paredes son dibujadas como muchas columnas de texturas unidas (como un tapiz).

Suelo y techo

El sistema para dibujar suelos y techos ("planos") es menos elegante que el usado para las paredes. Los planos son dibujados por medio de un algoritmo parecido al "flood fill (algoritmo de relleno por difusión)", debido a esto si se usa mal un constructor de BSP algunas veces el nivel tendrá "huecos" cuando la perspectiva pase por las orillas del suelo o el techo. Es por esto que cuando el jugador emplea el cheat de noclip (no uniones en las paredes), parece que el suelo y el techo se extienden en el vacío.

El suelo o el techo son dibujados como planos ("visplanes"). Las texturas de los planos en pantalla se disponen horizontalmente, ya sea un suelo o techo a una altura en particular, nivel de iluminación y textura (si dos sectores adyacentes tienen el mismo tipo de textura se fusionan en un solo visplano). Cada posición x en el visplano tiene una línea vertical particular de textura que debe ser dibujada.

Debido a esta limitante de dibujar una línea vertical en cada x posiciones, algunas veces es necesario dividir un visplano en múltiples visplanos. Por ejemplo al mirar un suelo con dos cuadrados concéntricos, el cuadrado más cercano dividirá verticalmente al suelo circundante. En el rango horizontal donde el cuadrado más cercano es dibujado 2 visplanso se necesitan para el suelo circundante.

Esto nos conduce a una de las limitantes clásicas conocidas del Doom, la cual frustro a muchos creadores de mapas por mucho tiempo. DOOM contiene un límite estático respecto al número de visplanos que puede manejar, si se excede de ese número el programa colapsara y devolverá un mensaje en DOS: "No more visplanes!". La manera más fácil de provocar la salida de este mensaje es creando un suelo con patrones tipo ajedrez, esto creara un gran número de visplanos.

Conforme los segs son renderizados, los visplanos son agregados también, extendiéndose desde los bordes verticales de la pantalla. esta extensión ocurre hasta que alcanzan algún visplano existente. Debido al modo en que trabaja, el sistema depende de los segs hayan sido renderizados en orden por el motor gráfico en general. Es necesario dibujar los vsiplanos más cercanos para que se puedan quitar los que se encuentran más lejanos. Si no es detenido este proceso el suelo y el techo se correrán ("bleed out") en las orillas de la pantalla como se describió previamente. Finalmente los visplanos forman un "mapa" de las diferentes áreas de la pantalla en las que dibujara texturas en particular.

Mientras los visplanos son construidos esencialmente de "tiras" (strips) verticales, el renderizado de bajo nivel actual es ejecutado en la forma de "spans" horizontales de textura. Después de que todos los visplanos son construidos pasan a ser convertidos en spans los cuales son los que rendearan la pantalla. Esto parece ser una compensación: es fácil construir visplanos como tiras verticales, pero debido a la naturaleza de como las texturas del suelo y el techo aparecen, es más fácil el dibujarlas como tiras horizontales. Debido a la naturaleza de los visplanos, la conversión es muy trivial.

Cosas (Sprites)

Cada sector en el nivel está unido a una lista de cosas guardadas en ese sector. Conforme cada sector es dibujado los sprites son colocados conforme la lista del sector. Si no se encuentran los sprites en el campo de visión, estos sprites son ignorados.

Las orillas de los sprites son unidas por chequeo de las listas de segs previamente dibujados. Los sprites en Doom son guardados en el mismo formato de columna base al igual que las paredes, lo cual es útil a la hora de renderizar. Las mismas funciones que se usan para dibujar paredes se emplean para dibujar sprites.

Mientras subsectores son guardados para estar en orden, los sprites en ellos no. Doom guarda una lista de sprites a ser dibujados ("vissprites") y ordena la lista antes del renderizado. Sprites lejanos son dibujados antes de los cercanos, esto causa que se dibuje de más pero usualmente es insignificante.

Hay un detalle final en las texturas medias en líneas de 2 lados, usadas en barras transparentes por ejemplo. Estas son mezcladas y dibujadas con los sprites al final del proceso de rendereo, en lugar de hacerlo con las otras paredes.