Estructuras de datos en juegos antiguos.

Tengo curiosidad por las estructuras de datos utilizadas al programar juegos antiguos como Super Mario Brothers para NES y Super Mario World para SNES. Tengo entendido que los juegos de este período se escribieron en asamblea. ¿Los programadores definieron / usaron alguna estructura de datos?

Por ejemplo: cuando aparece un grupo de monedas en la pantalla, ¿cómo se almacenan? ¿Los programadores solo usaron matrices? ¿O tal vez tenían listas enlazadas?

¡Salud!

Editar : Estoy interesado en varios enfoques ... no necesariamente un enfoque universal.

Edición 2 : en algunos de mis juegos utilizo un enfoque (potencialmente malo) hacia las colecciones y quiero saber si alguno de los juegos más antiguos utilizó un enfoque similar. Me gusta hacer lo siguiente:

// statically allocated arrays (max number of coins is 4)
int coinsXs[4] = {0, 0, 0, 0};
int coinsYs[4] = {0, 0, 0, 0};

// bitset that keeps track of which coins are active
int coinsActive = 0;

// ...

// update the active coins in an update function
for(int i = 0; i < 4; i++){
    if(coinsActive & (1 << i)){
        // update ith coin
    }
 }

data-structure MrDatabase
fuente

No hay una respuesta universal; todo se reduce a cómo un programador dado implementó la solución para un problema dado.

Ed S.

Si bien no creo que todos esos juegos hayan sido escritos en ensamblador, diré que era bastante común que los programadores de ensamblaje recolectaran sus pequeños componentes para reutilizarlos para copiar / pegar de un programa a otro. ¿Cuántas veces te gustaría escribir la función printf () después de todo? :)

James

Buen punto. Tengo mucha curiosidad sobre las colecciones asignadas dinámicamente frente a las colecciones asignadas estáticamente

MrDatabase

¿Qué problema específico no se tiene? ¿Por qué te importa lo que hacen los viejos juegos?

Tetrad

Lo que tienes en tu segunda edición es un ejemplo de un diseño de "estructura de matrices", que sigue siendo común incluso en los juegos modernos, ya que tiene beneficios para el paralelismo y la operación SIMD. Sony hizo una presentación hace un par de años sobre cómo la forma tradicional de C ++ de estructurar datos puede tener serios costos de

rendimiento

Respuestas:

Incluso en los días de 16 bits, las consolas de juegos eran básicamente computadoras pequeñas e integradas que ejecutaban software en tiempo real, y las estructuras de datos que utilizamos son las mismas que encontraría en cualquier parte de la informática: matrices, matrices, montones, árboles. No hay muchas listas vinculadas porque son muy lentas (las búsquedas indirectas tienen una latencia larga).

La diferencia es que antes del STL, y con un rendimiento tan crítico, ¡generalmente teníamos que escribir las estructuras y los algoritmos nosotros mismos!

David Braben hizo una conferencia divertida en el GDC de 2011, donde habló sobre todos los trucos locos que usó para instalar Elite en un BBC Micro en 1984. Puedes verlo gratis en el GDC Vault .

Crashworks
fuente

Frio. ¿Usó matrices asignadas dinámicamente? ¿O la mayoría tenía un tamaño estático? Tengo curiosidad por las situaciones en las que, por ejemplo, cinco monedas aparecerían en la pantalla y permanecerían en la pantalla hasta que el jugador las recogiera (o se desplazaran fuera de la pantalla).

MrDatabase

@MrDatabase: asignaciones estáticas siempre que sea posible. Para casos como los que usted describe, a menudo solo tendríamos una matriz estáticamente asignada de, por ejemplo, 32 monedas posibles que podrían existir. Cuando las monedas llegaran al mundo, llenaríamos un lugar en la matriz. Cuando se fueron, lo aclaramos. La asignación dinámica no estaba disponible, simplemente evitamos usarla porque cuando solo tienes 2 MB de RAM, ¡realmente necesitas garantizar que tu programa se ejecute en memoria constante!

Crashworks

Frio. Hago algo similar (ver edición # 2 de la pregunta). En mi función de actualización, verifico el bitset "coinActive" if(coinsActive)antes de pasar por maxNumCoins y actualizar. De esta manera, evito completamente el ciclo si hay cero monedas activas.

MrDatabase

+1 debido al enlace de GDC Vault. La charla postmortem Popolous de Peter Molyneux debe ser la charla más divertida que he visto.

TravisG

MeDataBase: copia el último objeto activo en la ranura que estaba ocupada por una moneda que se volvió inactiva (es decir, si tiene 10 monedas, la moneda 5 se vuelve inactiva, copie la moneda 10 en la ranura 5 y disminuya las monedas nocivas) puede simplemente iterar hacia arriba para numCoins y actualizar todos esos elementos. No necesitarías el 'si'. Por supuesto, esto solo funciona si las monedas inactivas no necesitan mantener el estado y si el orden de actualización no es importante (el estado podría mantenerse si la matriz almacena punteros en monedas y no en monedas reales, pero luego obtiene un comportamiento de caché disperso que es probablemente peor que el 'si')

Kaj

Aquí hay una discusión interesante en GameDev.net para el código fuente de Super Mario Bros: Código fuente de Super Mario

pek
fuente