Mostrar Mensajes
16
Inteligencia Artificial / Otra De Ia: Pathfinding De Grupos De Unidades
« en: 11 de Mayo de 2005, 03:08:48 pm »
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
) 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.
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
) 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.
).