• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

maze solve

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ryan James
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 558
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ?
 
Ryan James
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 558
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi ryan,

Outer classes can't be private;
Only nested classes can be private.
 
Ryan James
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 1923
Scala Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ryan James
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 558
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic