Fregocles y la desinfección del Olimpo

Fregocles, o más bien la aventura de como hacer una aventura, comenzó tras otro proyecto fallido que terminaba en la carpeta de “demasiado ambicioso”. Se empezó sin nombre, sin historia y sin pretensión de terminar un juego. En sus inicios solo era un intento de crear un motor de aventuras gráficas, todo con la pequeña ilusión de que si llegaba a buen puerto, se plantearía la idea de hacer un juego.

Lo primero que vio la luz de ese motor fue la búsqueda de caminos. No es una parte muy específica, pero algún iluminado creyó que sería lo más difícil y que si se superaba, el resto sería coser y cantar. Sin profundizar técnicamente, aquí se muestra el proceso de desarrollo del algoritmo. Podéis bajar los binarios de una compilación de marzo de 2004 haciendo clic aquí.

La búsqueda se desarrollaría en un entorno 3D, pero en una aventura gráfica no es especialmente necesario disponer de varios niveles (en altura), teletransportes, etc. y ya que desde un punto de vista cenital, el personaje se mueve solo en 2D (aunque luego al andar se adapte a las alturas del terreno), la búsqueda trabajaría únicamente en dos dimensiones.

Otra decisión que había que tomar era si trabajar con una matriz de posiciones o mediante un grafo de nodos (como las aventuras clásicas en 2D). Usar nodos permite llevar a tu personaje justo a la posición que quieres y permite tener nodos no conectados muy cerca (por ejemplo a cada lado de un muro). Pero nos decantamos por el otro método, teniendo una cuadrícula que marca las posiciones en las que puedes estar. Esto limita bastante los movimientos del personaje, pero es más fácil de implementar, principalmente porque no necesita ningún editor específico para esto. De forma que solo era necesario una matriz que indicara las casillas por las que se puede pasar y las que no, un origen y un destino. El algoritmo genera una lista de casillas por las que hay que pasar para llegar al destino sin chocar.

Cada habitación tiene su propia matriz de colisiones, la cual es generada a partir de una imagen BMP donde el color negro significa “muro” y cualquier otro color indica “camino”. Más tarde el color de la parte caminable se utilizó para definir que cámara es usada en cada momento, pero eso es otro tema.

Lo básico estaba hecho, ahora había que refinarlo. El primer problema era ¿qué ocurre si origen y destino no están comunicados? Se optó por buscar la casilla más cercana al destino que si comunicara con el origen, así el personaje quedaría lo más cerca posible de donde se le había indicado que fuera.

El segundo problema era que el personaje se movía solo en ángulos de 90 grados, y eso no quedaba muy natural cuando una diagonal habría sido el camino más lógico. Se solucionó repasando el camino desde el final, intentando saltarse nodos innecesarios, usando diagonales y sin chocarse (contando además con que el personaje no es un punto y ocupa una superficie). En la imagen puede verse la casilla de origen (O) y la de destino (D), en color verde el camino inicial (solo giros de 90º) y en rojo (marcando los nodos con círculos) el nuevo camino con diagonales. Podrían existir caminos más cortos aun, pero con este simple sistema quedaba bien.

Se añadieron algunas optimizaciones para realizar varias búsquedas simultáneas, y la posibilidad de varios personajes esquivándose unos a otros. Con todo esto, una mopa y abrillanta suelos, se obtiene un camino limpio hacia cualquier parte.