Какие алгоритмы используются для перемещения по бесконечным полям с препятствиями?

Для перемещения по полям с препятствиями используют, например, алгоритм Ли для поиска кратчайшего пути от старта до финиша. eternalengy.livejournal.com

Суть алгоритма: eternalengy.livejournal.com

1. Программа распознаёт поле в виде двумерного массива. eternalengy.livejournal.com Пустое место обозначается значением «−2», а точки с препятствиями — значением «−1». eternalengy.livejournal.com
2. Выбирается стартовая точка и ей задаётся значение «0». eternalengy.livejournal.com Значение точки финиша при этом не меняется. eternalengy.livejournal.com
3. Поле сканируется из точки старта «волной». eternalengy.livejournal.com Значение каждой соседней ячейки увеличивается на 1 (0 → 1 → 2 → 3 и так далее). eternalengy.livejournal.com
4. Как только значение ячейки финиша меняется, поиск останавливается, путь уже найден. eternalengy.livejournal.com

Также для перемещения по полям с препятствиями используют команды проверки условий, которые проверяют, свободен ли путь в каждом из четырёх возможных направлений. inf-oge.sdamgia.ru Эти команды используют вместе с условием «если» и последовательностью команд. inf-oge.sdamgia.ru schol-info.ucoz.ru