aspose file tools*
The moose likes Java in General and the fly likes maze solve Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "maze solve" Watch "maze solve" New topic
Author

maze solve

Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
I'm wanting some help with regards to what is possible in java.

I'm writing a mouse than can solve a 2D maze, 16*16 cells. I'm wanting to make sure the mouse can explore the maze and then solve it based on all the routes its found. I figured I could use the faster flood algorithm once I have solved the maze since that would be allowed given I have aquired all the data. I was wondering if any one knew how I could get my mouse to explore the maze fully, recognise that fact and if it say could explore as far as it could make it follow a path back to the start of it finished search? I guess I'd have to use arrays and maybe stacks to implement this.

Any code snippets/ideas would help so I could visualise the actual code and how to start writing it.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Hi, welcome to the ranch!

There are some sophisticated algorithms for this, but simple brute force is a good place to start. You mentioned stacks which is a good intuition.

We try to give leading hints here, not complete answers. It's more fun when you do the discovery work, and it sticks to your brain better. First leading hint ... to give us all a starting point, are you comfortable with recursion?
[ April 18, 2007: Message edited by: Stan James ]

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
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
Recursion as in backtracking? I understand the theory, however implementing it where I come undone. I asssume I need to store in a 2d array all the co-ordinates and then assign them values related to say how many walls there are and the type of exits and how many times i've visted?

This is the maze:


And this is my code so far:



This is using the greenfoot environment, all the calls to Mouse etc are super's and they (mouse class) can't be changed. So far I've made it detect walls and walk the maze in a random fashion, which eventually solves teh maze, however extremely ineffeciently. I would like it to say make intelligent steps by going "have I been to teh cell on the right? yes . okay lets not visit again"

Also on the internet there are alot of algorithsm to solve a maze quickly however I need to do it 'manually' so to speak, my mouse needs to explore the maze and then find the best path based on that information.
[ April 18, 2007: Message edited by: ryan jamse ]
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi ryne,

I like that puzzle. So sweet.
I would like it to say make intelligent steps by going "have I been to teh cell on the right? yes . okay lets not visit again"


I got an idea; You can build an automatic Robo program which will go in directions : left,top,right,bottom(should maintain that order).

How you can program:
1. You need to have functions which will tell the Robo
1.1.isLeftAvail()
1.2.isTopAvail()
1.3.isRightAvail()
1.4.isBottomAvail()
2. Among the Four sides, three sides bloked means you can Block the place by constructing a wall(so as not to come again) when you move from that place to vacant place.

3. Always let the ROBO movein the order specified below
isLeftAvail() --> go if not
isTopAvail() -- > go if not
ifRightAvail() --> go if not
ifBootomAvail()--> go.

4. repeat 2-3 steps until you find all 4 sides bloked.

Did you got me ? I don't know its feasible in you code ?
But got my idea ?


Thanks & Regards, T.Srinivasan
SCWCD 1.4(89%), SCJP 5.0(75%)
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
I've added:

private class mapCell()
{
public visited boolean = false;
public northWall boolean = false;
public eastWall boolean = false;
public southWall boolean = false;
public westWall boolean = false;
}

however having errors making it compile it's saying an '{' is expected on the first line.
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi ryan,

Outer classes can't be private;
Only nested classes can be private.
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
edit. figured it out.


public class mapCell
{
public boolean visited = false;
public boolean northWall = false;
public boolean eastWall = false;
public boolean southWall = false;
public boolean westWall = false;
}

works, had some of the words wrong way round.

Now I need to get it to systematically check all these walls.
[ April 18, 2007: Message edited by: ryan jamse ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Cool discussion, hope you're having fun doing this!

Think about how you'd tell a 5th grader to walk a maze of rooms. You're standing in a room. If there's a door to your left and you haven't already been there, go left. Now you're standing in a room. If there's a door to your left and you haven't already been there, go left. There's the recursion.

If you can't go left, try another direction. If you have tried all directions, back up one room and try another direction. "backing up" is coming out of the recursive call. Oh, and if you get out of the rooms, you're done.

Walking the maze you might take some chalk, put an X in the middle of any room you visit and draw an arrow every time you go through a door. The Xs tell you where you've been and the arrows tell you how to get back. Recursion handles the "how to get back" part, but you still need to mark each room somehow.

The recursive bit looks a kind of like:

Does that make sense?
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
Yeah, that makes sense. That was the idea I have been thinking about, hopefully when I return to university next week I'll have sorted out the exploring bit and can start finding out how about how to get the mouse to follow paths.

I'd imagine there will be quite alot of if and else statements for this idea?
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
I would also like to ask a question and some major direction on this bit/links to help.

How do I use my class:
public class MapCell
{
public boolean visited = false;
public boolean northWall = false;
public boolean eastWall = false;
public boolean southWall = false;
public boolean westWall = false;
}
Take info from the cell I'm in such as the co-ords, etc and then put it into an array. I could figure out how to say get the wall info and co-ords but how do I actually place that information into an array?
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

That reminds me of a nice (german) book for programming-beginners:
www.amazon.de Programmieren-spielend-gelernt-Mit-Java-Hamster-Modell

There are very few methods available
- leftturn ()
- forward ()
- bolean freeAhead ()
- boolean targetReached ()

and you have to solve some tasks.
One of the last ones is solving a maze.

You may solve it, if you walk every possible way, and you use every possible way if you try every possibility on each step.
You don't need to memorize cells you visited, because the recursion does.

And it reminds me of Sedgewicks Algorithms, because you may see the maze as a graph, and now you're traversing the graph (which is, effectively, the same problem).
[ April 18, 2007: Message edited by: Stefan Wagner ]

http://home.arcor.de/hirnstrom/bewerbung
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
Yeah, I had a look at that Hamster one before as it was made on the environment I'm having to use (greenfoot) however alot of it is in german heh.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
BTW, Ryan, we have a secret cache of rancher solutions from a few years ago. As a teaser, we'll show you ours after you show us yours. Mine is in there; it's a giant gnarly club of a solution compared to the cool ones.
Ryan James
Greenhorn

Joined: Apr 18, 2007
Posts: 15
The code of mine so far is at my blog on: http://itendsnow.co.uk/blog/

Of course this only explores the maze randomly yet, I'm currently writing the code to check intelligently.
[ April 19, 2007: Message edited by: ryan jamse ]
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi ryan and james,

I love the way you think.

I will start coding the Maze and get back to you.

I have stopped playing with "programs" a long back that made me rusty.

I ll seek your help when required.

Have a nice day.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: maze solve
 
Similar Threads
Maze Solving
Comparing chars at positions in an array
Recursive Maze
Problem in a Maze.
help