Maze in Java

Thread Starter

jakegwood

Joined Apr 13, 2011
29
So I have an assignment where a user creates a maze and the computer solves it. The user first enters the size of the maze, then the maze itself ie,

rows:5
columns: 5

OXOOO
OXOXO
OOOXO
OOXXO
XXXXO

Whereas any space with an O can be navigated through, and X cannot. We have to get from the start, top left, to the finish, bottom right. First we have to output whether or not it's solvable, and then if it is solvable, how to solve it. (Start from finish and then have a list of instructions D- down, U- Up, L- Left, R- Right, you may not move diagonally.) So the solution to this puzzle would be DDRRUURRDDDD

Entering the matrix is of course easy, but as far as solving, there are a couple problems, but here's my logic:
1. create a boolean matrix of same dimensions as the maze. (true will mean that space could be part of the solution, false means no.)
2. set 0x0 and nxn = true
3. using for loops, scan through row by row, starting from the finish point. any position that has 2 o's next to it, as well as a true next to it gets a true. (this is the condition for a useful spot.)
4. In devious paths like my example step 3 won't catch every space the first time around so keep doing this until the boolean matrix before the sweep looks the same as the one after.... ie, the sweep isn't finding any more spaces.
5. After finding all potential spots, sweep through row by row again. any true spot that doesn't have 2 trues next to it (other than start and finish) are not part of the solution.
6. starting from top left find adjacent true spots and according to where they are relative to that step ad the corresponding letter to the solution array.
7. print the solution array.

Really, the only problem I have is when there are a 2x2 square of o's, as there are in my example, there is ambiguity, and if the checks for where the next true is when finding the solution are in a certain order, you'll get stuck in there.

Thanks.
 

Georacer

Joined Nov 25, 2009
5,182
Instead of going row to row, you could start from the first 'O' and progress towards the adjacent 'O's. When you reach a spot where two or more 'O's are adjacent leave a placemark.

Choose your next tile randomly. If at some point you reach a tile that is adjacent to the marked tile, disregard the previous tile and continue from the current tile.

This might solve a path like this one:
Rich (BB code):
XXXX
X--X
-||-
XXXX
but it won't shorten paths like this:
Rich (BB code):
XXXXX
X---X
-| |-
XXXXX
Is that clear?
 

Filox

Joined Oct 11, 2011
7
Hello jakegwood,

The best way to solve mazes is to use a graph searching algorithm, like breadth-first search, depth-first search
( \(O(|V|+|E|)\) complexity) or an even faster A*. If you want more information on how to use them on your problem , please ask.
 

djsfantasi

Joined Apr 11, 2010
9,156
This is strange, because I have been working on this problem in my head recently. I had this assignment in school some 35 years ago and had an unorthodox approach that was accepted. So YMMV

  1. At each cell, look for alternative paths. If only one, leave a numbered bread crumb. Your method of looking for alternative paths can determine if you use breadth versus depth searching. If none, see step 4.
  2. if there is an alternative path, push the current coordinates onto a stack and increment the numbered bread crumb. On the solution stack, push the direction of the alternative you are traversing
  3. Continue on the identified alternative path.
  4. if a dead end is encountered, return to the coordinates on the top of the stack. Delete the direction from the solution. Return to step 1
  5. Once at the exit, your solution will be in the solution stack.
This algorithm jumps back to decision points within the maze saving scan time, does not necessarily produce best solutions, but will always produce a solution. It is very fast.
 

panic mode

Joined Oct 10, 2011
2,715
you can also use "one hand touches wall". if the maze is solvable, this WILL get you through. also you can check if you are at exit since you know current coordinate.

idea is to start from whatever point, use one hand (left for example) and feel the wall as you are walking toward exit.
so, create variable direction and use different values for north, west east, south.
if at any moment there is no wall to your left, turn 90deg (and update direction).
if there is wall on the left and no obstacle in front, move one step forward.
if there is wall on the left and obstacle ahead, turn right.

you will need nested IFs or CASE statement to choose direction. for example if you re heading west and you hit the obstacle, "turn left" would mean turning south.
 

panic mode

Joined Oct 10, 2011
2,715
forgot to mention, here you do not need to keep track of visited positions or getting back to branched connection - you just keep advancing toward exit. if you get back to start position, there is no solution.
 

panic mode

