Adaptive Tile Refresh de Commander Keen

 (fabiensanglard.net)
2 puntos por GN⁺ 2023-07-29 | 1 comentarios | Compartir por WhatsApp
  • Adaptive Tile Refresh (ATR) es una técnica de scrolling que Commander Keen 1–3 usaba para evitar las lentas actualizaciones de pantalla completa en EGA, haciendo que se redibujaran solo los tiles modificados en lugar de toda la pantalla.
  • El modo EGA Dh guarda una pantalla de 320x200 con 16 colores dividida en 4 planos (C0~C3); escribir los 32 KiB de toda la pantalla por el bus ISA en cada frame solo llega a unos 5 fps, lo que dificulta una actualización a 60 Hz.
  • ATR maneja el movimiento vertical y horizontal dentro de una pantalla virtual usando los registros CRTC_START, OFFSET y PEL; cuando llega a un borde, hace un jolt para devolver el punto de referencia de la pantalla y sobrescribe en VRAM solo los tiles necesarios.
  • El costo de un jolt depende de cuántos tiles haya que redibujar; en un ejemplo de Commander Keen 1, de 250 tiles solo cambiaban 40 tiles, por lo que se redibujaba apenas el 16% de la pantalla, y el diseño de mapas con muchos tiles repetidos era clave para el rendimiento.
  • Commander Keen 4–6 reemplazó ATR por un método que aprovecha el wraparound de la apertura de VRAM de 64 KiB para seguir haciendo panning y dibujar solo las tiras de borde recién reveladas; en algunas tarjetas Super VGA esto generó problemas de compatibilidad al entrar en memoria no inicializada.

El límite de ancho de banda en EGA

  • Commander Keen funcionaba mejor en PCs con EGA (Enhanced Graphic Adapter), y la programación gráfica se hacía mediante registros de configuración y una ventana de memoria de 64 KiB mapeada a VRAM.
  • EGA guarda los datos internos en 4 planos: C0, C1, C2 y C3.
    • C0 guarda el bit menos significativo (LSB) de cada valor de píxel de 4 bits.
    • C3 guarda el bit más significativo (MSB).
    • Cada plano está compuesto por 200 líneas, con 40 bytes por línea.
  • La estructura de 4 bancos se diseñó para asegurar el ancho de banda necesario para seguir el ritmo de la pantalla CRT, y el CRTC lee 4 bytes en paralelo.
  • El modo EGA Dh que usa Commander Keen ofrece resolución de 320x200 y 16 colores.
    • No usa el método de reconfigurar las tintas entre 64 valores de color, como en el modo 10h.
    • Incluso en el modo Dh, se pueden cambiar los colores de la paleta dentro de los 16 colores básicos, algo que Commander Keen usa para sus efectos simples de fade in/out.

El redibujado de pantalla completa que evitó Adaptive Tile Refresh

  • El cuello de botella principal que resolvía ATR era el ancho de banda.
  • Escribir en cada frame los valores de 4 bits de 320x200 píxeles, unos 32 KiB, era una carga demasiado grande para el bus ISA.
  • Un bucle simple que actualiza toda la pantalla cada vez se queda en alrededor de 5 frames por segundo.
  • EGA también ofrece formas de escribir simultáneamente en los 4 bancos, pero aunque ayudan para limpiar la pantalla o para duplicar columnas en Wolfenstein 3D, no encajan con el problema de scrolling de Commander Keen.

Scrolling suave creado con registros

  • ATR primero crea dentro de la VRAM una pantalla virtual más grande que la pantalla visible, y mueve el área mostrada cambiando el valor de CRTC_START, que determina desde dónde lee el CRTC.
  • El scrolling vertical es relativamente simple.
    • Si se agregan 16 líneas arriba y 16 abajo de la pantalla visible, se usan 40 x 232 = 9,280 bytes por plano.
    • Para mover la pantalla una línea hacia arriba, se incrementa CRTC_START en 40 bytes.
    • Para moverla una línea hacia abajo, se decrementa CRTC_START en 40 bytes.
  • El scrolling horizontal usa en conjunto los registros OFFSET y PEL.
    • Al configurar OFFSET en 2, se agregan 16 bytes de padding entre líneas, dejando 16 píxeles de margen a cada lado de la pantalla virtual.
    • Si CRTC_START se incrementa en 1, por la estructura de planos la pantalla se mueve en bloques de 8 píxeles, demasiado brusco.
    • Horizontal Pel Panning, es decir, el registro PEL, permite saltar hasta 7 bits después de CRTC_START, haciendo posible el scrolling horizontal a nivel de píxel.
  • El movimiento horizontal real ajusta CRTC_START con el valor de la coordenada dividido entre 8, y configura PEL con el resto de la coordenada (% 8).

