Algoritmo (s) para encontrar entidades en movimiento en un laberinto

A tienen un laberinto y un personaje que está controlado por el jugador y un dron que tiene que encontrarlo (por sí mismo). ¿Alguien sabe un algoritmo de IA (eficiente) para hacer algo como esto? P.S. Sé que hay varios algoritmos de búsqueda de rutas (por ejemplo, A *), pero hasta donde sé, solo funcionan para encontrar la ruta entre dos nodos que "no se mueven" (esto funcionaría si mi personaje estuviera quieto, pero eso es obviamente no es el caso).Algoritmo (s) para encontrar entidades en movimiento en un laberinto

Fuente

2012-01-19 conectionist

¿Conoce el dron el diseño del laberinto o tiene que descubrirlo como va? Además, ¿sabe dónde se encuentra el jugador dentro del laberinto mientras se mueve? – cdeszaq

A * también requiere que conozca de antemano las ubicaciones de los puntos de inicio y fin. ¿El dron sabe dónde está el jugador y solo tiene que alcanzarlo? ¿Nuestro dron también necesita localizar al jugador? –

@cdeszaq Sí, conoce el diseño del laberinto (aunque no me importaría un algoritmo, supone que no lo sabe) y sí, sabe dónde está el jugador dentro del laberinto. – conectionist

Si el "punto de inicio" es donde está el dron, y el "punto final" se va a ejecutar en el reproductor, lo mejor que puede hacer usando un algoritmo "estándar" es usar A * periódicamente y desde que determina dónde debe moverse el dron.

A medida que te acercas al jugador, estarás calculando cada vez más rápido ya que el espacio de búsqueda es, en teoría, más pequeño.

uso de este, que sería ser posible que el jugador encuentre un conjunto de posiciones que, cuando se mueve entre ellas hace que el avión no tripulado para conseguir "pegado" sólo mover hacia atrás y adelante, pero ese tipo de optimizaciones son situación- un algoritmo específico y general no los incluirá.

Esencialmente, do tienen un espacio de búsqueda fijo cada "marco", pero solo tiene que ejecutar cada cuadro para decidir qué hacer.

Es probable que haya cambios en A * que cubran las perturbaciones menores entre las ejecuciones, pero no conozco ninguno fuera de mi cabeza.

Fuente

2012-01-19 15:46:57 cdeszaq

Esto fue en realidad lo primero que pensé. Uno de los problemas con esta solución es que calcular el camino puede llevar mucho tiempo al dron y luego su movimiento podría verse más o menos así: moverse un poco, luego detenerse y calcular, luego moverse nuevamente, luego calcular de nuevo, etc. me gusta moverme constantemente (algo así como la forma en que los fantasmas se mueven en pacman). – conectionist

Estoy de acuerdo, A * es probablemente su mejor opción. Querrá poder detener A * en medio de un cálculo cuando el humano se haya movido. También deberá actualizar los objetivos de inicio y fin cada vez que el ser humano o el dron se hayan movido. Supongo que también podría usar algo como el algoritmo de Johnson para encontrar todos los caminos más cortos entre todas las posiciones posibles y luego usarlo como una tabla de búsqueda. Eso debería funcionar si el laberinto no es dinámico. http://en.wikipedia.org/wiki/Johnson%27s_algorithm – Justin

@Justin - Me gusta la idea de la búsqueda ..._ Mucho_ más rápido que hacer A * continuamente. Puede usar la misma idea memorada _with_ A * y almacenar en caché los resultados. Luego, construirás lentamente la tabla de búsqueda según dónde estén el jugador y el dron, ignorando las partes "no visitadas" del laberinto hasta que se necesiten. – cdeszaq

Algoritmo (s) para encontrar entidades en movimiento en un laberinto

Respuesta

Cuestiones relacionadas