AS 2.0: Pathfinder en tablero hexagonal

Muy buenas a todos,

Antes de exponer mi problema, quisiera felicitaros por esta gran comunidad que habeis formado y daros las gracias por adelantado por vuestra ayuda.

Iré al grano: he empezado a programar juegos en flash este curso en una asignatura de la universidad, y debo crear un juego de combate por turnos al estilo "Advance Wars". El caso es que ya tengo implementada la parte inicial gracias a los inestimables tutoriales de Tonypa (tablero con hextiles: http://www.tonypa.pri.ee/tbw/tut25.html), tengo implementado el movimiento de las naves del Jugador 1 y las naves de la CPU son insertadas mediante randoms, pero ahora necesito implementar algun tipo de lógica para el movimiento de las naves CPU por el tablero y no consigo encontrar nada que sea fácilmente implementable! Encontré los códigos de ejemplo de Amit J Patel de pathfinding (http://www-cs-students.stanford.edu/~amitp/game-programming/a-star-flash/) orientado a tiles triangulares, cuadrados y hexagonales, he probado los swf de los dos primeros (puesto que amablemente nos los ofrece junto al código) pero no consigo compilar el caso de los tiles hexagonales que es el que me interesa, y creo que es lo que más se parece a lo que necesito, puesto que quiero que se vea el desplazamiento de las naves por los tiles "caminables".

En resumen, dado un tablero de tiles hexagonales alineados verticalmente (representado cada tile por un duplicateMovieClip de un hextile) necesito implementar el código para el movimiento de las naves a través de éstas. Os adjunto el código que sirve para introducir los tiles en la pantalla (básicamente una traducción del código de Tonypa que muchos ya conocereis):

Código ActionScript :

function creaGraella(graella) {
   //Adjuntamos un movieClip vacío ("Buit")
   _root.attachMovie("Buit","tiles",1);

   //Valor de inicio de profundidad para las naves

   var prof = 1000;
   //Clip contendrá los tiles
   joc.clip = _root.tiles;

   //Asignamos a clip las medidas del tile hexagonal
   joc.clip._x = joc.tileMida;
   joc.clip._y = joc.tileAlcada/2;

   //Colocamos los tiles hexagonales.
   //Les variables x, y son las coordenadas en el sistema de referencia de cada tile hexagonal
   for (var y = 0; y<alt_taulell; ++y) {
      for (var x = 0; x<ample_taulell; ++x) {
         //Nombramos el nuevo tile
         var nomTile = "t_"+x+"_"+y;

         joc.clip.attachMovie("Hextile",nomTile,y*100+x*2);
         joc.clip[nomTile]._x = x*joc.tileMida*1.5;
         joc.clip[nomTile].xtile = x;
         
         //Debemos determinar si estamos en columna par o impar
         //Es por eso que se hace necesario añadir la mitad de la altura del tile en función de si es par o impar
         joc.clip[nomTile]._y = y*joc.tileAlcada+x%2*joc.tileAlcada/2;
         joc.clip[nomTile].ytile = y;
         
         //Asignamos aleatoriamente si el tile será PISABLE ("TREPITJABLE") o NO PISABLE("NO_TREPITJABLE")
         var aleatori = Math.random();
         //trace("Tile "+nomTile);
         //trace(aleatori<0.2);
         if (aleatori<0.1) {

            joc.clip[nomTile].tipus = NO_TREPITJABLE;
            joc.clip[nomTile].gotoAndStop("no_trepitjable");

         } else {

            joc.clip[nomTile].tipus = TREPITJABLE;
            joc.clip[nomTile].gotoAndStop("trepitjable");
         }
      }
   }
}

Si conoceis alternativas al pathfinding para este tipo de juegos, estoy abierto a sugerencias, y por favor si necesitais más información acerca del juego para resolver mis dudas no dudeis en pedirmelo!
Gracias de nuevo!

No entiendo cual es tu problema. ¿Que es lo que te complica puntualmente?

Saludos, Hernán . -

Hernán escribió:

Buenas Hernán,

El problema REAL que tengo es que no sé como determinar el movimiento de las naves enemigas a través de los tiles. Desde que empecé a estudiar la programación de juegos he creído tener claro que lo que necesitaría para mover las naves de la CPU sería algun algoritmo de pathfinding, puesto que no hay ningun tipo de interacción humana en sus decisiones. Aun así, quizás esté equivocado y para mi caso exista alguna alternativa más acertada.

Os pongo una captura del modo combate para que os hagais una idea de la disposición de elementos:


Los tiles blancos son tiles "caminables" mientras que los morados son "no caminables". Las naves azules son las controladas por el jugador 1, las naves rojas son las de la CPU. Lo que necesito es que cuando llegue el turno de la CPU ésta lleve a cabo sus rutinas de lógica y luego desplace/ataque/defienda (o no) sus naves por el tablero. La lógica aún no la tengo implementada, pero creo más urgente determinar como desplazar las naves automáticamente puesto que se del cierto que será lo más complicado. He visto mucha documentación referente al pathfinding para grids rectangulares, pero muy poca cosa para tiles hexagonales, y la verdad es que además el tema de como gestionar las celdas vecinas también me tiene un poco mosqueado (pero eso es otro tema).

Soy muy novato en Flash, pero referente al pathfinding hexagonal que os comenté creo que los códigos de Amit estan escritos en ActionScript 3.0, lo que hace que no pueda usarlos correctamente en mi juego. Creo que mis dudas se verían resueltas si me pudieseis echar una mano para introducir ese código en mi juego en AS 2.0. O eso o buscar una alternativa al desplazamiento de las naves CPU...

Espero que así haya quedado más clara mi duda!

Pues no se que tan exacto quieras hacerlo, pero sean hexagonales o como fueran, es lo mismo, puesto que la idea del PathFinding es exactamente la que describes en tu pantalla, los prendidos y apagados de recorrido.

Lo que tendrías que pensar ahora, es si tu nave será inteligente o solo patrullara la zona. Si quieres que persiga a su objetivo, lo que tendrás que hacer es determinar primero donde esta. Luego ir moviendo hacia su destino final uno por uno, en el caso de que la movida sea "nula" reposicionarla al costado para que esa movida pueda pasar.

Si solo quieres que patrullen, es más fácil, dado que solo tienes que decirles que se muevan con un patrón N definido, donde también debes evaluar que la movida no sea nula, y si lo es reprocesarla.

Saludos, Hernán . -

Pues la idea és, como he comentado en el primer mensaje, hacer un juego por turnos. Por lo tanto cuando le toca el turno a la CPU, ésta debe decidir qué hacer con cada nave.

Cada nave tiene 4 acciones posibles: MOVIMIENTO, ATACAR, DEFENDER y PASAR EL TURNO. Con MOVIMIENTO la nave puede desplazarse un máximo de tantos tiles como lo indique su parámetro "movimiento" (la nave más lenta se puede mover solo un tile, mientras que la más rápida puede moverse 4), con ATAQUE y DEFENSA la nave puede atacar/defender a una distancia máxima igual a la de sus respectivos parámetros "ataque" y "defensa", y con PASAR EL TURNO no se hace nada. El jugador 1 posiciona manualmente las naves, así que no hay ningún problema a excepción de terminar de ajustar el código que muestra el frame "movimiento" de cada tile al que puede llegar; en cambio para el jugador CPU necesito que éste decida qué hacer con cada nave, y por ejemplo si ha decidido mover la nave pues que calcule la ruta más sencilla hasta la posición final, esquivando los tiles "no caminables", y luego muestre por pantalla el desplazamiento de la nave a través del camino calculado. Es por eso que estoy tan obsesionado con el pathfinding, pero creo que si me pongo a hacerlo desde cero puede ser que no termine a tiempo el proyecto.

En el caso de ATAQUE tan solo debería mirar si la nave enemiga está dentro del rango de ataque, y en el caso de DEFENSA la nave tomaría una posición de ventaja en caso que en el siguiente turno fuese atacada por una nave enemiga. La lógica para determinar cual de estas cuatro acciones debería tomar cada nave aún no la tengo, pero antes de eso creo que sería oportuno tener solucionado el tema de como hacer que las naves enemigas se muevan solas por el tablero.

A ver si podeis echarme un cable, que de pronto me siento un poco atascado, la verdad...

Gracias de nuevo!

Hola de nuevo,

Espero no incumplir demasiado las normas con este doble-post, pero he hecho algunos avances en el juego y me gustaría compartirlos con vosotros.

He remodelado gran parte del código del juego, de tal modo que ahora los tiles que cambian de color en función de la acción que se desea ejecutar ya no siguen el patrón de tiles vecinos, sino que se calcula la distancia desde su centro al centro del tile principal y se evalua si está dentro del rango de tiles accesibles. Esto es perfecto en hexágonos puesto que desde cualquier dirección la distancia hasta el siguiente centro es siempre la misma, que es la altura del hexágono. Os pongo una imagen para que veais el resultado:



De igual modo los tiles se reinician cuando se ha decidido el tile de destino, volviendolos blancos. He aquí el código para pintarlos segun la acción y el alcance de ésta:

Código ActionScript :

function pinta_abast(nau, accio, abast_accio) {
   trace("Entrem a la funció");
   var xtile_origen = Math.round((nau._x-_root.joc.clip._x)/_root.joc.tileMida/1.5);
   trace("nau._x val "+nau._x);
   trace("xtile_origen val "+xtile_origen);
   var ytile_origen = Math.round((nau._y-(xtile_origen%2+1)*_root.joc.clip._y)/_root.joc.tileAlcada);
   trace("ytile_origen val "+ytile_origen);
   //Assignem a tile_origen el tile des d'on sortim per a treballar més còmodament.
   var tile_origen = _root.joc.clip["t_"+xtile_origen+"_"+ytile_origen];

   for (var i = 0; i<_root.ample_taulell; ++i) {
      for (var j = 0; j<_root.alt_taulell; ++j) {

         var Tile = _root.joc.clip["t_"+i+"_"+j];

         var dist_x = Math.abs(Tile._x-tile_origen._x);
         var dist_y = Math.abs(Tile._y-tile_origen._y);
         var dist_centres = Math.round(Math.sqrt(Math.pow(dist_x, 2)+Math.pow(dist_y, 2)));

         if ((dist_centres<=(_root.joc.tileAlcada*abast_accio)) && (Tile.tipus == _root.TREPITJABLE)) {

            Tile.gotoAndPlay(accio);

         } else {
         }
      }
   }
}

donde "nau" es el nombre del movieclip de la nave con la que interactuamos, "accio" es una cadena de caracteres correspondiente a una de las tres acciones ya mencionadas ("movimiento", "ataque", "defensa"), y "abast_accio" es un entero que indica el alcance de dicha acción (1 tile de distancia, 2 tiles, etc...). Antes usaba las coordenadas de los 6 tiles vecinos, pero realmente solo me era útil cuando el valor del alcance era 1, para valores superiores era un caos por culpa del sistema de coordenadas (hay que diferenciar columnas pares e impares!).

Hablando de coordenadas, al buscar información estos últimos meses acerca del pathfinding en hexágonos encontré un paper muy interesante de Peter Yap aquí (os recomiendo descargarlo y convertirlo a PDF antes que nada). Hasta hoy no había tenido tiempo de mirarmelo a fondo, pero al leermelo detenidamente he encontrado datos interesantes como por ejemplo el uso de la distancia Vancouver en vez de la Manhattan para calcular el coste de los desplazamientos entre hexágonos, puesto que al tener distintas alturas las columnas pares e impares la Manhattan no funciona y hay que hacer ciertas correcciones. En cuanto saque algo más en claro os lo comentaré.

Aun así sigo abierto a sugerencias para el control de las naves CPU en mi juego. ¡Cualquier idea será bienvenida!

¡Hasta pronto!

Buenas,

Nuevamente me paso por aquí para ver si me podeis echar una manita con algunas dudas referentes a flash.
Ya he conseguido diseñar un pathfinding hexagonal, no muy optimizado pero da el pego para el juego que estoy haciendo. Os pongo el pseudo-código para que os hagais una idea de como funciona:

Código ActionScript :

function pathFinding(iniciTile, finalTile, pas, max_passos) {

   clearInterval(_global.pathfind);//aturem la iteració
   trace("Pas "+pas+" del pathfinding");
   iniciTile.tipus = _root.TREPITJABLE;

   if (iniciTile == finalTile || pas>max_passos) {//Si el tile d'inici és igual al final o s'han dut a terme el màxim de passos possibles aturem la iteració
      trace("Fi del pathfinding");
      iniciTile.tipus = _root.NAU_2;
      return;
   }
   //Si les destinacions canvien d'una iteració a una altra...       
   if (finalTileprevi != finalTile) {
      //S'anul·len els nodes visitats
      llistaTancada = null;
      llistaTancada = new Array();
      trace("llistaTancada reiniciada");
   }
   llistaTancada.push(iniciTile);
   omplirVeins(iniciTile,finalTile);
   var tileProper = mesProper();
   llistaOberta = null;
   llistaOberta = new Array();

   if (tileProper != finalTile) {
      //Desplacem la nau fins el tileProper
      mouNau(iniciTile,tileProper);
      iniciTile = tileProper;
   }
   //Guardem la posició del tile destí d'aquesta iteració       
   finalTileprevi = finalTile;
   if (iniciTile.pes != 1) {
      pas += 1;
      _global.pathfind = setInterval(pathFinding, 100, iniciTile, finalTile, pas, max_passos);
   } else {
      trace("La nau ha arribat a destí");
      iniciTile.tipus = _root.NAU_2;
   }
}

El pathFinding desplaza la nave una posición por cada iteración que se hace del código mediante setInterval.
iniciTile y finalTile son los nombres de los tiles de inicio y final del pathfinding, "pas" es el número de iteraciones de pathfinding que hemos hecho de momento, "max_passos" es el máximo de iteraciones a hacer (si no se llega al objetivo antes de "max_passos" se para el pathfinding). El significado de "max_passos" viene del hecho que las naves que quiero mover tienen un alcance limitado y sólo pueden moverse un número determinado("max_passos") de tiles. Las iteraciones vienen definidas por la función setInterval asignada a la variable _global.pathfind.

En general funcionaría bien si no fuera porque, tal como está diseñado ahora mismo, el código flash sigue ejecutandose simultaneamente a las iteraciones! Lo que me interesa a mí es que tan solo siga ejecutando código cuando hayan terminado las iteraciones del pathfinding para la nave en cuestión. Os pongo el código para ver si queda más claro:

Código ActionScript :

   var nomTile = "t_"+nau.xtile+"_"+nau.ytile;
   var iniciTile = joc.clip[nomTile];
   trace("Localització nau: "+nomTile);
   
   var nomTile = "t_"+objectiu.xtile+"_"+objectiu.ytile;
   var finalTile = joc.clip[nomTile];
   trace("Localització objectiu: "+nomTile);
   
   
   pathFinding(iniciTile,finalTile,1,nau.moviment);
gotoAndPlay("Jugador 1");
//gotoAndPlay se ejecuta después de la primera ejecución del pathFinding!

El problema aquí está claro: Flash me salta al frame "Jugador 1" antes de terminar las iteraciones de la función pathFinding, y a mí me interesa que lo haga una vez terminadas las "max_passes" iteraciones o bien cuando haya encontrado el tile final. La cosa se complica si lo que quiero hacer a continuación del pathFinding de esta nave es ejecutar otros pathFindings para el resto de naves, ya que se ejecutan todas de golpe y el _global.pathfind es sobreescrito cada vez por todas las naves a la vez. El resultado, pues, es nefasto.

He probado con un bucle infinito vacío para evitar seguir ejecutando código que se cancele al llegar al final de las iteraciones, de este estilo:

Código ActionScript :

while(true){
       if(finIteraciones){
                 break;
       }
}

pero flash colapsa y debo cerrarlo a la fuerza. ¿Alguna sugerencia?

Esquemáticamente pondré la sucesión de eventos para que quede claro lo que quiero conseguir con el código:

1. nave 1-->pathfinding hasta nave enemiga más cercana
   
2. ---> iteraciones de pathfinding hasta encontrar la nave o hasta llegar al límite de iteraciones posibles
   
3. ---> pasar a nave 2 y repetir el proceso--->...
   
4. --->cuando se ha terminado con todas las naves, pasar a frame "Jugador 1".
   

Gracias de nuevo!