Generación de laberintos en BERZERK

[Bubu]

¡Jarl, torpedos!

Resulta que me ha dado por investigar el Berzerk, uno de mis 25 juegos favoritos arcades, y quiero profundizar en cómo monta el laberinto.




La cosa según he leído es como sigue:

- Se asignan 8 puntos en pantalla por donde salen los muros, 4 arriba y 4 abajo
- Cada punto saca un muro en una de las 4 direcciones: N, S, E, O
- A cada uno de esas 4 direcciones le asociamos un valor: N=00, S=01, E=10, O=11
- Una pantalla queda definida por 8 muros
- Cada muro se obtiene mediante un número de 16 bits, quedándonos con los 2 bits de menos peso del byte alto
- Para obtener un número de 16 bits se usa esta fórmula: X * 7 + $3153, dos veces
- Inicialmente X = $3153

Con esto, vamos a ver qué nos sale. Como X=$3153, tenemos que $3153 * 7 + $3153 = $8A98. Ahora lo volvemos a aplicar: $8A98 * 7 + $3153 = $FB7B, el resultado sería $FB7B. Ese número en binario es el 1111 1011 0111 1011, que si nos quedamos sólo con los bits 8 y 9, nos quedamos pues con 11, cuya dirección es oeste. Ya tenemos el 1er muro de los 8 muros.

Vamos ahora a por el 2º muros. Para ello, la formulita:

$FB7B * 7 + $3153 = $11B0
$11B0 * 7 + $3153 = $AD23

cuyos bits 8 y 9 son el 01, que se corresponde con muro al sur.

Y así 8 veces. La pantalla quedaría tal que esta:





OK. Hasta aquí está claro. Como veis al final una pantalla son 16 bits (2 bits por muro). Ahora hay que calcular la pantalla de al lao, y después la de al lao, etc. El BERZERK resulta que calcula 1024 pantallas, y las almacena en una matriz de 32 x 32 (que son 1024), de esta manera:



Y estas 1024 pantallas las calcula nada más arrancar el juego. Por eso los que hayáis juegado al BERZERK habréis notado cómo tarda varios segundo en arrancar, precisamente por eso, porque está a jierro calculando números.

Me queda por saber qué pasa si me matan, e inicio de nuevo una partida. ¿En qué pantalla aparezco? De esto nu tengo ni idea.

[oscarbraindead]

Realmente interesante. El Berzerk es uno de mis juegos preferidos y lo he intentado programar alguna vez (http://computeremuzone.com/ficha.php?id=283 aquí está disponible una versión para GBA que hice hace la torta de años).
La generación de las pantallas era un poco lío. No recuerdo si en su día busqué y no encontré cómo lo hacía el Arcade o ni siquiera lo busqué y me lié a hacer mi propia rutina, más compleja y con peores resultados que ésta.
Creo que cuando acabe con algunos de los fregados con los que estoy ahora intentaré una versión para PC...

Muchas gracias por la información!
Saludos

[Bubu]

Me alegro que te guste. Yo alucino con el método: jamás se me hubiera ocurrido que con 16 bits tuvieras una pantalla. El método de 2 bits por muro es buenísimo.
Ahora me surje una duda: como sabes, al salir de la habitación por la derecha, apareces en la izquierda de la siguiente, pero esa puerta está cerrá pa que no puedas volver a la anterior y quedarte ahí buclao. Así las cosas, ¿qué pasa si hago un cuadrao? Uséase, salgo por la derecha, después por arriba, después por la izquierda y después p'abajo. ¿Volvería a la primera pantalla?

Procedo a catar...

[Bubu]

Catado: efestivamente se repite la pantalla al hacer un cuadrao, pero con robots más difícles. Me queda totalmente claro cómo funciona el laberinto. Bueno, casi... Lo que nu sé es cuando echo una 2ª partida, en qué pantalla empieza. ¿Depende del tiempo que tarde en echar la moneda? Quiero decir, una especie de LD A, R

[josepzin]

Me encanta cuando destripan estos clásicos!

[jltursan]

Muy interesante, la verdad es que es una idea muy simple y muy de la época, cuando todavía había que ingeniarselas

Ahora, precisamente en la pantalla que pones veo sólo 7 muros y me pregunto, ¿habrá algún control de direcciones de muro prohibidas?, me explico, en la captura parece que un punto ha generado sur y el inmediatamente debajo de él, norte, el resultado es que sólo se ve un muro, no dos. Si hubiese extrema mala suerte podría quedar una pantalla extrañuja con sólo cuatro muros.
Entiendo que en el juego no se hace ese control, la probabilidad no es lo suficientemente grande como para merecer ese gasto de código.

[Bubu]

Pues no, ese caso no está controlado en el código, pero como se ve en el mapa no se producen esos casos, entiendo que eso es debido a la fórmula:

$3153 + $07*N

Verás que todos los números son impares, y seguramente esto hará que al aplicarlo 2 veces y tomar sólo 2 bits, no se repitan consecutivamente. Yo creo que la elección de ese número $3153 es fundamental, así como el factor 7, pero esto lo tengo que demostrar.
De todas formas peor hubiera sido que el último número de 16 bits de una pantalla coincidiera con su primer número de 16 bits al pasarlo por la fórmula. Esto haría que llegaría un momento en el que todas las pantallas serían iguales.

Es increíble que con una fórmula tan simple, se generen 1024 pantallas de un laberinto, sin que sean simples ni repetitivas.