aspose file tools*
The moose likes Beginning Java and the fly likes Maze solver method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Maze solver method" Watch "Maze solver method" New topic
Author

Maze solver method

Aj Prieto
Ranch Hand

Joined: Sep 28, 2012
Posts: 75

I've been trying to write the same method for a couple of hours now now and I don't seem to be getting any closer to figuring it out. What it has to do is use an enum class, Direction, and use that to find its way out of a maze.

The maze:


The 'S' is the beginning and the 'E' is the end.


Direction enum:


My code


The part I am having trouble with is that it goes into a stackoverflow and I don't know what is causing it. Also I need help when it comes to creating the arraylist containing the directions that it took to exit the maze.

Thanks in advance.


Da mihi sis bubulae frustum assae, solana tuberosa in modo Gallico fricta ac quassum lactatum coagulatum crassum.
Wendy Gibbons
Bartender

Joined: Oct 21, 2008
Posts: 1107

stack overflow means you have got into and endless loop, and it is going round and round in circles till it runs out of memory or stack.
So what would be really helpful is if you provide us with the exception stacktrace, as that will show the lines it is looping around.

So your teacher wrote the enum and you need t use it? did I understand correctly?
Aj Prieto
Ranch Hand

Joined: Sep 28, 2012
Posts: 75

I'm sorry, but what is an exception slacktrace?

Yes, he gave it to us to use.
Wendy Gibbons
Bartender

Joined: Oct 21, 2008
Posts: 1107

when you get an exception it lists the method and line it was at when the error occured, but also the method and line that called that method, so on until it reaches the main method, or the start of the thread.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

The exception stacktrace is what looks like garbage dumped to your screen when the program crashes. It actually contains useful information (usually only the top several lines are needed).

My guess is that the problem is in your "getPathToExit" method, since that is a recursive function. You aren't hitting the base case, so it keeps calling itself over and over and over, and eventually you run out of memory.

I would suggest putting in a few "System.out.println()" statements in that method. print out what row and col are each time you enter, and what you return each time you come out.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Wendy Gibbons wrote:stack overflow means you have got into and endless loop...

@Aj: Just to be clear, it usually means that you've got into an endless recursive loop - ie, a call to a method that either
(a) is itself, or
(b) ends up calling itself in a ring
so I'd concentrate on line 107 if I were you.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Wendy Gibbons
Bartender

Joined: Oct 21, 2008
Posts: 1107

oh winston is much nicer than me, i don't bother reading the code until I have some clues:

anyway here is an example of a stack trace from another discussion.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Aj Prieto wrote:What it has to do is use an enum class, Direction, and use that to find its way out of a maze.

This has nothing to do with your problem, but strangely enough, I've implemented an enum (also called Direction) that does almost exactly what yours does (great minds obviously think alike ).
You might save yourself a lot of those switch statements by simply supplying the x and y "changes" for a single unit move in that direction as constructor values, viz:I'm also not sure that you need HERE, since it's (I assume) a condition, rather than a Direction - ie, some turn, or set of turns, that you've done has ended you up in the same Direction as you started from.

Winston
Aj Prieto
Ranch Hand

Joined: Sep 28, 2012
Posts: 75

The direction enum was given to us by the teacher and we were told to use it.

Implementing this enum thing is really starting to confuse me.

Anyways, I'm going to try and get some rest and try again in the morning.
Aj Prieto
Ranch Hand

Joined: Sep 28, 2012
Posts: 75

I changed my code. Now it won't loop through. I'm thinking it's something wrong with my recursive call. The println statements are to tell me where it enters or doesn't.

New code:


@Winston HERE is used to signify the end of the maze.

Thanks again.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Aj Prieto wrote:I changed my code. I'm still getting stackoverflow.

Ooof. Bad move. Never change code unless:
(a) You KNOW that it's the right thing to do.
(b) It's to test a theory - and if it doesn't pan out: BACK OUT THE CHANGE.
Above all: don't add enhancements to code that doesn't yet work.

@Winston The HERE is to signify that it has reached the exit 'E'.

So I was right; it's a condition, NOT a Direction. It might work, but it's probably not the best solution.

Winston
Aj Prieto
Ranch Hand

Joined: Sep 28, 2012
Posts: 75

@Winston, oops, at least I still have the code on the first post.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

Having it print things like "HAWAII" or "HELLO" isn't really what I mean.

I would have it print things like:

"calling getPathToExit with row = <whatever> and col = <whatever>"
" row or column out of bounds"
" map position equal to a space"
" map position equal to E"
" map position equal to 'S' or a space"
" entering for loop with <whatever> iterations"
" loop iteration <whatever>"

etc. each time above when I put "<whatever>, i would print out the value of the appropriate variable/calculation.

While I was writing that, I noticed something. What is the purpose of the or condition on line 38? if map[row][col] is a space, it will be handled on line 30. So it is un-needed at best, and wrong at worst.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Maze solver method