Использование стека для обхода и решения лабиринта — Java

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

Я считаю, что простейший алгоритм общей идеи, который я хотел бы реализовать в самой программе, должен быть:

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

Но у меня возникли проблемы с созданием более глубокого алгоритма, а также с размещением моего класса Points. Я знаю, что для точек я должен был установить координату X и координату Y, а также установить геттеры для двух. Как вы думаете, мне нужно больше методов, чем эти два? Например, должен ли я создать метод, который передает координаты x и координаты y в качестве параметров, чтобы я мог просто объединить их вместе, вместо того, чтобы устанавливать x и y по отдельности?

Вот как будет выглядеть образец лабиринта, где вы начинаете в правом нижнем углу и пытаетесь пройти в верхний левый, где X обозначает стены, а O обозначает открытые пространства в лабиринте:

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O 
X X O X X X O

person Copernikush    schedule 08.02.2012    source источник
comment
Привет, Коперникуш, это домашнее задание?   -  person DaveFar    schedule 08.02.2012
comment
Вместо этого я бы использовал график и использовал алгоритм джикстры, чтобы найти путь. Для этого уже есть библиотеки.   -  person willcodejavaforfood    schedule 08.02.2012
comment
В вашем лабиринте есть несколько входов, тогда можно ли закончить обход в любом из них?   -  person Sufian Latif    schedule 08.02.2012
comment
@DaveBall, лол, да, ты меня понял   -  person Copernikush    schedule 09.02.2012
comment
@Copernikush: Хорошо, я добавил соответствующий тег!   -  person DaveFar    schedule 09.02.2012


Ответы (7)


Вы уверены, что ваш алгоритм решит любой лабиринт? Я думаю, что он застрянет в этом простом макете (где S — начало, а F — конец):

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

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

Алгоритм правила правой руки (см. страницу Википедии, а также другие разделы для больше алгоритмов лабиринта) должны решить любой лабиринт без циклов, и его довольно легко реализовать в java.

person Greg    schedule 08.02.2012
comment
Хорошая ссылка, я не знал о правиле правой руки (+1). Но это правило работает, только если лабиринт просто связан.... - person DaveFar; 08.02.2012
comment
Ну, я бы предположил, что единственные символы в лабиринте - это О и Х. - person Copernikush; 08.02.2012
comment
Правильно, я использую только S и F, чтобы отметить пробелы O, где вы заканчиваете и начинаете. Вы предполагаете, что в вашей модели ходьба по коридору, разворот и выход из лабиринта через вход были бы приемлемым результатом? - person Greg; 08.02.2012

Вы можете использовать

Stack<Point> points = new Stack<>();

// add a point
Point p = new Point(x, y);
if (points.contains(p))
   // been here before, in circles.
else
   points.add(p);
person Peter Lawrey    schedule 08.02.2012

Для части алгоритма предпочтительна рекурсия в глубину стека. Что-то вроде:

currentSpot = (0,0)  // The starting point //

while(! currentSpot.isExit()) {

  if (! currentSpot.left().isWall()) stack.push(currentSpot.left());
  if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward());
  if (! currentSpot.right().isWall()) stack.push(currentSpot.right());

  currentSpot = stack.pop();  // Get the next location //
}

Вы хотите, чтобы ваш класс точек возвращал следующую точку в каждом заданном направлении (кроме обратного), а также определял, когда вы окажетесь на краях лабиринта. Вам, вероятно, понадобится класс Maze, который содержит все точки, выполняет печать, хранит X/O и т. д. Таким образом, вы, вероятно, могли бы заменить начальный currentSpot = (0,0) на currentSpot = Maze.getStartingSpot() ;

person Steven Mastandrea    schedule 08.02.2012
comment
Кроме того, этот псевдокод предполагает, что все лабиринты будут иметь решение. Если вы хотите защититься от неразрешимых лабиринтов, то вы должны изменить while на while (!currentSpot.isExit() && stack.size() › 0). Затем вы можете проверить фактический решенный лабиринт, проверив currentSpot.isExit() после цикла while. - person Steven Mastandrea; 08.02.2012
comment
При создании класса Points, как бы я делал движение вперед, влево и вправо и определял, когда я нахожусь на краю лабиринта/ - person Copernikush; 08.02.2012
comment
Когда вы создаете лабиринт, в идеале у вас должен быть класс Maze, содержащий общую структуру и точки. В этот момент класс Point может просто делегировать Maze для возврата следующей точки. - person Steven Mastandrea; 12.02.2012

Для вашего алгоритма вам не нужен стек. Только если вы используете возврат для отмены решения обхода, вам понадобится стек.

person DaveFar    schedule 08.02.2012

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

person kaoD    schedule 08.02.2012
comment
+1 за обратную ссылку. -1, так как абстрактный алгоритм Коперникуша не требует возврата. сделать 0 в сумме ;) - person DaveFar; 08.02.2012
comment
@DaveBall, ты совершенно прав, мне нужно перестать пролистывать текст, это очень плохая привычка :) Я отредактировал свой ответ, чтобы исправить это. - person kaoD; 08.02.2012

Используйте алгоритм следования за стеной: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

person Suzan Cioc    schedule 08.02.2012

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

  1. Идите налево. Если можно, повторите.
  2. Если нет, идите прямо. Если возможно, вернитесь к шагу 1.
  3. Если нет, идите направо. Если возможно, вернитесь к шагу 1.

На каждом этапе вы также проверяете, является ли место, на котором вы стоите, финишем. Если вы не можете продолжать (т.е. не можете идти влево, прямо или вправо), вы отмечаете место, на котором стоите, как «посещенное» и возвращаетесь назад. Промыть и повторить.

person ggrigery    schedule 08.02.2012