Una de las cosas más comunes en los juegos es implementar un algoritmo que lleve a un personaje del punto A al punto B. En el camino, siempre, obstáculos por donde no se puede pasar.
Estos algoritmos, denominados "Path Finding" o "Búsqueda de Camino", están muy bien documentados y hay muchísimos ejemplos en Internet para entornos de programación actuales.
Bueno, ¿ Que pasa si queremos implementar esta funcionalidad en Sinclair BASIC ?.
Nos encontramos con varios problemas:
- El uso de recursos de lenguaje de programación como colas, objectos , etc.
- Las limitaciones propias del Sinclair BASIC. Tenemos muy poca memoria donde debe residir todo el programa o juego, no solo el algoritmo y un numero muy limitado de espacio para variables.
- La velocidad de proceso en Sinclair BASIC, sobre todo dentro de bucles.
Todo esto comienza como parte del desarrollo del juego Retro8ogue. Estoy en la fase de implementar el movimiento de los monstruos en pantalla, pero con sentido (o lo que llaman también I.A., Inteligencia Artificial).
Una vez dentro del rango de visión / oído del monstruo, éste debe encontrar el camino hacia el personaje, independientemente del mapa y los obstáculos que se pueda encontrar. Como es un juego rogue - like, el mapa es generado aleatoriamente y nunca es igual.
Dadas las limitaciones, partimos de las siguientes premisas:
- Utilizar el mínimo de variables posibles.
- Utilizar el mínimo de lógica posible.
- Optimizar para velocidad de proceso.
- Reconocimiento de gráficos definidos por el usuario (UDG) para la gestión de colisiones.
- Un poco de aleatoriedad, para darle al personaje alguna posibilidad, cuando se enfrenta a varios monstruos en avance.
Es decir, simplificar al máximo las posibilidades de búsqueda para minimizar el código y las necesidades de proceso. Añadir un poquito de aleatoriedad en la búsqueda del mejor camino.
Veamos el ejemplo en pantalla de nuestro intento:
Hay una escalera que el personaje tiene que encontrar.
El mapa es aleatorio, pero no muy poblado de bloques para facilitar la labor.
Lo primero que definimos es que hay 8 direcciones posibles para el personaje.
4 5 6
3@7
2 1 8
La idea es que, de las 8 posibles direcciones, ¿cual es la que está mas cerca del objetivo?.
Todo lo hacemos con coordenadas X e Y, para lo que la pantalla del Spectrum es perfecta.
Esto lo calculamos de la siguiente manera:
d = ABS(destino_x - origen_x)+ABS(destino_y-origen_y)
Si calculamos esto sobre las 8 posibles direcciones que podemos seguir, sabemos cual es la que mas cerca nos deja del objetivo. Si esa dirección está ocupada por algo que no nos deja pasar, nos movemos de forma aleatoria 1 vez.
Hay muchas maneras más efectiva de hacer esto, pero la utilizada nos garantiza que:
- Eventualmente, lleguemos al objetivo.
- El monstruo se comporta de vez en cuando de forma aleatoria en su movimiento, lo que añade jugabilidad al juego.
- Es muy fácil de implementar en BASIC y de optimizar para usar el mínimo de código, variables y proceso.
El resultado en BASIC es aceptable en términos de rendimiento, y una vez pasado a código máquina, funciona de forma excelente.
Si al ejemplo le quitamos el uso de detección de UDG's , irá aún más rápido. He utilizado los UDG's para hacer el ejemplo más completo y aplicable al desarrollo de Retro8ogue.
Hay otras optimizaciones hechas en el movimiento aleatorio para que no se pierda tiempo, pero esas las puedes ver en el propio código (como no intentar otra vez un lado que está obstruido en el mismo ciclo).
Puedes descargar una cinta en formato TAP con el código Sincalir Basic aquí.
Puedes descargar una cinta en formato TAP con el programa en código máquina aquí.
Puedes ver el vídeo del ejemplo funcionando:
