Некоторые способы решения задачи поиска кратчайшего пути среди неизвестных препятствий:

• Алгоритм Дейкстры. 14 На каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё. 1 Завершает работу, когда цель достигнута (или просмотрены все вершины). 1
• Двухэтапные алгоритмы. 1 Запускаются в два этапа: препроцессинг (запускается единожды для графа и может занимать много времени, рассчитывает вспомогательную информацию) и запрос (запускается по требованию для пары вершин и должен выполняться очень быстро). 1
• ALT-алгоритм. 1 На препроцессинге берут небольшое количество вершин (например, 16), обозначают их как ориентиры, для каждого из ориентиров считают кратчайшие пути до всех вершин и сохраняют эти пути. 1 На запросе используют A*, если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром — по нему идут в первую очередь. 1
• Непрерывное представление данных. 2 На вход системе подают бинарное чёрно-белое изображение — «карту» с препятствиями, где в качестве препятствий выступают простые полигоны без самопересечений. 2 Исходное растровое изображение карты преобразовывают к непрерывному представлению с заданной точностью, после чего пользователь может выбирать начальную и конечную точки, получая кратчайший путь между ними. 2 Минимальный путь вычисляется с помощью построения графа видимости полигональной области и нахождения маршрута на этом графе одним из классических алгоритмов. 2