Using a stack to move and solve a maze - Java

Question

So, I'm trying to create a program for solving labyrinths that will solve the labyrinth of X and O. What I would like to do is create a point class so that I can create a 2-dimensional array of points that would allow printing on the output page, as well implement a stack to be relatively simple.

The simplest algorithm of the general idea that I would like to implement in the most real program, I consider:

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 

But I had problems with developing a more in-depth algorithm, as well as to determine the class of my glasses. I know that for the glasses I had to set the X coordinate, and also set the Y coordinate, as well as the getters for the two. Do you think I need more methods than these two? For example, should I create a method that passes the x coordinate and y coordinate as parameters, so I can just combine them together, instead of setting x and y separately?

It will look like the labyrinth of the sample, where you start in the lower right corner and try to pass in the upper left corner, and X as walls and O as open spaces in the labyrinth:

 OOOOOXO XXOXOOX OXOOXXX XXXOOXO XXXXOOX OOOOOOOXXOXXXO 

Answer 1

Are you sure that your algorithm will solve any maze? I think he is stuck in this simple layout (where S starts and F ends):

 xxxxxxxxxx Sooooooxxx xxxxxxoxxx xxxxxxFxxx 

Your algorithm will go through the first hall until it encounters a fall, turn left, do not collide with the "northern" wall, do not turn left and do not go down the first corridor, where it will turn left again and continue to repeat this problem.

The correct editing algorithm (see the wikipedia page, as well as other sections for more labyrinths) should be solved by any labyrinth without loops, and it should be pretty easy to implement in java.

Answer 2

you can use

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

Answer 3

For the algorithm, you can use backtracking ( EDIT , although this does not quite match your general idea.) You just need to understand that your movements are “popped” onto the virtual stack and they need to be untangled (and therefore undone). You may need to implement the stack yourself if the "robot" is actually a moving object, but you can rely on the call stack if you just want to solve the maze.

Answer 4

For part of the algorithm, the depth of the first recursion through the stack is preferred. Sort of:

 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 // } 

You want your point class to return the next point in every given direction (except for the opposite), and also detect when you are on the edge of the maze. You probably need a Maze class that contains all the dots, prints, saves X / O, etc. So you can probably replace the original currentSpot = (0,0) with currentSpot = Maze.getStartingSpot ();

Answer 5

For your algorithm you do not need a stack. Only if you use backtracking to override the crawl decision will you need a stack.

Answer 6

Use Wall Sequential Algorithm: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Answer 7

We solved this problem once when I was in school, and we used a solution similar to the right / left hand rule. I believe we did this by learning about linked lists. In a nutshell, the algorithm was something like this:

• Go left. Repeat if possible.
• If not, go straight. If possible, return to step 1.
• If not, go right. If possible, return to step 1.

At each step you also check if the place you are standing in is the finish. If you cannot continue (that is, you cannot go left, straight or right), then you mark the place you are standing in as “visited” and backed up. Rinse and repeat.