Pathfinding basado en polígono

Question

Implementé una cuadrícula base A * pathfindinder en Java. Me gustaría hacer una malla/Pathfinder navegación basada polígono, pero el problema que tengo es la siguiente:

Si encontrara la ruta naranja entonces podría usar algo como a funnel algorithm para enderezarlo para conseguir la deseada ruta (azul). Sin embargo, si el programa calcula el costo de cada una de las rutas, rojo y naranja, entonces dirá que el rojo es el más barato. ¿Cómo programo mi algoritmo A * y/o creo mis mallas para que esto no suceda?

Answer 1

El capítulo 15 en Computational Geometry: Algorithms and Applications describe y resuelve exactamente este problema: el espacio libre se puede describir mediante un mapa trapezoidal, pero las rutas que se encuentran utilizando el mapa no son necesariamente las más cortas. La representación recomendada (también discutida en LaValle's Planning Algorithms (Section 6.2.4)) es un llamado gráfico de visibilidad, que tiene bordes que conectan los vértices de los obstáculos.

El seudocódigo y las figuras están disponibles en la página principal del libro y el Google preview también contiene partes del capítulo.

Answer 2

debe consultar este enlace: http://alienryderflex.com/shortest_path/ explica cómo calcular la ruta más corta dentro de un polígono, una explicación muy clara y la implementación del código.

Answer 3

Disculpa, no podemos ayudarte con tu pregunta directamente, pero hemos migrado un pathfinder basado en polígono para haxe y puede compilarse en java (solo probado con swing hasta ahora pero podría intentarlo pronto slick2d) y podría integrarse en Java proyecto dado un poco de investigación. Se llama hxDaedalus y está en github y podría ser un punto de referencia interesante.