¿Alguien puede sugerir documentos o algoritmos sobre el cálculo de los caminos más cortos en espacios euclidianos con polígono no convexo como obstáculos?
path-finding
aneuryzm
fuente
fuente
Respuestas:
El enfoque más simple es convertir los polígonos no convexos en múltiples convexos, luego hacer una colisión convexa normal y encontrar rutas (a través de A * o D * o lo que sea). El primer proceso a menudo se llama triangulación en geometría computacional, y hay varias formas comunes de hacerlo.
fuente
Puede que esta no sea la respuesta exacta a su pregunta, pero puedo sugerirle un enfoque sobre este tema.
En realidad su problema son dos problemas combinados.
Y el segundo problema está incrustado en el primero. Puedo recomendar comprender la búsqueda ciega primero. Aquí hay una presentación muy simple al respecto: Blind Search
Si lee el documento para construir el espacio de estado, necesitará generar puntos de estado y deben ser legales, lo que significa que estos estados pueden estar en su camino más corto para que no choquen con ningún objeto en su espacio. A partir de ahora puedes continuar con los algoritmos de colisión euclidianos. Después de construir su espacio de estado y árbol de búsqueda restringido con colisiones, puede elegir cualquiera de los algoritmos de ruta más cortos o uno propio o uno híbrido modificado.
fuente