wood burning stoves*
The moose likes Java in General and the fly likes solving a maze Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "solving a maze" Watch "solving a maze" New topic
Author

solving a maze

Michael Burris
Greenhorn

Joined: Oct 15, 2010
Posts: 4
I have to write code that will solve a maze that has enumerated types and I have to have a class that will read in the maze, a class to solve the maze, and a class to display the solution. My problem is in the class that reads the maze. When I choose the file that it is supposed to read, it doesn't put out the file correctly. Here is what it's supposed to show:
7 4
#######
#...#o#
#*#...#
#######

But when I run my test it only returns this:

#.##

I was wondering if maybe I made a mistake in creating the enumerated type or elsewhere. Any help is appreciated. Here is the code that I have.

Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19654
    
  18

Welcome to the Ranch, Michael!

Can you please UseCodeTags next time? I've added them for you this time, and as you can see it reads a lot easier.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
first thing I'd recommend is to add some extra debug output to see what exactly "myScanner.next()" returns. It may point to an obvious flaw with your logic.

I suspect that you don't want the myScanner.next() to be within the inner loop. My guess is that you are trying to read the maze in line by line then for each line you are reading the individual characters. With the myScanner.next() inside the inner loop this is not what is happening.

I'd also check that you have your WIDTH/HEIGHT and i/j variables the right way round.

Do you just get the output you described? I'd expect an exception to be thrown due to an index out of bounds or similar. You didn't post your main method so just check you aren't swallowing that up somewhere.
Michael Burris
Greenhorn

Joined: Oct 15, 2010
Posts: 4
I changed a few things around and now it is printing out all of the elements in the maze, but they are all on one line. Here is my new code:



EDIT:

I got the code working properly thanks to your suggestions and a few from a friend. Thank you.
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
no problem, glad to help. It reminds me of an assignment I did back when I was at uni. By the way: the reason it prints out the whole maze on one line is because you use System.out.print. If you change it to System.out.println then it will output the text and then terminate the line.

If this is a homework assignment and you haven't learned about Map/HashMap yet then you may want to ignore the following suggestion.
Your current fromChar implementation requires you to have an if condition for each valid char in the maze which is not ideal. A solution I've used many times with enums is to provide a 'lookup' implementation to return the required enum based upon a lookup key. So inside your Square enum class you would need to declare a Map and also initialise the key/value to the character/Square combination:

and then your fromChar method becomes:


So based upon this if you wanted to add a Door square then all you would need to define would be a new value in your enum such as:
Michael Burris
Greenhorn

Joined: Oct 15, 2010
Posts: 4
I haven't learned about Map/HashMap yet, but thanks for the suggestion anyway. I was curious if you could help me with the class that actually solves the maze though. I've gotten part of it written, I'm just having issues with having the solver look at the places around it's current location to see if it is the finish or not. I don't expect you to help me because I know you're not obligated to, but it would be appreciated if you could. Here is the code I have so far for the solver:



The MazeSquare is the same as the enum Square from the previous class, I just changed it because it was causing confusion the other way.
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
to start with most people on this forum are happy to help by giving you hints and pointing you in the right direction which is exactly what you seem to be asking for.

Where people tend to be less helpful is if you ask them to do all of your work for you. For more info see the HowToAskQuestionsFAQ in general and specifically the NotACodeMill and DoYourOwnHomework sections.

From a quick look through your code I think a couple of starting points may be:
(i) You don't add to your agenda other than the MazeSquare.START. So first iteration of the loop agenda is not empty. You pop the agenda and then second iteration, agenda will be empty.
(ii) If my understanding of your algorithm is correct then I think you may need to use the concept of an adjacency list. That is each time you pop a MazeSquare from the agenda and it is not the finish and not in the history then you need to somehow add all of the neighbours of the MazeSquare to the agenda. To do this with the MazeSquare enum is probably not possible. To do this I think you will need to have a Node class that is constructed with a type of square (MazeSquare enum) and knowledge of the neighbours (a List of Nodes).
(iii) not sure what you are using the search variable for but you don't test the value.


When I was looking at a maze solving problem at uni the algorithm we had to use was a bit more basic. It was the right turn (left turn works too) algorithm whereby anytime you come to a right turn you take it. It will solve the maze but is inefficient and won't give you the shortest path.

Anyway, your algorithm looks similar to some other path finding algorithms I've seen in the past. Has the algorithm got any specific name (eg Breadth First Search, Depth First Search, Djikstra, A*, etc)? I actually learned how to use A* from the book "Developing Games in Java" by David Brackeen (my uni library had a copy and I've since purchased my own). Google books have the book in an online form here. Chapter 12 - Pathfinding may be worth a look, even if you're not using the exact A* algorithm then the basic data structures will probably be useful. He even has his own website here where you can download the source code to have a look at. From what I remember of the implementation of A* it is all done with LinkedList and loops so shouldn't be anything beyond what is in your existing code.






Michael Burris
Greenhorn

Joined: Oct 15, 2010
Posts: 4
Thanks for all the great help. Seems that book has what I need to finish the project. Much appreciated for all the insight.
 
Don't get me started about those stupid light bulbs.
 
subject: solving a maze
 
Similar Threads
Maze Solving
July Newsletter Puzzle (Maze Solver)
Abbott's Revenge
help
a very elusive bug