Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
А что мешает сгенерировать сетку и проверить её узлы на перекрытие объектами?
Кроме того в подобных реализациях есть проблема движения «по стеночке». Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё.
Кроме того в подобных реализациях есть проблема движения «по стеночке». Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё.
А что мешает сгенерировать сеткуРасход памяти?
Довольно часто бывает что оптимальнее обойти кучку препятствийМожете привести пример, когда это не будет частным случаем алгоритма из статьи?
qiao.github.io/PathFinding.js/visual
там есть возможность посмотреть примеры поиска используя разные алгоритмы:
Да, можно сказать что этот trace не тот-же самый, но основная проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.
Соседние точки в сетке не надо хранить в памяти, они легко генерируются на лету просто добавляя шаг сетки.
там есть возможность посмотреть примеры поиска используя разные алгоритмы:
trace
a* по сетке
Да, можно сказать что этот trace не тот-же самый, но основная проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.
Расход памяти?
Соседние точки в сетке не надо хранить в памяти, они легко генерируются на лету просто добавляя шаг сетки.
Так вы привели тот же самый алгоритм (А*). А зачем вы привели trace, для меня загадка.
Я, может, туплю, но имхо, за динамическую генерацию сетки вы будете расплачиваться качеством найденного пути. За размер ячеек вы тоже будете расплачиваться. И все равно расход ресурсов у вас будет выше на хоть сколько-то вменяемых размерах данных. В том числе потому, что вы будете генерировать по целой пачке ячеек на пустые линии без препятствий.
проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.А в чем проблема-то? Не трудно доказать, что любой кратчайший путь будет касаться хотя бы одного из препятствий. У вас на сетке он (А*) точно также идет по стеночке (еще и не кратчайшим путем). При этом решение из сабжа позволяет работать с бесконечной точностью без роста накладных расходов.
Я, может, туплю, но имхо, за динамическую генерацию сетки вы будете расплачиваться качеством найденного пути. За размер ячеек вы тоже будете расплачиваться. И все равно расход ресурсов у вас будет выше на хоть сколько-то вменяемых размерах данных. В том числе потому, что вы будете генерировать по целой пачке ячеек на пустые линии без препятствий.
Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё
Имеете в виду, что может быть выгоднее сгенерировать неоптимальный по длине путь "в обход", чем долго возиться с большим количеством шагов на оптимальном пути "между препятствиями"?
Очень круто
Здорово. Применить к построению красивых графов, вершины которых имеют подписи или иллюстрации, помещающиеся в кругах —просто отлично, чтобы не было наложений на вершины.
Прошло почти 20 лет, а алгоритмы обхода препятствий реализованные в трассировщике спектра — так и не смогли повторить, скопировать, или украсть. А между прочим, там всё это есть…
Ссылочку можно?
Предполагаю что речь об этом, но насчет не смогли ли, не уверен.
Сам не использовал, а по картинкам, вроде бы ничего революционного.
А я использую.
После составления правил трассировки — остаётся только дождаться результата. Намного приятнее ручной разводки. Причём если вы попробуете найти автоматическую разводку с современных пакетах до 1000$ — то подобного качества не обнаружится.
В более дорогих есть, и там используется та-же спектра.
После составления правил трассировки — остаётся только дождаться результата. Намного приятнее ручной разводки. Причём если вы попробуете найти автоматическую разводку с современных пакетах до 1000$ — то подобного качества не обнаружится.
В более дорогих есть, и там используется та-же спектра.
Хороший перевод, вспомнил, что-то подобное смотрел в диздоке (или журнале разработчиков?) Left For Dead'а. Там как раз выводили алгоритмы что бы зомби бежали за игроками при этом красиво огибая препятствия и не сильно друг в друга врезаясь. Надо поискать, должно же быть полезно даже теперь…
Интересно! Я так понимаю что строится фактически аналог графа видимости в полигоне с дырками ( типа такого), только для круглых препятствий. Думаю, в статье не помешало бы упоминание этого и сравнение с ним.
Открыл оригинал статьи — залип на час, играясь окружностями :)
правильно ли я понимаю, что это просто алгоритм Дейкстры на графе? Ну и граф нужно сначала построить понятным способом
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск пути среди круглых препятствий