maze solve

[Ryan James]

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]

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]

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:

import greenfoot.*;  // (World, Actor, GreenfootImage, and Greenfoot)
 
import java.util.List;
import java.util.ArrayList;
import java.awt.*;
import java.awt.image.*;
import java.awt.geom.*;
import javax.swing.*;
 
public class Tux extends Mouse
{
    private GreenfootImage tuxRight;
    private GreenfootImage tuxLeft;
    
    final int TEST1 = 0;  // location empty
    final int TEST2 = 1;  // visted
   
    int maze[][] = new int[16][16]; // create 64 integers
    
    public Tux()
    {
        super("Tux","Ryan","Orcimsoft");
        tuxRight  = getImage();
        tuxLeft = new GreenfootImage(getImage());
        tuxLeft.mirrorHorizontally();     
        tuxLeft.scale(20,20);
        tuxRight.scale(20,20);
    }
    
    public void act() 
    {
         int x = getX();
         int y = getY(); 
         int num;
        
         World myWorld = getWorld();
         num = Greenfoot.getRandomNumber(4) +1;
            if(num ==1)
            {
                List Brick = myWorld.getObjectsAt(x, y-2, Brick.class);
                if (Brick.isEmpty()) 
                    { y = getY() -4; }
                }
            if(num ==2)
            {
                List Brick = myWorld.getObjectsAt(x, y+2, Brick.class);
                if (Brick.isEmpty())
                    {y = getY() + 4; }
                }
            if(num ==3)
            {
                List Brick = myWorld.getObjectsAt(x-2, y, Brick.class);
                if (Brick.isEmpty())
                    {x = getX() - 4; }
                }
            if(num ==4)
            {
                List Brick = myWorld.getObjectsAt(x+2, y, Brick.class);
                if (Brick.isEmpty())
                    {x = getX() + 4; }
                }
                setLocation(x, y);
                System.out.println ("" + x + " " + y);
            }
               
    class Location // hold x and y co-ords
        {
            private int x;
            private int y;
            public Location( int x, int y )
        {
            this.x = x;
            this.y = y;
        }
            public int getX()
                {
                      return x;
                    }
            public int getY()
                {
                      return y;
                    }
                }
 
}

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]

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]

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]

Hi ryan,

Outer classes can't be private;
Only nested classes can be private.

[Ryan James]

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]

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:

main()
{
   call goFromHere( startingRoom )
}
 
goFromHere( room )
{
   if ( room == destination )
      declare success!
   if ( room has a NORTH door and I haven't been there )
      goFromHere( the next room NORTH )
   if ( room has an EAST door and I haven't been there )
      goFromHere( the next room EAST )
   etc.
   return back to prior room
}

Does that make sense?

[Ryan James]

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]

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]

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]

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]

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]

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]

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.