• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

solving a maze

 
Michael Burris
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20661
65
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Paul Beckett
Ranch Hand
Posts: 96
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 96
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 96
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for all the great help. Seems that book has what I need to finish the project. Much appreciated for all the insight.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic