Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using a stack to traverse and solve a maze - Java

Tags:

java

stack

maze

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
like image 817
Copernikush Avatar asked Feb 08 '12 15:02

Copernikush


People also ask

How do you use a stack to find a path between two points in a maze game?

Initially, we will push a node with indexes i=0, j=0 and dir=0 into the stack. We will move to all the direction of the topmost node one by one in an anti-clockwise manner and each time as we try out a new path we will push that node (block of the maze) in the stack.

Can we use stack for backtracking?

The technique is called backtracking. The key feature is that a stack is used to keep track of each placement of a queen. The program uses a stack to keep track of where each queen is placed.


1 Answers

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.

like image 195
Greg Avatar answered Oct 06 '22 00:10

Greg