Comments 15
А что мешает сгенерировать сетку и проверить её узлы на перекрытие объектами?
Кроме того в подобных реализациях есть проблема движения «по стеночке». Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё.
Кроме того в подобных реализациях есть проблема движения «по стеночке». Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё.
0
А что мешает сгенерировать сеткуРасход памяти?
Довольно часто бывает что оптимальнее обойти кучку препятствийМожете привести пример, когда это не будет частным случаем алгоритма из статьи?
+1
qiao.github.io/PathFinding.js/visual
там есть возможность посмотреть примеры поиска используя разные алгоритмы:
Да, можно сказать что этот trace не тот-же самый, но основная проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.
Соседние точки в сетке не надо хранить в памяти, они легко генерируются на лету просто добавляя шаг сетки.
там есть возможность посмотреть примеры поиска используя разные алгоритмы:
trace![image](https://habrastorage.org/r/w1560/getpro/habr/comment_images/26f/0dc/510/26f0dc510d3ad078ff26f6c1ce5b7f32.png)
![image](https://habrastorage.org/getpro/habr/comment_images/26f/0dc/510/26f0dc510d3ad078ff26f6c1ce5b7f32.png)
a* по сетке![image](https://habrastorage.org/r/w1560/getpro/habr/comment_images/573/1f9/84d/5731f984d0379c52b9248366cdd108ac.png)
![image](https://habrastorage.org/getpro/habr/comment_images/573/1f9/84d/5731f984d0379c52b9248366cdd108ac.png)
Да, можно сказать что этот trace не тот-же самый, но основная проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.
Расход памяти?
Соседние точки в сетке не надо хранить в памяти, они легко генерируются на лету просто добавляя шаг сетки.
0
Так вы привели тот же самый алгоритм (А*). А зачем вы привели trace, для меня загадка.
Я, может, туплю, но имхо, за динамическую генерацию сетки вы будете расплачиваться качеством найденного пути. За размер ячеек вы тоже будете расплачиваться. И все равно расход ресурсов у вас будет выше на хоть сколько-то вменяемых размерах данных. В том числе потому, что вы будете генерировать по целой пачке ячеек на пустые линии без препятствий.
проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.А в чем проблема-то? Не трудно доказать, что любой кратчайший путь будет касаться хотя бы одного из препятствий. У вас на сетке он (А*) точно также идет по стеночке (еще и не кратчайшим путем). При этом решение из сабжа позволяет работать с бесконечной точностью без роста накладных расходов.
Я, может, туплю, но имхо, за динамическую генерацию сетки вы будете расплачиваться качеством найденного пути. За размер ячеек вы тоже будете расплачиваться. И все равно расход ресурсов у вас будет выше на хоть сколько-то вменяемых размерах данных. В том числе потому, что вы будете генерировать по целой пачке ячеек на пустые линии без препятствий.
0
Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё
Имеете в виду, что может быть выгоднее сгенерировать неоптимальный по длине путь "в обход", чем долго возиться с большим количеством шагов на оптимальном пути "между препятствиями"?
0
Очень круто
0
Здорово. Применить к построению красивых графов, вершины которых имеют подписи или иллюстрации, помещающиеся в кругах —просто отлично, чтобы не было наложений на вершины.
0
Прошло почти 20 лет, а алгоритмы обхода препятствий реализованные в трассировщике спектра — так и не смогли повторить, скопировать, или украсть. А между прочим, там всё это есть…
0
Ссылочку можно?
+1
А я использую.
После составления правил трассировки — остаётся только дождаться результата. Намного приятнее ручной разводки. Причём если вы попробуете найти автоматическую разводку с современных пакетах до 1000$ — то подобного качества не обнаружится.
В более дорогих есть, и там используется та-же спектра.
После составления правил трассировки — остаётся только дождаться результата. Намного приятнее ручной разводки. Причём если вы попробуете найти автоматическую разводку с современных пакетах до 1000$ — то подобного качества не обнаружится.
В более дорогих есть, и там используется та-же спектра.
0
Хороший перевод, вспомнил, что-то подобное смотрел в диздоке (или журнале разработчиков?) Left For Dead'а. Там как раз выводили алгоритмы что бы зомби бежали за игроками при этом красиво огибая препятствия и не сильно друг в друга врезаясь. Надо поискать, должно же быть полезно даже теперь…
0
Интересно! Я так понимаю что строится фактически аналог графа видимости в полигоне с дырками ( типа такого), только для круглых препятствий. Думаю, в статье не помешало бы упоминание этого и сравнение с ним.
+1
Открыл оригинал статьи — залип на час, играясь окружностями :)
0
правильно ли я понимаю, что это просто алгоритм Дейкстры на графе? Ну и граф нужно сначала построить понятным способом
0
Sign up to leave a comment.
Поиск пути среди круглых препятствий