martes, 21 de agosto de 2012

PathFinding

Después de un tiempo sin publicar nada... voy a escribir un poco acerca de un tema que he estado investigando.
Se trata de la búsqueda de caminos o en inglés "pathfinding".
Es un problema común en juegos de estrategia, así como juegos de laberintos tipo comecocos, etc.
En muchos de estos juegos, la inteligencia artificial de los entes móviles, puede que esté intentando buscar el camino óptimo para llegar de un sitio a otro. Incluso nuestro personaje, si le mandamos ir a un sitio, es probable que tenga que tener en cuenta los obstáculos que hay en el terreno y trace el camino más corto.
Para esto se usan los algoritmos de PathFinding.
Hay varios algoritmos populares, por ejemplo el A*, el WaveFront o BrushFire que es en el que yo me centraré con el código.
Antes deponerme con estos algoritmos que me resultaban algo difíciles, intenté empezar con un algoritmo publicado por un usuario en el foro de unity spain, el cual no precisaba de muchos conocimientos.
En realidad era un algoritmo de intuición ya que no buscaba el camino óptimo, si no que más bien hácía que el personaje fuera moviéndose por donde más posibilidades instantáneas había para llegar al objetivo.
Después de estar unas semanas mejorando este código, y consiguiendo algún resultado bastante convincente, llegué a la conclusión de que había algún problema que era imposible de esquivar con ese método.

Entonces miré el A*, y vi que era bastante lioso y usaba recursividad...

Pasé al wavefront que parecía más fácil y en efecto me qeudé con él.
También usa una función recursiva a la hora de buscar el camino óptimo pero me resultó bastante más fácil de implementar y de hecho la función la hice desde cero fijándome solo en el pseudocódigo del algoritmo.
Yo esta vez lo hice en C# ya que en ese momento me dió por aprender un poco de C#.
A su vez, un compañero del foro, lo implementó en Js.

Bueno os escribo la función ActualizarMatriz que es la básica. No está comentado así que hace falta un poco de imaginación para entender lo que se hace.

 void ActualizarMatriz(Vector2 NuevoTarget, intNuevoPeso){
  int i;
  int u;
  int v;
  for (i = 0; i < 8 ; i++){
   u = (int) NuevoTarget.x + X[i];
   v = (int) NuevoTarget.y + Y[i];
   if  (u >= 0 && u <10  && v >= 0 && v <10  ){
    if (Matriz[u,v] != -1 && NuevoPeso < Matriz[u,v]){
        if(u==PosicionPlayerActual.x&&v==PosicionPlayerActual.y)
        break;
    Matriz[u,v] = NuevoPeso;
    Vector2 Adyacente = new Vector2(u,v);
    ActualizarMatriz(Adyacente, NuevoPeso + 1);
    }
   }
  }
 }
 

Si tenéis dudas, contactad conmigo por email o dejando aquí un comentario y os ayudaré.

Podéis pedirme el código completo del fichero por si queréis probarlo en vuestro ordenador, o incluso os puedo dejar mi proyecto de unity con todo preparado.

Un saludo.