Pull to refresh

Comments 18

Ну и как теперь определить какую гифку вы имели ввиду и не поменял ли ее с тех пор автор?
Вот эта:
image
?
Почему не a*?
Зависит от эвристики ©
Но да, если бы эвристикой было бы простое эвклидово расстояние, он пошел бы вдоль стенки
Вот так как-то image
Хотя зависит от того как подкрутить h (эвристику) и g (вес ребра)
Это не A star, путь явно не оптимальный. Либо подкручено не правильно.

Для квадратов давно разработаны эвристики, для только вертикаль/горизонталь — Манхэттен, для плюс диагоналей — Чебышев.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*
Где можно срезать?
Вот здесь?image
Так длина пути не изменится.
1 клетка — 1 шаг. Как раз по Чебышеву.
Если хочется минимизировать количество изломов — то нужно либо напрямую за них штраф добавлять, либо отказаться от чебышева в пользу эвклида. (чтобы шаг по диагонали был не 1, а sqrt(2))
Да не а-стар это, картинка не такая должна быть. :)

qiao.github.io/PathFinding.js/visual — здесь эмулируете? Если нет — дайте ссылку где именно, мне прямо интересно посмотреть как A* дает такую картинку.

A* будет давать другую, вот такую:


То что на вашем скрине — судя по всему Trace.
С Weight 5 и более и Octile или Manhattan получилось несколько похожее получить — но это не правильно при диагональных переходах, Manhattan точно нельзя (Octile не знаю как работает эвристика).

Скажите уже параметры, не томите.
Что значит «неправильно»? Что вам визуально не нравится рисунок?
Путь кратчайший? Кратчайший.
Фронтир на момент достижения пути — минимизирован. (Меньше посетили клеток перед тем как нашли финиш)
Эвклида я взял:
image
Да, согласен, был не прав — по клеткам столько же, уже прочитал ваш коммент выше. Если брать длину желтой ломаной — то так больше получается.
Ну у меня была цель минимизировать количество «синего» — посещенных клеток.
А так, можно в эвристику затолкать много чего. Например направление на север сделать менее желанным, итп
Да, я знаю — у меня AI для платформера (вернее лабиринта) сча в разработке, своя реализация A*, все бегают/прыгают/лазают, просто у меня идет подсчет переходов между нодами (не клетки, так генерятся), там везде разные длины, я удивился что находит такой путь, но длина по клеткам в общем то это объясняет.

Ну она очень странно выглядит. На следующем шаге берутся смежные вершины. А тут после упора в стену анимация прыгает с одной стороны на другую. Понятно что можно извратиться и с эвристикой и с поиском соседей так что получиться нечто похожее. Но это так и к поиску в ширину можно свести

// закрываем точку
closedPoints.Add(openPoints[0]);
// открываем новые точки и удаляем закрытую
openPoints = ClosePoint(0, openPoints, closedPoints, worldData, pfType, targetPoint);


Это обычно делается в основном цикле, зачем вы вынесли это отдельно для первой точки?

По оптимизации не очень понятно, слишком кратко написали. Можете попонятнее расписать, это самая интересная часть статьи.

Кстате у вас много открытых пространств, Jump Point Search искал бы быстрее.
JPS будет сканировать почти всю карту если нужно обойти гору. А карта большая.
Если не учитывать вопрос особенностей реализации A* алгоритма и, соответственно, его производительность даже при поиске пути одного NPC, что во многих случаях может оказаться минусом алгоритма, то в минусы можно записать еще и игнорирование данным алгоритмом движущихся объектов и любых изменений воксельного мира после нахождения оптимального пути. Проще говоря, достаточно поставить единственный воксель на пути NPC и он застрянет и не узнает об этом, а постоянные перерасчеты A* будут стоить крайне дорого.
На открытых пространствах алгоритм считает быстро.
UFO just landed and posted this here
Sign up to leave a comment.

Articles