Jolt y actualización parcial por tiles

  • Al llegar al borde de la pantalla virtual, ATR realiza un jolt para volver a centrar la pantalla virtual.
  • Como redibujar toda la pantalla tarda unos 200 ms y cae a 5 fps, el jolt no hace un redibujado completo: sobrescribe solo los tiles que cambiaron.
  • Los niveles de Commander Keen están hechos con tiles de 16x16.
    • Cuando el artista dibuja tiles, el sistema de build asigna un ID único a cada tile.
    • El diseñador de niveles coloca IDs de tiles en un editor 2D para crear el mapa.
    • El motor lleva registro de qué ID de tile hay en la pantalla virtual.
  • En el momento del jolt, compara los IDs de tiles del estado actual de la pantalla virtual con los del estado objetivo ya vuelto a centrar.
    • Los tiles iguales se omiten.
    • Solo los tiles distintos se sobrescriben en VRAM.
  • La eficiencia del jolt es inversamente proporcional a la cantidad de tiles que haya que redibujar, así que los diseñadores del juego debían construir los tilemaps de modo que aparecieran muchos tiles repetidos.
  • En un ejemplo de Commander Keen 1, al moverse suavemente hacia la derecha hasta que se termina la pantalla virtual y ocurre un jolt de 16 píxeles hacia la izquierda, solo cambian 40 tiles de 250.
    • La proporción redibujada equivale al 16% de toda la pantalla.
  • Sobre el fondo se dibuja una capa de sprites.
    • El motor mantiene una lista de coordenadas de tiles sucios que fueron cubiertos por sprites.
    • En cada frame nuevo, recorre la lista de sucios, restaura los tiles de fondo y luego vuelve a dibujar los sprites.