Joined Oct 10, 2011
2,715
rows:5
columns: 5

OXOOO
OXOXO
OOOXO
OOXXO
XXXXO

so solution in this case would be
DDDRURUURRDDDD

note it is not always most efficient but it is simple and it works
 

Thread Starter

jakegwood

Joined Apr 13, 2011
29
That seems to make sense. I am trying to figure out efficient solutions too though. After going through with my method, the only true spaces are the actual path and 2x2 boxes connected to the path. I did add one step though in development, that each time you move, you make false the position you're in, then move. That means that walking through the puzzle, any true squares must either be one that gets you closer to the solution or, part of a square. But I think that would mean that if you are in a superfluous square (which I cannot think of a square that is not) that means that any true points diagonal to you must be part of the superfluous square. Therefore, you could make false all points diagonal to you. Then, run modified step 5 (modified step 5 makes sure there is at least 1 true space next to another true space) and clear out the other parts of the extraneous solution. So:

OXOOO
OXOXO
OOOXO
OOXXO
XXXXO
XXXXO

So all of these O's are part of the path, and they will all work, but there is ambiguity.

So when I am at P, the ambiguity is discovered, and a check will find that there are two adjacent possibilities, so let's delete any diagonal possibilities (Keep in mind I am destroying the path behind me as well as the space I am at, otherwise there would always be two possibilities):

XXOOO P=Position
XXOXO
POOXO
OXXXO
XXXXO
XXXXO

Now, run modified step 5, which will get rid of the spot below, but not the one to the right, as it has the spot adjacent to it also true:

XXOOO P=Position
XXOXO
POOXO
XXXXO
XXXXO
XXXXO

Then you are left with one solution. It would have to be more elegant however if you had an extended superfluous square (i.e. superfluous rectangle)

Anyway, I know mine is a bit clunky, but it does work so far, though I do feel like I am blind to a few possibilities that might be disastrous (and I haven't solved it for the superfluous rectangle). I like all of yours better, in terms of streamlined logic, but I am also trying to figure the shortest path, and I don't know if there's anyway to do that unless you've already entered the maze.

Filox, I am really not sure what you mean by that, but I would love to learn more, is there a place I can do that?
 
Can your maze have loops? If yes, a "follow the wall" algorithm will not work.

I would suggest checking out the A* algorithm:
http://en.wikipedia.org/wiki/A*_search_algorithm

For a high-school program, the local students had to build robots that solved mazes. They were allowed two runs and the best time was used as their score. Most students mapped the entire maze on their first run, then use the a* algorithm to determine the fastest path for the next run.

Sorta unrelated, but fun to watch.. look how fast this maze solving robot goes!:
http://www.youtube.com/watch?v=4pVgEoH-sjw
 

Thread Starter

jakegwood

Joined Apr 13, 2011
29
So assuming the maze is NxN, I don't really understand how A* would work if the solution were more than N+N steps.

And also how would you define a solution? Would it be an array of dirrections and then when you find a set of new directions you compare it to that one just to make sure it isn't the same one?
 

Georacer

Joined Nov 25, 2009
5,182
Can your maze have loops? If yes, a "follow the wall" algorithm will not work.

I would suggest checking out the A* algorithm:
http://en.wikipedia.org/wiki/A*_search_algorithm

For a high-school program, the local students had to build robots that solved mazes. They were allowed two runs and the best time was used as their score. Most students mapped the entire maze on their first run, then use the a* algorithm to determine the fastest path for the next run.

Sorta unrelated, but fun to watch.. look how fast this maze solving robot goes!:
http://www.youtube.com/watch?v=4pVgEoH-sjw
A flat maze cannot have loops and the "hug the wall" technique will always work.

In order for it to be unusable, the maze has to have bridges and overpasses.
 
When I say loops, this is more the situation I was thinking of S= start position, E= end position:

S0000
0XXX0
00EX0
0XXX0
000000

If you used a PURE left/right wall following algorithm, you could potentially forever walk around the perimeter of the maze.

Although their requirements state the start and end will always be on the perimeter and off the top of my head I can't think of a time when a pure right/left approach would fail.
 

Georacer

Joined Nov 25, 2009
5,182
That's why I said that, given the OP's specifications, the "hug a wall" technique is always viable.

It is mathematically proven that for entrance and exit on the perimeter, on a flat maze, this technique will yield results.
 
Top