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

Question

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

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

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

Но у меня возникают проблемы при разработке более глубокого алгоритма, а также при размещении класса очков. Я знаю, что для Точек я должен был установить координату 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

Answer 1

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

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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 () ;

Answer 6

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

Answer 7

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

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);