Doble búfer y el drifting de la segunda trilogía

  • Para evitar artefactos visuales, todo el sistema se replica con dos framebuffers.
    • Mientras el CRTC lee uno, el otro puede escribirse en otra ubicación de la VRAM.
    • Cada búfer usa (320 + 32) * (200 + 32) * 4 / 8 = 40,832 bytes.
    • El doble búfer completo usa 40,832 * 2 = 81,664 bytes, más que los 64 KiB de la tarjeta EGA original de IBM.
  • Según VileR, la única placa con 64 KiB era la EGA original de IBM; la mayoría de los clones EGA aparecidos alrededor de 1986–1987 traían 256K, y para cuando salió Commander Keen casi no había tarjetas EGA con menos de 256K.
  • En Commander Keen 1–3 se notan en pantalla los patrones repetitivos que exige ATR, pero en Commander Keen 4–6 esa característica no es tan evidente.
  • La segunda trilogía de Keen aprovecha el comportamiento de wraparound por el cual, cuando CRTC_START llega al final del bloque de 64 KiB, vuelve al inicio del bloque.
    • La pantalla sigue haciendo panning y solo se dibuja la fila de tiles del borde que acaba de aparecer.
    • Al desaparecer el jolt, se reduce la necesidad de crear campos repetidos de colores similares.
  • Este método se parece más a una mejora que elimina el jolt que a una función nueva.
    • Como los dos elementos del doble búfer hacen drift por el espacio de VRAM a la misma velocidad, no se superponen.
    • En la mayoría de los casos funciona bien.
  • En algunas tarjetas Super VGA aparecieron problemas.
    • En tarjetas con implementaciones no estándar y más memoria, podía no producirse wraparound desde el final al inicio y, en su lugar, entrar en memoria real existente pero no inicializada.
    • En vez de manejar por separado varias tarjetas no estándar, Carmack optó por una solución sencilla: al llegar al final de la pantalla, aceptar un hitch y copiar toda la pantalla hacia arriba.
  • Es posible que esta técnica de drifting haya impedido almacenar tiles y sprites en VRAM para usar copias rápidas VRAM-to-VRAM, pero probablemente no fue un gran problema porque la cantidad que había que dibujar en cada frame era muy pequeña.

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-29
Opiniones de Hacker News

  • La suavidad del desplazamiento de Commander Keen 4~6 no tuvo rival en PC durante varios años, incluso después de que los juegos pasaran a gráficos de 256 colores.
    Gracias al asombroso trabajo técnico de John Carmack y al arte con paleta de 16 colores de Adrian Carmack, id terminó haciendo algunos de los juegos de plataformas para PC con mejor aspecto durante un tiempo en los años 90.
    Adrian Carmack no es pariente del Carmack más famoso, pero lo considero un maestro oculto de las paletas de 16 colores.

    • Se siente bastante raro que todos los juegos clásicos de Commander Keen se hayan desarrollado y lanzado entre diciembre de 1990 y diciembre de 1991.
      La velocidad de avance en gráficos y jugabilidad fue realmente enorme.
      El cambio desde el primer juego: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      El cambio hasta el último juego: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      Los jugué en persona cuando era niño, y había olvidado que todo estaba pasando tan rápido.
    • Si hablamos del juego de plataformas para PC con mejor aspecto durante un tiempo en los años 90, elegiría Prince Of Persia.
      No quiero menospreciar a Commander Keen, pero siento que los visuales y la mecánica de juego de PoP eran únicos para la época.
      Me pareció mágico cuando lo jugué por primera vez, alrededor de los 7 años, y sigue siendo mi juego de plataformas favorito, así que admito que tengo un sesgo.
      Claro que PoP no tiene nada de scroll, y esa parte es la magia negra de Commander Keen.
    • Quizá sea una mirada retrospectiva, pero gran parte de este desarrollo innovador parece bastante simple comparado con el desarrollo actual.
      “La memoria es lenta, así que redibujemos solo lo que cambió” hoy es una idea casi obvia.
      Aun así, las optimizaciones de los episodios 4~6 son interesantes. También es curioso que en los episodios 1~3 se hacía todo el trabajo asumiendo que el búfer no hacía wrapping, pero en realidad sí lo hacía, así que ese trabajo terminó siendo inútil.
    • ¿Y Jazz Jackrabbit? Ese juego también tenía un scroll VGA realmente suave.

  • Una vez hice un juego basado en tiles con DirectX 5 en Windows 98, y al principio implementé algo parecido a lo que describe este artículo.
    La situación era un poco más simple porque la pantalla no hacía scroll, aunque podía haber que redibujar muchos tiles.
    Al final eliminé todo ese código, porque al perfilar el costo de dibujar toda la pantalla en una tarjeta RIVA TnT, el tiempo era tan pequeño que ni siquiera podía medirlo.
    Me alegra haberme perdido la era EGA en el desarrollo para PC. Creo que en esa época no habría terminado nada.

    • A mí, por el contrario, me encantaba esa programación de bajo nivel.
      Optimizábamos con desplazamientos de bits en vez de multiplicaciones, escribíamos el código crítico en ensamblador y, a medida que los procesadores avanzaban, escribíamos 16 o 32 bits a la vez.
      Teníamos poco material, así que seguí aprendiendo con libros de la biblioteca local y disquetes con archivos txt.
      Era demasiado joven y me faltaba experiencia, así que no terminé nada, pero logré un scroll vertical suave, casi hice funcionar el scroll horizontal, e implementé doble búfer para un cubo 3D giratorio. Incluía búfer de profundidad, matemáticas y dibujo de polígonos línea por línea.
      Luego llegó DirectX y desapareció el punto de contacto con la máquina; un cubo 3D giratorio se volvió demasiado fácil y dejó de ser divertido.
    • Incluso en ese entonces ya se estaba abriendo una gran brecha entre las tarjetas gráficas más lentas y las más rápidas.
      El bus se ensanchó de 8 bits a 16/32 bits, las tarjetas gráficas empezaron a soportar posted writes para que la CPU esperara menos, y con CPUs más rápidas los sistemas veloces podían escribir una pantalla de 640x480x256 a más de 300 cuadros por segundo.
      En ese caso pudo haber sido un búfer de memoria del sistema en caché con copia por DMA, o quizá el blitter se encargaba del dibujo. Pero incluso en la época de Windows 98 había tarjetas 3D de gama baja cuyo acceso desde la CPU era muy lento, apenas mejor que una tarjeta vieja de bus ISA.
      Ahora que las resoluciones de pantalla se han vuelto tan altas, en cierto modo la situación se revirtió un poco. Aunque puedas redibujar una pantalla completa 4K a 60 cuadros por segundo, no es fácil llamarlo eficiente.
      Los juegos normalmente todavía redibujan todo, pero los compositores de escritorio hacen bastantes optimizaciones, como asignar capas dinámicamente a planos de hardware para reducir las áreas que se redibujan.

  • Trabajé en otra empresa de juegos en la misma época, y se me ocurrió por mi cuenta una técnica de scroll como el segundo enfoque.
    No creo que sea algo tan sorprendente. Si en aquel entonces estabas resolviendo el mismo problema, probablemente habrías llegado a una conclusión parecida.
    También hice mi propio driver de audio PWM para reproducir sonidos muestreados con el altavoz de la PC, y parece que todos los demás también lo hacían.
    La PC no recibió suficiente cariño antes de que todos nos pasáramos a las consolas. Demos como 8088 MPH de Hornet todavía me emocionan.

    • Si fue un juego lanzado, ¿podrías decir el título para poder compararlo? Estoy de acuerdo en que a la mayoría se le habrían ocurrido soluciones parecidas, pero me da curiosidad si el resultado al jugar se siente igual.
    • Si no era tan extraordinario, ¿por qué tantos de los juegos de plataformas con scroll de primer nivel de la época tenían tantos tirones?
      No es un requisito para que un juego sea divertido, pero la suavidad que mostraba Keen, especialmente en hardware de gama baja como por debajo de 10 MHz, era algo que te abría los ojos en esa época.
    • La fama muchas veces viene no de la invención en sí, sino de la capacidad de comercialización y marketing.
      Debe de haber innumerables grandes inventos que permanecieron desconocidos durante miles de años.
      Yo también “inventé” algo parecido a LinkedIn 10 años antes de que apareciera, pero no logré comercializarlo con éxito. Creo que la mayoría de los inventos nunca se hacen ampliamente conocidos.
      Por eso muchas startups empiezan con dos personas: una experta y una de negocios.
      Así que no está mal decirlo. Esta invención quizá no tenga nada de especial por sí sola, pero se volvió especial por la combinación de novedad, utilidad y comercialización exitosa.

  • El excelente libro Masters of Doom explica que Keen era un juego al estilo Mario, es decir, de desplazamiento horizontal.
    id le propuso esta tecnología a Nintendo como una opción para portar Mario a PC, pero Nintendo la rechazó, y así nació Keen.
    Fue un salto enorme para los juegos de PC y abrió una nueva era para los juegos en PC.
    Lo que todavía no termino de entender es qué era tan distinto entre la tecnología de la NES y la de la PC como para que Nintendo pudiera implementar el desplazamiento horizontal varios años antes que la PC.

    • EGA ofrecía, en esencia, un gran framebuffer.
      En los modos gráficos EGA podías dibujar cualquier cosa arbitraria que quisieras: líneas, círculos, píxeles individuales, etc., y estaba hecho para usarse así.
      Pero el desplazamiento no era gratis. Había que copiar memoria directamente y, como muestra el artículo enlazado, si lo hacías a fuerza bruta solo obtenías unos 5 fotogramas por segundo por la limitación de ancho de banda del bus ISA.
      La NES y otras consolas de 8/16 bits no estaban hechas para dibujar cosas arbitrarias. Estaban hechas para renderizar tiles.
      Bastaba con definir una cuadrícula de tiles de fondo y proporcionar un offset de desplazamiento. Los sprites funcionaban de forma parecida, pero podían moverse de manera independiente. Todo eso venía gratis a 60 fotogramas por segundo.
      La desventaja era que no podías renderizar fácilmente cosas arbitrarias. Por ejemplo, si querías pintar un solo píxel en algún lugar, necesitabas rodeos bastante fuertes.
      No era tanto un problema que Nintendo hubiera “descubierto” antes que IBM; más bien, IBM creó un sistema gráfico de propósito general para computadoras de propósito general y gráficos estáticos, que ofrecía control fino sobre cada píxel. Si miras una tarjeta EGA, es un dispositivo bastante enorme, con mucho silicio.
      En cambio, Nintendo creó un sistema gráfico dedicado mucho más simple, diseñado para mover tiles.
    • En realidad hicieron un port de SMB3 y se lo mostraron a Nintendo.
      Cuando Nintendo no lo aceptó, crearon assets nuevos y eso terminó convirtiéndose en Keen.
      El video del port está aquí: https://youtu.be/1YWD6Y9FUuw
    • No estoy del todo seguro, pero entiendo que la NES tenía un chip gráfico dedicado para manipular sprites, y en PC todo eso había que hacerlo por software.
    • El método del artículo consiste en usar un framebuffer de píxeles independientes para imitar por software los tiles que el hardware administra.
      Para el lado de NES, https://www.nesdev.org/wiki/PPU parece un buen punto de partida.
      El desafío principal no era “descubrir cómo hacer desplazamiento horizontal” en sí, sino adaptar un motor de juego con desplazamiento horizontal para que se viera bien dentro del espacio de memoria y las restricciones de ancho de banda de un sistema completamente distinto.
    • Creo que la NES y el GB eran basados en tiles.
      Como los juegos se hacían con sprites con capas, tenía bastante sentido como forma de “acelerar” 2D.

  • En la entrevista de Lex Fridman a John Carmack repasan todas las innovaciones principales de cada juego.
    Es un episodio realmente interesante y lo recomiendo mucho si tienen tiempo. Dura alrededor de 5 horas.

  • Todavía recuerdo la época en que creía conocer casi todos los secretos de Commander Keen Goodbye Galaxy.
    Mis compañeros de escuela solían pedirme, después de clases, que les contara los secretos de los niveles que jugaban en las computadoras de la escuela.

    • Qué envidia. En mi escuela, dentro de la gente con la que llegué a hablar, yo era el único nerd que había oído hablar de Commander Keen.

  • Si veo fabiensanglard.net, recomiendo de inmediato.

    • Él es una verdadera joya. Su libro sobre CPS1 también es excelente.
      Si alguien conoce otros blogs de juegos clásicos con profundidad técnica, me gustaría que los compartiera.
      https://nicole.express/ y https://sudden-desu.net/ también están entre mis favoritos.

  • Entendí cómo funcionaba el desplazamiento vertical ajustando el punto de inicio del framebuffer por scanline, pero al principio no me quedaba claro cómo era posible el desplazamiento horizontal sin retorcer demasiado el framebuffer.
    Pensándolo un poco más, me di cuenta de que se parece a dibujar una imagen sobre el lateral de un cilindro. Sin importar dónde dibujes el borde izquierdo de la imagen, siempre hay una forma de girar el cilindro y configurar CRTC_START y el registro PEL para ver la imagen completa con nitidez.
    También me pareció interesante la parte de que “al llegar al borde de la pantalla, usaban una solución sencilla: aceptaban un tirón y copiaban toda la pantalla hacia arriba”.
    Recuerdo que al iniciar Keen normalmente aparecía un mensaje como “VGA compatibility mode enabled”, y siempre me pregunté qué significaba.

  • Commander Keen era un jueguito realmente adorable
    Tengo que buscar una forma de volver a ejecutarlo
    Pero ¿cuál sería la mejor manera de hacerlo? Hace unos 20 años que no uso Windows desde que me volví “adulto”; ¿cómo podría jugarlo en Debian?

    • Se puede jugar directamente: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • No estoy de acuerdo. Este era un juego para niños que, por alguna razón, podían usar una computadora pero no tenían Nintendo
      En esa época las computadoras costaban como 10 veces más que las consolas, así que por lo general era porque los adultos tenían ideas muy firmes sobre lo que debía hacer el niño
      Comparado con los juegos de NES y Genesis, le falta alma. En su momento me gustaba, pero lo volví a probar hace poco en DosBox y sentí claramente que no hay punto de comparación
    • DosBox corre muy bien los juegos VGA antiguos y funciona en casi cualquier plataforma, incluso dentro del navegador: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Supongo que con DosBox
    • Commander Keen y Jill of the Jungle fueron los juegos que me introdujeron a la PC en su momento. Qué buenos recuerdos

  • Hace algunos años implementé el segundo método, y aun dibujando solo el borde delantero era muy lento
    Eso sí, lo escribí en C y nunca aprendí bien programación en ensamblador
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...