Комментарии 18
на первой гифке не a*
0
Ну и как теперь определить какую гифку вы имели ввиду и не поменял ли ее с тех пор автор?
Вот эта:
?
Почему не a*?
Зависит от эвристики ©
Но да, если бы эвристикой было бы простое эвклидово расстояние, он пошел бы вдоль стенки
Вот эта:
?
Почему не a*?
Зависит от эвристики ©
Но да, если бы эвристикой было бы простое эвклидово расстояние, он пошел бы вдоль стенки
0
Вот так как-то
Хотя зависит от того как подкрутить h (эвристику) и g (вес ребра)
Хотя зависит от того как подкрутить h (эвристику) и g (вес ребра)
0
Это не A star, путь явно не оптимальный. Либо подкручено не правильно.
Для квадратов давно разработаны эвристики, для только вертикаль/горизонталь — Манхэттен, для плюс диагоналей — Чебышев.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*
Для квадратов давно разработаны эвристики, для только вертикаль/горизонталь — Манхэттен, для плюс диагоналей — Чебышев.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*
0
Где можно срезать?
Вот здесь?
Так длина пути не изменится.
1 клетка — 1 шаг. Как раз по Чебышеву.
Вот здесь?
Так длина пути не изменится.
1 клетка — 1 шаг. Как раз по Чебышеву.
0
Если хочется минимизировать количество изломов — то нужно либо напрямую за них штраф добавлять, либо отказаться от чебышева в пользу эвклида. (чтобы шаг по диагонали был не 1, а sqrt(2))
+1
Да не а-стар это, картинка не такая должна быть. :)
qiao.github.io/PathFinding.js/visual — здесь эмулируете? Если нет — дайте ссылку где именно, мне прямо интересно посмотреть как A* дает такую картинку.
A* будет давать другую, вот такую:
То что на вашем скрине — судя по всему Trace.
qiao.github.io/PathFinding.js/visual — здесь эмулируете? Если нет — дайте ссылку где именно, мне прямо интересно посмотреть как A* дает такую картинку.
A* будет давать другую, вот такую:
То что на вашем скрине — судя по всему Trace.
0
С Weight 5 и более и Octile или Manhattan получилось несколько похожее получить — но это не правильно при диагональных переходах, Manhattan точно нельзя (Octile не знаю как работает эвристика).
Скажите уже параметры, не томите.
Скажите уже параметры, не томите.
0
Что значит «неправильно»? Что вам визуально не нравится рисунок?
Путь кратчайший? Кратчайший.
Фронтир на момент достижения пути — минимизирован. (Меньше посетили клеток перед тем как нашли финиш)
Эвклида я взял:
Путь кратчайший? Кратчайший.
Фронтир на момент достижения пути — минимизирован. (Меньше посетили клеток перед тем как нашли финиш)
Эвклида я взял:
0
Да, согласен, был не прав — по клеткам столько же, уже прочитал ваш коммент выше. Если брать длину желтой ломаной — то так больше получается.
0
Ну у меня была цель минимизировать количество «синего» — посещенных клеток.
А так, можно в эвристику затолкать много чего. Например направление на север сделать менее желанным, итп
А так, можно в эвристику затолкать много чего. Например направление на север сделать менее желанным, итп
0
Да, я знаю — у меня AI для платформера (вернее лабиринта) сча в разработке, своя реализация A*, все бегают/прыгают/лазают, просто у меня идет подсчет переходов между нодами (не клетки, так генерятся), там везде разные длины, я удивился что находит такой путь, но длина по клеткам в общем то это объясняет.
0
Ну она очень странно выглядит. На следующем шаге берутся смежные вершины. А тут после упора в стену анимация прыгает с одной стороны на другую. Понятно что можно извратиться и с эвристикой и с поиском соседей так что получиться нечто похожее. Но это так и к поиску в ширину можно свести
0
// закрываем точку
closedPoints.Add(openPoints[0]);
// открываем новые точки и удаляем закрытую
openPoints = ClosePoint(0, openPoints, closedPoints, worldData, pfType, targetPoint);
Это обычно делается в основном цикле, зачем вы вынесли это отдельно для первой точки?
По оптимизации не очень понятно, слишком кратко написали. Можете попонятнее расписать, это самая интересная часть статьи.
Кстате у вас много открытых пространств, Jump Point Search искал бы быстрее.
0
Если не учитывать вопрос особенностей реализации A* алгоритма и, соответственно, его производительность даже при поиске пути одного NPC, что во многих случаях может оказаться минусом алгоритма, то в минусы можно записать еще и игнорирование данным алгоритмом движущихся объектов и любых изменений воксельного мира после нахождения оптимального пути. Проще говоря, достаточно поставить единственный воксель на пути NPC и он застрянет и не узнает об этом, а постоянные перерасчеты A* будут стоить крайне дорого.
0
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Алгоритм поиска пути A* в воксельной 3d игре на Unity