Быстрый поиск пути в подземелье

В данном документе описывается алгоритм поиска пути (pathfinder), использующий эвристический алгоритм breadth-first (первой области).

Поиск пути мы начнём из начальной точки и попытаемся найти кратчайший путь к точке назначения. Мы сделаем это путём рассчёта для каждого поля (квадрата) расстояния от него до начальной точки и как только мы достигнем цели, мы вернёмся по [квадратам] с наименьшими числами. Возможно, это звучит запутано, но рассмотрим это:

8767D9876  D - точка назначения
765678765
654567656
##3####4#  # - стена (непроходимая)
4321S1234  S - старт (начальная точка)

Числа представляют минимальное число шагов, требующееся чтобы пройти от начала до данного поля. Если мы теперь отследим обратный путь через наименьшие числа:

  67D
  567
  4
##3#### #
  21S

Мы сможем получить путь:

    D
  ...
  .
##.#### #
  ..S

который и будет то, что нам нужно. Также, можно было бы допустить диагональное перемещение (то, что хотят большинство искателей пути в roguelike-играх), или сделать его (перемещение) зависящим от местности. Это по выбору программиста.

Вот путь, который может осуществить этот алгоритм. 'Поле' ('square') - координата на карте. Эта реализация использует карту темницы, и стек. В стеке 'проталкивание' ('push') должно проталкивать значение наверх, 'выталкивание' ('pop') должно выталкивать последнюю вложенную в стек величину, и 'сдвиг' (shift') должен сдвигать ранее вытолкнутую величину (реверсивное выталкивание (reverse pop)).

1. Теперь начало - текущее поле.
2. Выберите смежное поле, которое ещё установлено в 0. Если такого нет, goto 5.
3. Назначьте выбранному полю значение текущего поля +1. Если выбранное поле - [конечная] цель, goto 7
4. Протолкните выбранное поле в список незаконченных полей. goto 2.
5. Мдвиньте первое значение из списка неоконченных полей, сделайте его текущим полем.
6. goto 2.
7. Теперь конец - текущее поле.
8. Выберите смежное поле.
9. Если значение выбранного поля равняется значению текущего поля -1, сделайте его текущим полем. если нет, goto 8.
10. Сохраните позицию текущего поля относительно выбранного (Север, Восток, Юг, Запад и т. д.). Если оно является началом, goto 12 после этого.
11. goto 8.
12. Вернуться к списку указаний (return list of directions)

Не добавляя 'вес типа местности' ('terrain-type weight') (пересечение одного типа требует больше 'шагов') и эвристическую функцию, мы не должны проверять есть ли уже в стеке проталкиваемое поле. Самый быстрый путь к следующему полю всегда будет тот, который первый в стеке. Не нужно каждый шаг сканировать стек, что сохраняет много циклов.

Если бы у нас была эвристическая функция, два стека, и каждый цикл мы проверяли оба стека, мы бы только попусту потеряли циклы, при этом есть большая возможность, что вообще нет пути, который ведёт к цели! Другими словами, я полагаю, что это очень хороший алгоритм, который даже если и проверяет все достижимые поля (если не находит цель сразу), то делает это БЫСТРО.

демонстрация поиска пути:

..........#.........#################################.
....XXXXXXX.........########################........+.
...X......#XXXXXXXXXXXXXXXXXXXO######################.
..X.......#.........#####################.###########.
#X#########.........#####################.############
#X#########.........##########@XXXXXXXXXX.####...../..
#X##......+.........#####################X##########..
#X#############+######.......############.XXXXXXXXXX..
#X######.....+.......#.......############.##########X.
#X############.......#.......#######################X.
#X############......./.......#.......####.....XXXXXX..
+X############.......#.......#.......########X######..
#X############.......#.......#.......####...X.....####
#X####################.......#.......####..X......####
#X####.........###############.......####..X......####
#X####.........#.............#.......####..X......####
#X####.........#.............#.......####..X......#...
+X####.........#.............#.......######X#######...
#X####.........XXXXXXXXXXXXXXXXXX....###..X....####...
#X####........X#.............####X######.X.....####...
..XXXXXXXXXXXX.#.............#....XXXXXXX......####...
######.........#.............###########.......#######

Автор: Pieter Droogendijk.
Источник: неизвестен.
Перевел: Дмитрий О. Бужинский [Bu], 05.08.2005.