Алгоритм прохождения лабиринта

Question

В настоящее время мы программируем игру (довольно неизвестный язык: modula 2), И проблема, с которой мы столкнулись, заключается в следующем: у нас есть лабиринт (не идеальный лабиринт) в сетке 17 x 12. Компьютер должен создать путь от начальной точки (9, 12) до конечной точки (9, 1). Я нашел некоторые алгоритмы, но они не работают, когда роботу приходится возвращаться:

xxxxx
    x
=>  x
    x
  xxx

или

    xxxxx
        x
xxxxxx  x
     x  x
     x  x
xxxxxx  x
=>      x
xxxxxxxxx

Я нашел решение для первого типа примера, но затем второй тип не мог быть решен, и решение, которое я придумал для второго типа, заставило бы робота застрять в ситуации первого типа.

Это много кода, поэтому я дам идею:

WHILE (конечный пункт назначения не достигнут) DO { попробуйте идти направо, если ничто не блокирует вас: идите направо если вы столкнетесь с блоком, попробуйте подняться до тех пор, пока вы не пойдете направо, если вы больше не можете подниматься, попробуйте спуститься, пока вы не пойдете направо (начиная с места, где вы впервые были заблокированы), если вы не можете больше падать, попробуйте сделать один шаг оставьте и заполните пробелы, которые вы тестировали с блоками. }

Это работает для первого типа проблемы ... не для второго. Теперь я могу ошибаться, поэтому я открыт для более совершенных алгоритмов или решений, в особенности для того, как я мог бы улучшить свой алгоритм.

Большое спасибо !!

Answer 1

Возможно, вам потребуется реализовать алгоритм поиска пути, потому что вы не только хотите найти какой-либо путь, но и хотите найти кратчайший возможный путь.Наиболее популярными алгоритмами поиска пути являются Dijkstra и A *.Если вы знаете расположение всего лабиринта, он даст вам кратчайший путь из одной точки в другую.

Answer 2

Мне кажется, я помню, как ваш алгоритм работал только тогда, когда вы входите в лабиринт через вход, обнимаете стену и пытаетесь выйти. Например, если вы начнете с «острова» в середине лабиринта, он не будет работать.

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

Для вашего первого примера. Вероятно, вы можете распознать шаблон, причем числа - это количество шагов, необходимое для перехода к каждой ячейке, начиная со стрелки.

xxxxx
3212x
2101x
3212x
43xxx

Конечно, вы можете восстановить выбранный путь, если хотите, отслеживая для каждой ячейки лучший предыдущий путь к этой ячейке.

Поиск в ширину работает при условии, что расстояние между каждой ячейкой сетки является постоянным. Если расстояние между соседними ячейками меняется, вы можете взглянуть на этот класс проблем: Проблема кратчайшего пути .

Answer 3

Вы думаете о проблеме как о персонаже, проходящем лабиринт. Я бы не стал этого делать. Я мог бы представить лабиринт в виде серии туннелей, по которым течет вода (это означает, что ответ будет течь во всех направлениях). Таким образом, если бы вы представляли лабиринт в виде 2-х пространственного массива строк, с нулем (или некоторым другим символом в качестве стены), другим разделителем в качестве мест, которые еще не были обнаружены (скажем, «о»), а остальные кратчайший путь к этому квадрату (используя «n», «e», «s» и «w»). Затем, перебирая цикл, каждый раз каждый квадрат будет смотреть, может ли он распространяться на другой квадрат (если в квадрате есть «o»), затем он добавляет каскадную версию строки, в которой этот квадрат должен перейти к следующему квадрату, с символом, представляющим движение, которое потребовалось, чтобы добраться туда. Когда вы найдете конечный квадрат, все готово.

Answer 4

Проблема, которую вы пытаетесь решить, называется pathfinding . Есть много методов, от простой грубой силы до удивительных A *. В Википедии очень хороший обзор здесь .