Pathfinding óptima

Question

Fondo
Hay un mapa cuadrado con algunos obstáculos en él. Los obstáculos están representados por polígonos. He implementado siguiente ruta algoritmo de búsqueda:
1) Elegir precisión (que va a ser denotado por k)
2) Dividir mapa en cuadrados k x k.
3) Hacer el gráfico de los cuadrados de acuerdo a las siguientes reglas:
- Cada nodo representa un cuadrado
- Dos nodos están conectados si y sólo si están adyacentes y ninguno de ellos Cosist cualquier obstáculo
. 4) Encontrar camino más corto usando un algoritmo * (o Dijkstra o algún otro ...)

Este algoritmo funciona bastante bien, si no es un mapa dinámico. Esto significa que los obstáculos no se pueden mover.

Preguntas
1) ¿Es ese enfoque eficiente?
2) ¿Qué hacer en caso de obstáculos se pueden mover?
3) ¿Cómo tratar otros agentes? Vamos a considerar la situación donde hay 100agents en la habitación. Hay dos existe. Todos los agentes están en un grupo, y ese grupo cerca de una de las salidas. Si todos los agentes van a la salida más cercana, entonces va a causar un cuello de botella. Algunos de ellos debe ir a la otra salida para minimizar el tiempo necesario para salir. ¿Cómo conseguir tal resultado?

Answer 1

Utilice la A * Ruta como una guía general alrededor de los obstáculos estáticos y realizar href="http://www.red3d.com/cwr/steer/Obstacle.html" para la dinámica de obstáculos (más pequeñas). Reynolds también tiene un algoritmo para el cuello de botella de problemas. Él lo llama Queuing .