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, como veremos al explicar como definir trayectorias complejas.

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 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.


Un ejemplo de programa:

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. Solo 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 en la entrada