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

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

xxxxx
    x
=>  x
    x
  xxx

or:

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

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

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

ПОКА (конечный пункт не достигнут) СДЕЛАЙТЕ {старайтесь идти направо, если вас ничего не мешает: идите направо, если вы встретите блок, пробуйте вверх, пока не сможете идти направо, если вы больше не можете подниматься, попробуйте спуститься вниз, пока не сможете пойти направо, (начиная с того места, где вы были заблокированы в первый раз), если вы больше не можете спуститься вниз, попробуйте сделать один шаг влево и заполните пробелы, которые вы тестировали, блоками. }

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

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


algorithm maze
person Sam    schedule 19.03.2010    source источник

Ответы (4)


arrow_upward
2
arrow_downward

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

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

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

xxxxx
3212x
2101x
3212x
43xxx

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

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

person Larry    schedule 19.03.2010

arrow_upward
2
arrow_downward

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

person Daff    schedule 19.03.2010

arrow_upward
1
arrow_downward

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

person Leif Andersen    schedule 19.03.2010

arrow_upward
0
arrow_downward

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

person Martin Wickman    schedule 19.03.2010