Комментарии 12
Мне статья нравится. Особенно нравится подход, когда пробуют все своими руками. Но есть пара замечаний.
1) Вы используете термины, которе тут абсолютно лишние: «окрестности Мура», «окрестности фон Неймана». Статья написана для неискушенного пользователя, а вот такие термины, как бы намекают на очень сильную связь с научным трактатом. А ведь можно было смело без терминов обойтись.
2) Либо у конкретно вашей реализации, либо у волнового алгоритма в целом нету возможности задать «проходимость клетки», то есть поиск пути в ситуации, где клетки могут быть пройдены с разной скоростью и «кратчайший» != «оптимальный». Например может будет быстрее пробежать по мосту, чем плыть через реку.
1) Вы используете термины, которе тут абсолютно лишние: «окрестности Мура», «окрестности фон Неймана». Статья написана для неискушенного пользователя, а вот такие термины, как бы намекают на очень сильную связь с научным трактатом. А ведь можно было смело без терминов обойтись.
2) Либо у конкретно вашей реализации, либо у волнового алгоритма в целом нету возможности задать «проходимость клетки», то есть поиск пути в ситуации, где клетки могут быть пройдены с разной скоростью и «кратчайший» != «оптимальный». Например может будет быстрее пробежать по мосту, чем плыть через реку.
Кстати, идея… А что, если задать целочисленную цену (штраф) прохода у ячейки и задерживать волну в клетке соответственно штрафу прохода? Фронты волны двигать как в пошаговой стратегии — итерациями.
Спасибо, на самом деле без терминов будет лучше, поправил
2) Конкретно в моей реализации нету возможности. А вообще такая возможность есть. тогда нужно клетке с плохой проходимостью ставить не 0, а например 2 если это поле, 4 если это болото и тд. В таком случае нужно будет поправить проверку на «уже помеченную клетку», так как сравнение с 0 не подойдет. Если будет необходимость, могу описать как это сделать или помочь в реализации.
В эту стаью не включал, так как не хотел усложнять. Цель — максимально доступно и понятно описать алгоритм на практическом примере.
В эту стаью не включал, так как не хотел усложнять. Цель — максимально доступно и понятно описать алгоритм на практическом примере.
Кратчайший путь, по определению, имеющий минимальную длину в «километрах». Умный в гору не пойдёт, умный гору обойдёт. Но, если лезть через гору будет короче, то это и будет кратчайшим путём. А вот для поиска оптимального пути уже можно (нужно) учитывать скорость прохождения участков. Тогда нужно использовать взвешенный граф, а не просто граф, как при волновой трассировке.
Если у кого-то будут замечания по статье или коду, напишите мне на хабре или на почту devmobby@gmail.com. Исправлю.
Если карта не очень большая, может быть проще заранее посчитать кратчайшие пути из каждой точки в каждую точку (пропуская точки с препятствиями, конечно)? Например, алгоритмом Флойда-Уоршелла.
Если я правильно понял суть Вашей модификации алгоритма, то Ваш юнит застрянет, встретив на пути препятствие нетривиальной конфигурации.
Если Вы говорите о проблеме локального оптимума, то вот здесь автор предложил решение. Правда, в той статье рассматривался метод потенциальных полей, но, я думаю, идею можно адаптировать и для волнового алгоритма.
Не знаю, что там с локальным оптимумом, я говорю конкретно вот об этом:
И следующим за ним куском кода. То есть, автор взял волновой алгоритм и выкинул из него… волновой алгоритм. И теперь объект не ищет маршрут, а просто как по компасу стремится сократить расстояние между собой и целью. Что будет, если на пути его окажется препятствие — представить не трудно.
Теперь нам всеголишь нужно пройтись по соседним клеткам. Посчитать расстояние с каждой соседней клетки до объекта F и переместиться в ячейку с минимальным расстоянием.
И следующим за ним куском кода. То есть, автор взял волновой алгоритм и выкинул из него… волновой алгоритм. И теперь объект не ищет маршрут, а просто как по компасу стремится сократить расстояние между собой и целью. Что будет, если на пути его окажется препятствие — представить не трудно.
Код можно значительно ускорить и немного обезопасить:
1. Ограничить количество шагов поиска пути, т.к. если юнит окажется заперт то алгоритм зациклится.
2. Значительно увеличить скорость поиска пути можно проверяя только граничные клетки. Для этого можно сохранять их в массив например. Новые граничные клетки соответственно сохранять во второй массив и в конце итерации обменивать массивы местами. Тогда не придется при каждой итерации просматривать всю карту, это значительно повышает скорость работы. Особенно на очень запутанных картах.
1. Ограничить количество шагов поиска пути, т.к. если юнит окажется заперт то алгоритм зациклится.
2. Значительно увеличить скорость поиска пути можно проверяя только граничные клетки. Для этого можно сохранять их в массив например. Новые граничные клетки соответственно сохранять во второй массив и в конце итерации обменивать массивы местами. Тогда не придется при каждой итерации просматривать всю карту, это значительно повышает скорость работы. Особенно на очень запутанных картах.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация волнового алгоритма нахождения кратчайшего пути к динамически движущимся объектам в unity3d на C# в 2d игре