This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes LEJOS :: Maze Solver Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "LEJOS :: Maze Solver" Watch "LEJOS :: Maze Solver" New topic
Author

LEJOS :: Maze Solver

J Bean
Greenhorn

Joined: Oct 27, 2004
Posts: 2
Hi,

I am new to Java and I've just been given a massive Java assignment in college..We have to build an "intelligent" robot - it's built - and then program it to go around a maze in the quickest time possible

The first time it goes around it'll bump into everything and learn..but the second time around it must go straight through the maze in the shortest time possible without touching any walls

Can anyone help me with this?? Or has anybody got code examples for this?

Thanks for any help given..
Chris Staten
Ranch Hand

Joined: Sep 24, 2004
Posts: 101
It sounds like your instructor is teaching you about recursion. This is a fun topic, but there isn�t a short answer to your question. I wrote a program to solve this kind of problem (but it�s been a few years) and I can remember a good bit of it.

I had a few classes that I can remember (I�m sure there were more):
  • A driver class with my main method (MazeSolverDriver)
  • My actual solver class (MazeSolver), this is where the heavy lifting happens.
  • An exception class for when an invalid maze file was given as an argument (instructors like to blow up your code )
  • A maze position class that I didn�t write myself (instructor provided this)

  • I basically took a flat file in as an arg that represented a maze (instructor provided this file) and walked through the maze recursively calling my MazeSolver object until I found the path through the maze.

    The solver would try to walk north first until it ran into a wall, then it would mark the position as a wall and try to go east. After one step east (if there was not a wall there) the solver would then try to step north again and start the process over again. Basically each time the solver took a step (let�s look at a step to the north) it would then try north first, then east, next west, and then steps back south last. You can understand this by drawing a map on a piece of paper using that algorithm.

    I used a stack object from the java.util package to keep track of my path by pushing my position objects onto the stack once I found the solution path. If I had to back up I would mark the position object for the current position as visited and step back.

    The basics for stepping forward and backward went something like this:
    I had four methods for stepping forward in the maze (stepNorth, stepEast,�) and in each method I would first step one position in the proper direction (e.g. north would take my current position and change the row attribute by -1 and the column by 0). Once I got my new position I would check a few things about my newly acquired position and return false if needed:

    If my new position passed these initial tests I would check to see if it was the solution point of the maze (base case). If so I would push it onto my stack and return true. If it was not the solution I would (still within my current method) try to call the stepNorth method, then east, then west�

    The way that I would walk my next steps in each method would be like this:

    The beauty of this is that I keep calling methods from within those same methods (recursively), so they keep stacking on top of each other and when you find the solution and return true the method below you will return true (pushing the current position onto the stack) until the whole thing collapses and you have your solution path.

    In this situation the current method was being called from the position to it�s south so it didn�t need to stepSouth(). The (north) argument you see is the current grid position (e.g. row 23, column 42). The method needs this argument to know where to step from. In this situation I�m calling the stepNorth method from within the stepNorth method recursively, if that doesn�t work then I stepWest, then stepEast.

    There is a lot more to this solution, but I hope this gives you some ideas as to which way to head in your program.
    [ October 27, 2004: Message edited by: Chris Staten ]
    Dirk Schreckmann
    Sheriff

    Joined: Dec 10, 2001
    Posts: 7023
    Welcome to JavaRanch, J Bean (if that is your real name)!

    Folks around here won't be too likely to do your work for you. If you get started, ask a good question about something you're trying to figure out, I'm sure 'Ranchers will be glad to help nudge you in the right direction.

    What part of your task are you stuck on? Are you brand new to Java programming? Are you an experienced programmer, but the artificial intelligence aspect is new?


    [How To Ask Good Questions] [JavaRanch FAQ Wiki] [JavaRanch Radio]
    Layne Lund
    Ranch Hand

    Joined: Dec 06, 2001
    Posts: 3061
    This sounds like an interesting project. I think you should start by describing your design for the system at a high level. In otherwords, don't worry about the programming language at all quite yet. I'll be more than willing to help when you have specific questions, either about the design, or later when you start implementing it. As stated earlier, most people around here expect you to show that you are doing most of the work.

    Out of curiosity, I have a few questions for you. First, at you programming a physical robot? Or is it a simulation of some sort? If you have an actual robot, what is the interface used to upload the program? Like I said, this sounds like a very intriguing problem. Please come back with some specific questions as you work on this.

    Regards,

    Layne


    Java API Documentation
    The Java Tutorial
    Stan James
    (instanceof Sidekick)
    Ranch Hand

    Joined: Jan 29, 2003
    Posts: 8791
    Just google for "maze solving algorithm" and you'll find plenty. The brute force recursive method works - I wrote one last year for the puzzle forum near the bottom of the forum list - but there is a much more efficient one named for the author ... Knuth? Warning - you'll never be able to pass that off as your own work! Being a real square, I wrote my own BEFORE I used google. Lots more fun that way!


    A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
    Barry Gaunt
    Ranch Hand

    Joined: Aug 03, 2002
    Posts: 7729
    It's for the Lego Mindstorms RCX I think, LEJOS is a cool non garbage collecting implementation of Java in firmware.


    Ask a Meaningful Question and HowToAskQuestionsOnJavaRanch
    Getting someone to think and try something out is much more useful than just telling them the answer.
    J Bean
    Greenhorn

    Joined: Oct 27, 2004
    Posts: 2
    It is for the Lego Mindstorns RCX yes

    Basically I have a Light Sensor - this will be used to find the end and start of the maze using two different coloured markings on the ground..

    I have a touch sensor at the front to detect the walls..

    And two motors to drive the robot through the maze..

    I'm not familiar with Java to be honest and this seems to be beyond my capabilities - this is why I came here looking for help..Just wondered if anybody had done anything like this before and could give me some pointers! Thanks for your help so far..
    Barry Gaunt
    Ranch Hand

    Joined: Aug 03, 2002
    Posts: 7729
    If I had to learn about this I would start here.
    Chengwei Lee
    Ranch Hand

    Joined: Apr 02, 2004
    Posts: 884
    Hi,

    What sort of maze do you have? A normal squarish maze of a known/unknown size. What defines solving the maze, is it moving from 1 corner to another or is it moving from 1 corner to the centre of the maze?

    Software simulation & actual hardware implementations may have some gaps to bridge. For example, does the JVM that you use on the Lego supports Java collections?

    As said by many others, you really shouldn't worry about being new to Java & not able to code it. The most important part is the strategy that you're going to use to solve the maze, and that is PL-independent.

    Lets say I've a 16x16 maze & solving it means getting from 1 corner to the diagonally opposite corner. What's the first thing that will come to your mind? You need a map don't you? Cos you have to know your way around the maze & if you don't a map, you can't remember whether have you been to that location before. So as you move along, you draw your map & mark the places where you'd been, until you finally reach the goal.

    Next, using those standard graph traversing algorithm, you could convert your map into a suitable input format for the algorithm & use it to find the shortest path.

    Next, you just need to use this calculated shortest path.

    This is just 1 way of doing it. I'm sure there're plenty around.

    So, don't worry about not being able to code very well in Java. Your solution in solving the maze is more important. Once you have it listed in steps, then you complete your steps 1 by 1 & you've your solutions for submission!

    HTH.

    Cheers!


    SCJP 1.4 * SCWCD 1.4 * SCBCD 1.3 * SCJA 1.0 * TOGAF 8
     
     
    subject: LEJOS :: Maze Solver
     
    Similar Threads
    Why use Tomcat or Jetty instead of a multithreaded Endpoint publisher?
    Recursive Maze
    maze program help
    maze solve
    help