Учитывая начало и цель, как найти кратчайший путь в сетке навигации?
Я прибегнул к «алгоритму A * на сетке навигации» только для того, чтобы получить неправильные способы оценки g-значений, как это
или это
Суммируя длину отрезков синей линии, мы получаем значение g, но оно завышается (значение g следует недооценивать). Этот алгоритм будет возвращать оптимизированный путь, но не гарантированно будет самым коротким.
Единственный способ, которым я могу придумать, — это нарисовать график видимости на основе навигационной сетки. Но это будет стоить слишком много памяти.
Есть ли другие способы расчета кратчайшего пути в сетке навигации?
Решение
Чтобы приблизить кратчайший путь к тому, что вы имеете в виду, вы должны прекратить использовать точки фиксации в качестве узлов A-звезды, то есть прекратить использовать центр треугольников или центр треугольника.
Попробуйте переместить точки по мере распространения звезды.
Например, используйте треугольные узлы на треугольнике, которые:
-
либо пересечение края треугольника следующего узла A-звезды с сегментом, образованным предыдущим узлом A-звезды, и пунктом назначения
-
или ближайшая точка от пересечения, упомянутого выше, на краю треугольника следующего узла A-звезды
Или попробуйте изменить узлы пути после вычисления вашей звезды, как в настоящее время, используя аналогичные критерии.
Обратите внимание, что это сгладит окончательный путь (как красная линия на ваших чертежах).
Но это только поможет уменьшить завышенную оценку, но это не гарантирует, что вы найдете кратчайшие пути, как вы и предполагали.
Лучше попытайтесь изменить узлы пути после вычисления вашей звезды, используя центр треугольников, используя алгоритм вытягивания строки a.k.a. Это даст вам кратчайший путь через треугольники, пройденные выходным путем A-звезды.
Другие решения
Других решений пока нет …