Páginas

Lógicas masivas

Descripción de la técnica de programación de "lógicas masivas" (mas información en el libro 8 bits de poder, que puedes descargar de https://github.com/jjaranda13/8BP )

La clave de lograr velocidad en muchos sprites es utilizar la técnica que he bautizado como “lógicas masivas”. Esta técnica consiste fundamentalmente en ejecutar menos lógica en cada ciclo de juego (lo que se denomina “reducir la complejidad computacional”) y para ello hay dos opciones:
  • Usar una sola lógica que afecta a muchos sprites a la vez (usando los flag de movimiento automático y/o relativo)
  • Usar diferentes lógicas pero ejecutar solo una o unas pocas en cada ciclo del juego.
Ambas opciones tienen un mismo objetivo: ejecutar menos lógica en cada ciclo, permitiendo que todos los sprites se muevan a la vez pero tomando menos decisiones en cada ciclo del juego.  La clave está en determinar qué logica o logicas ejecutar en cada ciclo. En el caso mas sencillo, si tenemos N sprites simplemente ejecutaremos una de las N lógicas. Pero en casos más complejos deberemos ser astutos para determinar que lógicas conviene ejecutar.

A continuación os muestro el siguiente vídeo con unos ejemplos del resultado de esta técnica. Son programas en BASIC, simplemente para imprimir los sprites usan la libreria 8BP pero la clave está en que aplican la técnica de logicas masivas para poder funcionar. Y si no fuese así, no podrían hacer lo que hacen. Comprobadlo viendo el siguiente vídeo



Lo que hemos hecho ha sido reducir la complejidad computacional. Hemos partido de un problema de “orden N”, siendo N el número de sprites. Suponiendo que cada lógica de sprite requiera 3 instrucciones BASIC, en principio habría que ejecutar N x 3 instrucciones en cada ciclo. Con la técnica de “lógicas masivas”, transformamos el problema de “orden N” en un problema de “orden 1”. Se llama  problemas de “orden 1” a los que involucran un número constante de operaciones independientemente del tamaño del problema. En este caso hemos pasado de Nx3 = 32x3 = 96 operaciones BASIC a sólo 3 operaciones BASIC. Esta reducción de complejidad es la clave del alto rendimiento de la técnica de lógicas masivas.



Movimiento en bloque de escuadrones
Si lo que quieres es simplemente mover a la vez un escuadrón en una dirección, cualquiera de las dos funciones siguientes de la librería 8BP te servirán:

  • Si usas |AUTOALL tienes que ponerle velocidad automática a los sprites en la dirección que quieras (en Vx, en Vy o en ambas) y por supuesto activar el bit 4 del byte de estado. El comando AUTOALL tiene un parámetro opcional para invocar internamente a |ROUTEALL antes de mover a los sprites
  • Si usas |MOVERALL tienes que activar el bit 5 del byte de estado a los sprites que vayas a mover. Este comando requiere como parámetros cuanto movimiento relativo en Y y en X deseas


De esta forma con una única instrucción estás moviendo muchos sprites a la vez. En caso de que cada uno de tus sprites se deba mover de forma independiente y con una lógica "Inteligente", sigue leyendo

Técnica de lógicas masivas en juegos tipo pacman
En un juego con varios enemigos podríamos pensar que basta con ejecutar la logica del enemigo1 en el primer ciclo, la del enemigo 2 en el segundo ciclo , la del enemigo 3 en el tercer ciclo y vuelta a empezar. Sin embargo lo que conviene es ejecutar la logica cuando dicha logica debe tomar una decisión.
en juegos tipo pacman esto ocurre cuando un fantasma llega a una bifurcación en la que puede tomar una nueva dirección de movimiento en función de su inteligencia

Supongamos que tienes 8 enemigos y que las bifurcaciones del laberinto ocurren en múltiplos de 8. Si el primer enemigo está en una posición múltiplo de 8 le tocará ejecutar su lógica. Al segundo enemigo le toca ejecutar su lógica de decisión en el ciclo siguiente. Si no se encuentra en una posición de bifurcación del laberinto no podrá cambiar su rumbo
Para que “encaje” su posición con un múltiplo de 8 y así poder decidir qué camino tomar en la bifurcación, simplemente empezamos el juego con este segundo enemigo colocado en un múltiplo de 8 menos uno. Considerando coordenadas que comienzan en cero, los múltiplos de 8 son:

  • Primer enemigo: posición 0 o 8 o 16 o 24 o 32 o XX (en eje x o y, da igual)
  • Segundo enemigo: posición 7 o 15 o 23 ...
  • Tercer enemigo : posición 6 o 14 o 22 ...

Y así sucesivamente. Colocas a tus enemigos siguiendo esta regla:

Posición = múltiplo de 8 – n, siendo n el numero de sprite

Y cada vez que le toque a un enemigo ejecutar su lógica, podrá encontrarse en una bifurcación. En el siguente ejemplo tenemos un fantasma que debe tomar una decisión en el instante t=5, posteriormente lo hará en t=5+8 y la siguiente será en t=5+8+8, etc.

lógicas masivas en juegos tipo pacman

Cuando le toque ejecutar su lógica deberá comprobar que no se encuentra en una posición en mitad de un pasillo sin bifurcaciones. Debe comprobarlo y para ello puede usar PEEK contra un carácter del layout, ya que su coordenada dividida entre 8 es precisamente una posición del layout. El PEEK es muy rápido (unos 0.9 ms) frente a la detección de colisión que consume más de 3ms. Con PEEK compruebas si la posición superior está ocupada por un ladrillo (por ejemplo) y si hay vía libre entonces el enemigo podría tomar esa nueva dirección.

¿Y si solo tienes 5 enemigos? Pues muy fácil. Hay ciclos que puedes simplemente no ejecutar ninguna lógica y así los cinco siempre toman decisiones al encontrarse en posiciones de bifurcación, múltiplos de 8.

Aritmetica modular para reducir tareas por ciclo
Vamos a ver otro ejemplo muy sencillo de aritmética modular con operaciones binarias en el que tenemos 4 tareas a ejecutar, pero solo ejecutamos una en cada ciclo de juego. Con este programa reducimos complejidad de orden 4 a complejidad de orden 1:

10 IF ciclo AND 1 THEN 90
20 REM cada dos ciclos entramos aquí
25 IF ciclo AND 3 THEN 80
30 REM cada 4 ciclos entramos aquí
35 IF ciclo AND 7 THEN 70
40 REM cada 8 ciclos entramos aquí
50 <instrucciones de tarea 4> : GOTO 100 
70 < instrucciones de tarea 3> : GOTO 100
80 < instrucciones de tarea 2> : GOTO 100
90 <instrucciones de tarea 1>
100 REM --- fin de tareas ---


El resultado en el tiempo de la ejecución del programa es el siguiente:


Un ejemplo complejo de lógicas masivas

A modo de ejemplo de la técnica de programación de "lógicas masivas", vamos a ver como están hechas las hileras simétricas de 12 naves enemigas del videojuego "Anunnaki".
En este juego se ejecuta en cada ciclo de juego la logica de chequeo de comprobación de un solo punto de control o "nodo" de la trayectoria, que es aquel lugar donde las naves pueden cambiar de dirección. Se van comprobando secuencialmente dichos nodos, pero solo uno en cada ciclo de juego, de modo que solo dos naves pueden cambiar de dirección simultáneamente en el mismo fotograma. Como podemos apreciar, no es una limitación importante y el resultado final es aceptable a pesar de que estamos ejecutando todo desde BASIC. 

Cada instrucción es muy costosa en BASIC, pero programando con esta técnica logramos controlar la lógica de 12 naves enemigas  + 3 disparos + nuestra nave, un total de 16 sprites con vida propia pero con una muy reducida lista de instrucciones en cada ciclo.

La linea 3133 es la que gobierna el rumbo de todas las naves. Esto es "lógicas masivas". Intenta comprender la filosofía en este programa y no los detalles. Sólo una línea que gobierna a todos. Solo una, y en cada ciclo de juego se centra en dos naves diferentes en función del instante de tiempo en que nos encontramos.












Controla el tiempo, no el espacio:
Comencemos imaginando una trayectoria para una hilera de 8 naves enemigas. las naves pasarán una a una por una serie de "nodos de control", que son lugares en el espacio donde deben cambiar su dirección, definida por sus velocidades en X, e Y, es decir (Vx,Vy)

Trayectoria definida con "nodos de control"
Una forma de controlar que las 8 naves cambien de dirección en dichos lugares sería comparar sus coordenadas X,Y con la de cada uno de los nodos de control y si coinciden con alguno de ellos, entonces aplicamos las velocidades nuevas asociadas al cambio en ese nodo. Puesto que hablamos de 2 coordenadas, 8 naves y 4 nodos, estamos ante:

2 x 8 x 4 = 64 comprobaciones en cada fotograma

Esto no es viable si queremos velocidad desde BASIC. Y es que no es una estrategia eficiente computacionalmente. Puesto que estamos ante un escenario "determinista", podríamos estar seguros en cada instante de tiempo donde van a encontrase cada una de las naves y por lo tanto en lugar de hacer comprobaciones en el espacio, podemos únicamente centrarnos en la coordenada temporal (que es el número de fotograma del juego o el también llamado número de "ciclo de juego")

Puesto que conocemos a la velocidad a la que se mueven las naves, podemos saber cuando la primera de ellas pasará por el primer nodo. A ese instante lo llamaremos t(1). También asumiremos que debido a la separación entre las naves, la segunda de las naves pasará por el nodo en el instante t(1)+10. la tercera en t(1)+20 y la octava en t(1)+70

Sabiendo esto podemos controlar el tiempo con dos variables: una contará las decenas (i) y otra las unidades(j). Para controlar el cambio de las 8 naves en el primer nodo podemos escribir:

j=j+1: IF j=10 THEN j=0: i=i+1
IF i>=t(1) AND i<t(1) +8 THEN [actualiza velocidad de nave  i-t(1) con los valores de velocidad del nodo 1]

Como vemos con una sola linea podemos ir cambiando las velocidades de cada nave a medida que van pasando cada una de ellas por el nodo 1. Durante los 8 instantes de tiempo posteriores a t(1) se van actualizando cada una de las naves, justo cuando pasan por el nodo de control

Ahora vamos a aplicar lo mismo a los 4 nodos. Podríamos ejecutar 4 comprobaciones en lugar de una, pero sería ineficiente. Además si tuviésemos muchos nodos esto supondría muchas comprobaciones. Podemos hacerlo solo con una, teniendo en cuenta que la primera nave pasa por un nodo en un instante t(n) y la ultima nave pasa por ese nodo en t(n)+7

Cuando la primera nave pasa por el primer nodo, tiene sentido pensar en empezar a comprobar el nodo 2, pero no el nodo 3 ni el 4. Ya tenemos el nodo mayor que vamos a controlar.
En cuanto al nodo menor, podemos asumir que aunque tengamos 20 nodos, estén lo suficientemente separados como para que no haya naves atravesando mas de 3 nodos a la vez (vamos a suponer eso y usaremos ese "3" como parámetro). Por lo tanto el nodo menor a comprobar es el mayor - 3. Al nodo menor lo vamos a llamar "nmin" y al mayor "nmax".  ( nmin = nmax-3 ). El caso que queramos tener plena libertad para poder definir cualquier trayectoria, nmin debe ser nmax menos el número de naves de la hilera.


j=j+1: IF j=10 THEN j=0: i=i+1: n=nmax
IF n<nmin THEN 50:' no hay que actualizar mas naves
IF i>=t(n) AND i<t(n)+8 THEN [actualiza i-t(n)]:IF i-t(n)=0 THEN nmax=nmax+1: nmin=nmax-3
n=n-1

50 ' mas instrucciones del juego

Como veis cuando se incrementa en 1 la decena de tiempo, se comprueban los nodos desde "nmax" hasta "nmin" Y en cada nodo actualizamos la nave i-t(n). Pensad que si t(3) es, por ejemplo, 23, entonces cuando llegamos al nodo 3 en el instante i=23, actualizamos la nave i-23 =0, con los valores de velocidad del nodo 3.

En el siguiente ciclo de juego comprobamos si aun sigue "vigente" el intervalo de tiempo del nodo 2, y actualizamos la nave 1 con los valores de velocidad del nodo 2,

y en el siguiente ciclo comprobamos el nodo 1 y si sigue vigente actualizamos la nave 2, y asi sucesivamente, siempre teniendo en cuenta que la primera nave puede haber llegado a nmax, mientras que la siguiente nave puede estar en nmax-1 y la siguiente en nmax-2, etc.

En resumen, hemos transformado 64 comprobaciones en solo 1, usando "Lógicas masivas". Y si la trayectoria tuviese 40 en lugar de 4 nodos, habríamos transformado 640 operaciones en una sola!



No hay comentarios:

Publicar un comentario