Búsqueda de ruta en entornos 3D reales (por ejemplo, Edificios)

Question

¿Hay algún algoritmo de ruta que sea adecuado también para entornos 3D reales, p. 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 de 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

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 volumen conocido en el espacio), recomendaría 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. Ver el libro de texto clásico de Jean-Claude Latombe

Para los escenarios más simples, es probable que pueda conformarse con algoritmos de planificación de ruta usados ​​en primera persona juegos de ordenador, que son similares a Dijkstra, A * (example)

Answer 2

Para un algoritmo de aproximación puede mapear 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.