A* / pathfinding

Para el movimiento del personaje implementé un algoritmo A*.
Lo que hace es buscar el camino más corto entre dos puntos, en este caso, donde está ubicado el personaje y a donde queremos movernos. Obviamente el algoritmo se encarga de bordear los obstáculos (nodos no navegables) que puedan haber en el camino.



En la imagen de arriba el nodo verde es el origen, el rojo el destino, los blancos son los nodos navegables y los grises son los obstáculos. Los violetas representan los nodos que fueron analizados.
No voy a explicar a fondo como funciona el algoritmo ya que hay varios artículos muy buenos.

El algoritmo se basa en dos funciones, h(x) y g(x).
g(x) = distancia desde el origen hasta x
h(x) = distancia desde x hasta el objetivo

Para h(x) por lo general se usa la distancia más corta (una línea recta entre los puntos). Esta función se puede variar para encontrar caminos más reales, por ejemplo para evitar cáminos con zigzags innecesarios, entre otras cosas.
Comenzando desde el nodo inicial se agregan sus nodos adyacentes (aquellos que sean válidos) a una lista de posibles nodos a visitar. Luego de esa lista se elije el que tenga menor valor de g(x) + h(x) y a su vez para cada nodo elegido se agregarán sus adyacentes a una lista de posibles candidatos.

Como grilla, para saber que nodos se pueden navegar y cuales no, se usa la generada anteriormente.



El único problema que podríamos tener es si se clickea en una zona que no este pintada en azul, ya que ese nodo no es navegable y el algoritmo no lo tendría nunca en cuenta. Para solucionar esto, si el jugador intenta moverse a una zona no navegable primero se busca un nodo válido para usar como destino.
Por ejemplo, al clickear sobre la puerta el personaje va a moverse hasta uno de los nodos azules en el piso cercanos a la misma.

Agregué más cosas al juego en estas semanas, la más interesante (o que me resulto divertida de hacer) es la del scripting. A través del xml de las escenas se pueden scriptear distintas acciones para los elemenos del juego, ya sea actores, items, objetos, etc...

Supongo que la próxima entrada será sobre eso.