c++ - a*pathfinding

Pathfinding en entornos 3D reales(por ejemplo, Edificios)

Question

¿Existe un algoritmo de identificación de ruta adecuado también para entornos 3D reales, por ejemplo, edificios reales con múltiples escaleras, etc. Una biblioteca C ++ o implementación abierta sería espléndida ;-) Una solución que vi fue Djikstra pero me pregunto si hay algo más óptimo. Normal A * no funcionaría mejor que Djikstra ya que la heurística a distancia no funciona bien (Posición un piso por encima del destino). Otra solución que estoy considerando actualmente es la asignación del entorno 3D en un gráfico 2d. Entonces, si hay alguna implementación / biblioteca de C ++ disponible yendo de esta manera, sería útil también.

Answer 1

Para un algoritmo de aproximación, puede asignar fácilmente el 3d a una curva 1d y atravesar un octárbol con un código gris. De esa forma puedes reordenar cada ruta. No sé si hay una garantía de estar dentro de la solución óptima, pero debe ser mejor que cualquier método heurístico.

Answer 2

Si la ruta tiene que tener en cuenta la capacidad de navegar a través de obstáculos (es decir, el movimiento es el de una entidad con un volumen conocido en el espacio), le recomiendo consultar la literatura sobre la planificación del movimiento del robot. La noción de un espacio de configuración le permite manejar los cambios en pose para poder enfrentar los obstáculos. Vea el libro de texto clásico de Jean-Claude Latombe

Para escenarios más simples, probablemente pueda conformarse con algoritmos de planificación de ruta utilizados en juegos de computadora en primera persona, que son similares a Dijkstra, A * (ejemplo)