Using a stack to traverse and solve a maze - Java

Question

So I am trying to create a maze solver program that would solve a maze of X's and O's. What I would like to do is create a class of Points, so that I can create a 2-Dimensional array of Points which would allow printing to an output page as well as implementing the stack to be relatively simple.

The simplest algorithm of the general idea I'd like to implement in the actual program itself I believe should be:

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'm having trouble coming up with a more in-depth algorithm, as well as getting my Points class situated. I know for Points I should have set X coordinate, and set Y coordinate as well as getters for the two as well. Do you think I need more methods than those two? Like, should I create a method that is passes an x coord, and y coord as parameters so I can just push those together as one, instead of setting x and y individually?

This is what a sample maze would look like, where you start in the bottom right and try to traverse to the top left, with X's as walls, and O's as open spaces in the maze:

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

Retrench

Hi Copernikush, is this homework? – Alkalosis

I'd use a graph instead and use djikstras algorithm to find the path. There are already libraries for this. – Kurtzig

Your maze has multiple openings, then is it OK to end the traversal at any one of them? – Pyrology

@DaveBall lol yea, you got me – Retrench

@Copernikush: Ok - I added the appropriate tag! – Alkalosis

Answer 1

Are you sure your algorithm would solve any maze? I think it would get stuck in this simple mock-up (where S is start and F is finish):

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

Your algorithm would proceed down the first hall until it faced the fall, turn left, be facing the "north" wall, turn left again, and walk back down the first hallway, where it would turn left twice again and keep repeating this problem.

The the right-hand rule algorithm (see the wikipedia page, as well as other sections for more maze algs) should do solve any maze without loops, and should be fairly easy to implement in java.

Partida

Nice link, I did not know of the right-hand rule (+1). But that rule only works if the maze is simply connected.... – Alkalosis

Well I would assume that the only characters in the Maze are O's and X's. – Retrench

Right, I'm only using the S and F to mark the O spaces where you finish and begin. Are you suggesting that in your model, walking down the hall, turning around, and exiting the maze through the entry would be an acceptable outcome? – Partida

Answer 2

You could use a

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

Copyhold

Answer 3

For the algorithm you could use backtracking (EDIT although it doesn't quite match your general idea.) You just have to realize your movements are "pushed" into a virtual stack, and they must be unpushed (and therefore undone.) You might have to implement the stack yourself if the "robot" is an actually moving object, but you can rely on the call stack if you just want to solve the maze.

Fafnir

+1 for the backtracking-link. -1 since Copernikush's abstract algorithm does not require backtracking. make 0 in total ;) – Alkalosis

@DaveBall you're completely right, I have to stop skimming over text, it's a very bad habit :) I edited my answer to fix it. – Fafnir

Answer 4

For the algorithm portion, a depth first recursion through the stack is preferred. Something along the lines 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'll want your point class to return the next point in each given direction (except backward), as well as detect when you'd be at the edges of the maze. You'll probably want a Maze class that contains all of the points, does the printing, stores the X/O, etc. So, you could probably replace the initial currentSpot = (0,0) with currentSpot = Maze.getStartingSpot();

Depressomotor

Also, this psuedocode assumes that all mazes will have a solution. If you want to protect against unsolvable mazes, then you should change the while to be while (! currentSpot.isExit() && stack.size() > 0). Then you could test for an actual solved maze by testing currentSpot.isExit() after the while loop. – Depressomotor

When creating the Points class, how would I do the forward, left, and right transversing and detecting when I am at the edge of the maze/ – Retrench

When you generate the maze, ideally you'd have a Maze class that contains the overall structure and points. At that point, the Point class can simply delegate to the Maze to return the next point. – Depressomotor

Answer 5

For your algorithm, you do not need a stack. Only if you use backtracking to undo traversal decision, you would need a stack.

Alkalosis

Answer 6

Use wall follower algorithm: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Laurelaureano

Answer 7

We tackled 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 while learning about Linked Lists. In a nutshell, the algorithm was like this:

1. Go left. If possible, repeat.
2. If not, go straight. If possible, return to step 1.
3. If not, go right. If possible, return to step 1.

At each step, you also check to see if the spot you are standing on is the finish. If you are unable to continue (ie, not able to go left, straight, or right), you then mark the spot you are standing on as 'visited' and back up. Rinse and repeat.

Thesaurus