Комментарии 10
Будем брать узел справа, слева, сверху и снизу. Для простоты, узлы имеют названия частей света
и более про стороны свет в статье мы не услышим )
Так же непонятно в чем простота, если переменные даже не назвали как Vn, Vw, Vs, Ve.
А почему не так как я показал по черным пунктирам? Или это графическая условность? Тогда, по идее, нужно рисовать от центров квадратов.
Алгоритм идёт от пикселя к пикселю, поэтому пути получаются соответствующие. На картинке выше, я показал в чём разница "человеческого" и "компьютерного" пути. Если мы возьмём рисунок и просто проведём линию, то получим "истинный" короткий путь.
В статье я рассчитывал абсолютную ошибку, и можно заметить, что на диагоналях она формируется максимальная.
Алгоритм идёт от пикселя к пикселю, поэтому пути получаются соответствующие
То что я нарисовал всё равно более оптимальный маршрут от пикселя к пикселю.
На картинке выше, я показал в чём разница "человеческого" и "компьютерного" пути
Не-не-не, для адаптации прямой на сетчатой поверхности есть алгоритм Брезенхэма. Но и даже его вы не использовали на той картинке где я нарисовал черным пунктиром. Там у вас достаточно пикселей чтобы двигаться по пунктиру. ЛИБО, как я и отметил выше, вы изначально неверно отобразили работу алгоритма, если вы за пиксель считаете просто один квадрат лабиринта, тогда вам нужно соединять центры квадратов, а не рисовать тонкие линии вдоль стен.
В статье я рассчитывал абсолютную ошибку, и можно заметить, что на диагоналях она формируется максимальная.
Пардон, но я не готов обсуждать сам алгоритм.
на сетчатой поверхности есть алгоритм Брезенхэма
На самом деле, алгоритм Брезенхема даст путь такой же длины. Он же только на 8 соседних клеток может переходить. Значит там все ребра будут или по диагонали, или вдоль сетки. От перестановки слагаемых сумма не меняется, т.ч. можно сначала все вертикальные шажки сделать, а только потом все диагональные. На прямую вообще не похоже, но длина пути по пикселям та же самая.
На самом деле, алгоритм Брезенхема даст путь такой же длины
Ну я к длине не особо и прикапываюсь. Я о самом характере построения маршрута. Запустите в этот лабиринт A* и посмотрите как он построит. Просто во второй картинке что заставит алгоритм сделать два шага вверх? Мне кажется логичным сразу идти по диагонали или у вас вес диагонального шага тоже равен 1?
Посмотрел по формулам, у вас distance это скорее steps, то есть число шагов. Формально шагов вы сделаете столько же, но все равно непонятно почему ваш алгоритм жмётся к стенкам а не идёт по прямой.
Он может сделать сначала все шаги по диаганали, потому что это в сторону конца, а потом все по вертикали, потому что только в ту сторону кратчайший путь.
Кстати, я не автор. Похоже, у автора в статье расстояние - это именно длина пути вдоль сетки с 8 соседями. С корнями и вещественными числами.
Вдоль стенок алгоритм жмется потому, что ребра в каждой вершине перебираются в одном и том же порядке, без перемешивания и дополнительного рандома. Если и туда и сюда расстояние в итоге будет одинаковое, то берется первое попашееся. И это первое попавшееся - всегда в одну и ту же сторону, пока или до стенки не дойдет путь, или оставшийся путь не станет из одних только диагональных кусочков, и оптимальное направление не изменится.
Какой-нибуть обход в ширину или дейкстра на такой сетке найдут примерно такой же путь.
Сначала алгоритм рассчитывает поля расстояний, а затем, используя их, рассчитывает кратчайший путь. Пример на картинке.
Какой-то гибрид обхода в ширину и Дейкстры с кучей получился. Как уже заметили выше - пути оно ищет не кратчайшие. Чем оно лучше обхода в ширину по 8 соседним точкам? Оно точно медленнее а пути найдет такие же. На картинках с линиями еще и пути будут оптимальными.
Раз уж вы про алгоритм пишите, то опишите хотя бы его ассимтотическую сложность, сравните с другими алгоритмами, опишите где и когда он применим.
Спасибо за замечания. FMM в своей основе имеет алгоритм Дейкстры, но отличается от него способом расчета значений узлов(смотрите мат. описание). FMM легко расширяем, в отличие от Дейкстры. Я видел как в одной работе FMM использовали на триангулированной поверхности для рассчёта полей расстояний.
В этой статье у меня не было цели сравнивать алгоритмы. В рунете очень мало информации о FMM, и я решил это исправить.
Метод быстрого марша (Fast Marching Method)