Алгоритм поиска Ли
Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.
Алгоритм состоит из 3 шагов:
- Инициализация
- Распространение волны
- Восстановление пути
Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.
Псевдокод
Взято из Википедии.
Инициализация
Пометить стартовую ячейку
d := 0
Распространение волны
ЦИКЛ
ДЛЯ каждой ячейки loc, помеченной числом d
пометить все соседние свободные непомеченные ячейки числом d + 1
КЦ
d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)
Восстановление пути
ЕСЛИ финишная ячейка помечена
ТО
перейти в финишную ячейку
ЦИКЛ
выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
перейти в выбранную ячейку и добавить её к пути
ПОКА текущая ячейка — не стартовая
ВОЗВРАТ путь найден
ИНАЧЕ
ВОЗВРАТ путь не найден
Пример кода, который реализует алгоритм и выводит на экран путь (C#).