Реализация волнового алгоритма нахождения кратчайшего пути к динамически движущимся объектам в unity3d на C# в 2d игре

[NikolayJuly]

Мне статья нравится. Особенно нравится подход, когда пробуют все своими руками. Но есть пара замечаний.
1) Вы используете термины, которе тут абсолютно лишние: «окрестности Мура», «окрестности фон Неймана». Статья написана для неискушенного пользователя, а вот такие термины, как бы намекают на очень сильную связь с научным трактатом. А ведь можно было смело без терминов обойтись.
2) Либо у конкретно вашей реализации, либо у волнового алгоритма в целом нету возможности задать «проходимость клетки», то есть поиск пути в ситуации, где клетки могут быть пройдены с разной скоростью и «кратчайший» != «оптимальный». Например может будет быстрее пробежать по мосту, чем плыть через реку.

[HomoLuden]

Кстати, идея… А что, если задать целочисленную цену (штраф) прохода у ячейки и задерживать волну в клетке соответственно штрафу прохода? Фронты волны двигать как в пошаговой стратегии — итерациями.

[andreishe]

Тогда количество итераций будет расти вместе со «штрафом». Во взвешенном графе лучше искать алгоритмом Дейкстра.

[KuratnikDmitry]

Спасибо, на самом деле без терминов будет лучше, поправил

[KuratnikDmitry]

2) Конкретно в моей реализации нету возможности. А вообще такая возможность есть. тогда нужно клетке с плохой проходимостью ставить не 0, а например 2 если это поле, 4 если это болото и тд. В таком случае нужно будет поправить проверку на «уже помеченную клетку», так как сравнение с 0 не подойдет. Если будет необходимость, могу описать как это сделать или помочь в реализации.
В эту стаью не включал, так как не хотел усложнять. Цель — максимально доступно и понятно описать алгоритм на практическом примере.

[maaGames]

Кратчайший путь, по определению, имеющий минимальную длину в «километрах». Умный в гору не пойдёт, умный гору обойдёт. Но, если лезть через гору будет короче, то это и будет кратчайшим путём. А вот для поиска оптимального пути уже можно (нужно) учитывать скорость прохождения участков. Тогда нужно использовать взвешенный граф, а не просто граф, как при волновой трассировке.

[KuratnikDmitry]

Если у кого-то будут замечания по статье или коду, напишите мне на хабре или на почту [e-mail]. Исправлю.

[Amomum]

Если карта не очень большая, может быть проще заранее посчитать кратчайшие пути из каждой точки в каждую точку (пропуская точки с препятствиями, конечно)? Например, алгоритмом Флойда-Уоршелла.

[PHmaster]

Если я правильно понял суть Вашей модификации алгоритма, то Ваш юнит застрянет, встретив на пути препятствие нетривиальной конфигурации.

[boeing777]

Если Вы говорите о проблеме локального оптимума, то вот здесь автор предложил решение. Правда, в той статье рассматривался метод потенциальных полей, но, я думаю, идею можно адаптировать и для волнового алгоритма.

[PHmaster]

Не знаю, что там с локальным оптимумом, я говорю конкретно вот об этом:

Теперь нам всеголишь нужно пройтись по соседним клеткам. Посчитать расстояние с каждой соседней клетки до объекта F и переместиться в ячейку с минимальным расстоянием.

И следующим за ним куском кода. То есть, автор взял волновой алгоритм и выкинул из него… волновой алгоритм. И теперь объект не ищет маршрут, а просто как по компасу стремится сократить расстояние между собой и целью. Что будет, если на пути его окажется препятствие — представить не трудно.

[kumbr_87]

Код можно значительно ускорить и немного обезопасить:
1. Ограничить количество шагов поиска пути, т.к. если юнит окажется заперт то алгоритм зациклится.
2. Значительно увеличить скорость поиска пути можно проверяя только граничные клетки. Для этого можно сохранять их в массив например. Новые граничные клетки соответственно сохранять во второй массив и в конце итерации обменивать массивы местами. Тогда не придется при каждой итерации просматривать всю карту, это значительно повышает скорость работы. Особенно на очень запутанных картах.