В связи с разработками на тему процедурной генерации дошли руки и до алгоритма поиска кратчайшего пути. Первоначально, по уже забытым причинам, я обозначил его как алгоритм Дейкстры – выдающегося учёного, оказавшего огромное влияние на развитие компьютерной индустрии. Но в комментариях указали, что это волновой алгоритм.
Данный алгоритм во-первых очень прост, а во-вторых полезен не только для поиска кратчайшего пути.
Он работает на карте, состоящей из клеток.
Задача ставится так: если мы находимся в клетке (x, y), то каким кратчайшим маршрутом можно добраться в клетку (x1, y1)?
Очевидно, кратчайший маршрут это прямая линия. Но если на карте присутствуют препятствия, нужно будет их обходить, и тогда всё выглядит уже не так тривиально.
Именно такая задача решается, кстати, в игре Color Lines:
Алгоритм работает с любыми препятствиями, ему всё равно. Кроме того, маршрута из точки в точку может и вообще не существовать – и алгоритм сможет это определить.
Как это работает
Алгоритм описывают в терминах расстояний от начальной клетки, но мне кажется, что более наглядно можно представить его как растекание жидкости. Ведь мы знаем, что "вода дырочку найдёт", и если на карте существует маршрут между двумя клетками, жидкость обязательно соединит их.
Начнём с того, что капнем воду в начальную клетку. Она становится "мокрой". Далее повторяется один и тот же процесс:
- любая "мокрая" клетка делает "мокрыми" клетки вокруг себя, если они более "сухие", чем она
Каким образом можно построить кратчайший маршрут от любой клетки до источника? Здесь мы можем связать "мокрость" клетки с расстоянием от источника. Чем дальше от источника, тем "суше" становится клетка.
Значит, начав поиск с любой клетки, мы всегда должны выбирать вокруг неё более "мокрую" клетку, и таким образом дойдём до самой "мокрой", то есть до источника.
Развернув этот путь задом наперёд, мы получим маршрут от источника до заданной клетки.
Подготовка карты
В начальную клетку маршрута запишем расстояние до неё самой, то есть 0. Во все остальные клетки карты, которые не содержат препятствий, запишем какое-нибудь очень большое число. Назовём его MAX. Этим числом отмечаются ещё не исследованные клетки, а очень большое оно для того, чтобы быть заведомо больше любого другого расстояния.
Если карта очень большая, то в принципе создаётся вероятность, что максимальное расстояние на карте может сравняться с MAX. В этом случае я бы выбрал другой способ для пометки таких клеток, например отрицательные числа, или доп. карта со служебными битами. Но тогда немного поменяются и условия сравнения в алгоритме.
Работа алгоритма
Нужно пройтись по всем клеткам карты (кроме клеток с препятствиями) и сравнить их значение с соседними клетками (сверху, снизу, слева, справа). Если в клетке (x, y) хранится число d, а в соседней клетке число больше чем d+1, то в эту соседнюю клетку надо записать число d+1.
Данную процедуру нужно повторять до тех пор, пока происходят изменения.
Почему это работает
Сперва карта содержит только одну начальную клетку с расстоянием 0. Перебирая все клетки подряд, мы обязательно дойдём до этой клетки, где бы она ни находилась.
В клетке записано 0, и мы ищем соседей, в которых записано больше чем 1. Например, мы встретили в клетке число MAX, которое заведомо больше, значит мы запишем туда 1.
После первой итерации вокруг клетки с числом 0 появились клетки с числом 1, отстоящие от неё на 1 шаг. Далее повторяем процесс. Если мы нашли клетку с числом 1, то ищем соседей, у которых значение больше 2, и записываем в них 2. Получился очередной слой клеток с расстоянием 2 до начальной. Повторяем ещё раз, получаем слой клеток с расстоянием 3 до начальной, и так далее.
Если, допустим, у клетки с числом 3 мы найдём соседа не с MAX, а с числом 5, то это будет значить, что какой-то альтернативный маршрут уже дошёл до этой клетки, и установил ей расстояние 5 до начальной. Но так как наша клетка имеет расстояние 3, то соседняя с ней должна иметь расстояние 4. Значит, найден более короткий маршрут, и мы перезаписываем значение 4 в клетку, где было 5.
Приложения
Если маршрут не существует, то алгоритм не дойдёт до целевой клетки, и её значение останется равно MAX. Поэтому если мы видим, что у целевой клетки значение MAX, то уже сразу знаем, что маршрута нет.
Кроме маршрутов, алгоритм можно использовать для управления поведением врагов, например.
Если игрок находится в какой-то клетке, то эта клетка является источником. Если врагу надо догнать игрока, он всегда должен переходить из своей клетки в клетку с меньшим значением, а если убежать от игрока, то наоборот, в клетку с большим значением.
Также можно эмпирически оценивать объём некой области на карте. Если мы встречаем в клетках большие числа, значит они находятся на значительном расстоянии от источника и область скорее всего большая. Также можно просто сосчитать все клетки, которые не содержат препятствий и не равны MAX.
Реализация
Я сделал алгоритм на JavaScript, который можно смотреть онлайн.
https://js.do/nandakoryaaa/dijkstra
Если водить курсором мыши поверх карты, то можно видеть, как перестраиваются значения клеток. Чем темнее клетка, тем ближе она к источнику.
Замечание: по периметру карты клетки работают некорректно, так как мне было лень писать дополнительные проверки, и я просто не включаю их в обработку.