Otra De Ia: Pathfinding De Grupos De Unidades

[Daemon]

 Hola.

Una cuestion que siempre me ha llamado la atencion ha sido el movimiento conjunto de un grupo de unidades a un destino. Yo voy a dar aqui una idea (que aunque para mi sea nueva seguro que ya la pensado alguien antes, eso siempre pasa :P) Se trata de evitar al maximo posible lanzar de nuevo el algoritmo de busqueda de caminos cuando estamos moviendo grupos de unidades. Supongamos que para el algoritmo de busqueda tenemos un A* y que los factores de decision que tiene la funcion de coste es la del minimo camino (para simplificar). Ahora supongamos que deseamos mover un cto de unidades de forma coordinada, es decir en formacion y que deseamos que esa formacion se mantenga pese a los obstaculos (siempre que sea posible). La idea seria establecer una plantilla que indicaria como deben de situarse las unidades en la formacion y tener en dicha plantilla una "unidad centro" (p.e. en las coordenadas (0,0)) y el resto de unidades junto a esta (en coordenadas (-1, 0), (1,0) ...) La unidad central es la unica para la que se lanza la busqueda de caminos. El resto de unidades, se moverian siguiendo el camino, pero desplazado (+1, 0) o (-1, 0) dependiendo de su posicion en la formacion.

En cuanto una unidad de estas encuentre un obstaculo se lanzaria un algoritmo de busqueda local solo teniendo en cuenta la percepcion de la unidad (no todo el mapa), es decir si la unidad es capaz de ver el final del obstaculo entonces se lanza la busqueda local para enganchar con su posicion en la formacion pasado el mismo. En caso que no sea capaz de ver el final del obstaculo, yo la situaria detras de la unidad central que si tiene un camino hasta el objetivo y la volveria a colocar en su posicion una vez pasado el obstaculo.

De esta forma creo que es relativamente rapido (no necesita mas que un lanzamiento del A* para buscar el camino principal) realizar el pathfinding para grupos.

A ver señores, ¿que opinan ud?. ¿Ideas, comentarios otros algoritmos de busqueda mas eficientes que el A*?

Un saludete a todos.

[mimosete]

Si, me parece buena idea, vamos, no tengo otra mejor.
El caso que citas de pérdida del camino de alguna unidad por obstáculos, creo que es lo que ocurre en juegos de estrategia de soldados etc... los perdidos se ponen a seguir a un líder que sí sabe el camino. En cuanto "ven campo" corren para mantener la formación otra vez.

A mi también me llama la atención los movimientos de grupos, creo que salió en Ages II la primera vez. Lo que ya quedaba un poco feo era las carreras que se pegaban algunos para mantener la formación en una curva, etc... Esto ya está superado y hay juegos que son una maravilla en cuanto a este tipo de movimientos, por ejemplo Cossacks I y II, en que la AI de grupos está muy currada aunque tenga algunos fallitos.

Lo que ya no estoy tan seguro es que si esta simplificación de que hablas es válida también para grupos "informales", es decir que no mantienen ninguna formación

[vincent]

quizá no es directamente aplicable a mover unidades en un juego de estrategia, pero en cuanto a movimiento de grupos son interesantes los trabajos de Terzopoulos. Aqui os dejo la web. http://www.cs.toronto.edu/~dt/

[Tavo]

La idea es muy buena. Lo que hay que tener en cuenta es la distancia entre cada unidad, cosa de que no esten pegadas. Por otra parte, que pasaria si hay un puente de un casillero nada mas?, tratarian de meterse todos juntos, eso es otro problema, que no es dificil de solucionar (Se podria hacer que si una unidad del grupo que esta bloqueando el camino esta en movimiento hay que esperar hasta que se habilite el camino).

Saludos!

[flipper83]

creo recordar un artículo de Pyros sobre el "petrorians" que hablaban de esto, lo q hacian era tomar el grupo como un todo, y como bien dices lanzar un único A*, y al localizar colisiones por el camino, lo q hacian era como una teoria del embudo, los personajes de los extremos se movian hacia el centro de la formación.