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
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With