Solving a maze from the inside

[llemes4011]

Hi, I'm working on an algorithm that solves a maze from the inside, and seeks out 1 of the 4 exits on the sides, and after getting 1, it goes to the next until it has them all. The maze is always 22x22, and you only have 400 steps. I asked my teacher about using a recursive method to solve it, and he said that is probably the best way to go. But, the catch is that you don't know where the walls are, and they change every time. The rat (I'm trying to get a rat to all four exits) starts in the 4x4 box in the middle that has between 1 and 5 exits (it's different every time a maze is generated). The rat can see how far away a wall is, and you are allowed to store the positions in an array if you wish. He can also build walls and get his current x and y position.

(movement options are north, south, east, and west)

Here's an example of what a maze looks like:
http://farm4.static.flickr.com/3528/3201086335_4556d4aed7_o.jpg

I think that's everything, any help would be greatly appreciated =]

[masijade]

Okay, so what do you have, so far?

[BestJewSinceJC]

I did a project like this, except with more strict guidelines. What you do is use either a stack or a queue. Push the start space onto the stack/queue. Then, push any adjacent cells (that you can move to!) from the cell you're currently at (at first, this will be the start space). Then, pop a cell from the stack/queue and repeat. You will eventually find the finish. If that didn't make sense, you're basically 'looking' at whatever cell you're currently at, pushing all adjacent cells that you can move to on the stack, popping the next cell from the stack, and repeating until you find the finish.

Good luck...

[llemes4011]

Okay, so what do you have, so far?

hi, sorry for the long response time.

What I'm trying right now, is to take the current x,y position, and build a path from that, based on where the known walls are and where the rat thinks the the exit is located. The best path is regenerated every turn to compensate for new obstacles. The algorithm is recursive, and i think that's where some of the problem is located...

Sorry to code is so long, but all of the variables are pretty strait-forward

public class RecurseRat extends RatBot
{
    int[][] possibleExitLocations = new int[22][22];
    boolean[][][] wallLocations = new boolean[22][22][4];
    
    
    public RecurseRat() { super("RecurseRat", "Semmel"); }
    
    // called at the start of the maze i.e., when the maze starts
    public void initRat()  
    {
        for(int i=0;i<22;i++) for(int j=0;j<22;j++) possibleExitLocations[i][j]=0;
        for(int i=0;i<22;i++) for(int j=0;j<22;j++) for(int k=0;k<4;k++) wallLocations[i][j][k]=false;
    }
    
    // determin what the rat will do this turn (move n,s,e,w, or 
    // build a wall n,s,e,w, or acquire nearby cheese)
    public int chooseAction() 
    {
        storeWallLocations();
        
        resetCounters();  // reset variables for recursePath before generating new path
        recursePath();
        
        // return the first value of the best path
        return bestPath[0];
    }
    
    // uses the closestExitRange to triangulate exit location
    public void findExitLocation() 
    {
        // increase values for the possible exits
        int counter=0;
        for(int i=closestExitRange;i>0;i--)
        {
            if(x+i<=21 && y+counter<=21) possibleExitLocations[x+i][y+counter]+=1;                    
            if(x+i<=21 && y-counter>=0)  possibleExitLocations[x+i][y-counter]+=1;        
            if(x-i>=0 && y+counter<=21)  possibleExitLocations[x-i][y+counter]+=1;            
            if(x-i>=0 && y-counter>=0)   possibleExitLocations[x-i][y-counter]+=1;
            
            counter++;
        }
        
        // find the highest valued "exit" point
        int bestChoiceX=0;
        int bestChoiceY=0;
        for(int i=0;i<22;i++) {
            for(int j=0;j<22;j++) {
                if(possibleExitLocations[bestChoiceX][bestChoiceY]<possibleExitLocations[i][j])
                {
                    bestChoiceX = i;
                    bestChoiceY = j;
                }
            }
        }
    }
    
    int spacesMoved, neededExtraMoves, moveCount;
    int xCounter, yCounter;
    int[] bestPath;
    
    // recursivly find the best path-of-travel
    public int[] recursePath() 
    {
        // x- and y- counters are to signify how many units in each direction 
        // from the current real x, y that the algorithm is at
        int curX = x+xCounter; 
        int curY = y+yCounter;
        
        // the maximum number of moves = the closestExitRange, plus however 
        // many fewer/extra moves are needed so it lands EXACTLY on the exit, 
        // minus the number of places generated so far.
        moveCount = closestExitRange + neededExtraMoves - spacesMoved;
        
        // give the bestPath a length if it is the first time running algorithm
        if(spacesMoved==0) bestPath = new int[moveCount];
        
        while(spacesMoved<moveCount)
        {
            // if the algorithm will not land in an exit in EXACTlLY 
            // x number of moves, edit x acordingly, and reset algorithm.
            
            // if there are not enough moves to make it to the exit, crear variables, 
            // add 1 to extra moves, check again.
            if( spacesMoved==moveCount-1 && ((x>1 && x<20) || (y>1 && y<20)) )
            {
                neededExtraMoves++;
                xCounter=0;
                yCounter=0;
                spacesMoved=0;
                bestPath = new int[moveCount];
                recursePath();
            }
            
            // if there are not too many moves, crear variables, 
            // subtract 1 from extra moves, check again.
            else if( spacesMoved<moveCount && (x==0 || x==21 || y==0 || y==21) )
            {
                neededExtraMoves--;
                xCounter=0;
                yCounter=0;
                spacesMoved=0;
                bestPath = new int[moveCount];
                recursePath();
            }
            
            // look in all directions, and find the highest value, and 
            // move in that direction
            int moveDir = findFurthestWay(lookNorth, lookEast, lookSouth, lookWest);
            
            if(moveDir==NORTH) { yCounter--; bestPath[spacesMoved] = NORTH; }
            if(moveDir==SOUTH) { yCounter++; bestPath[spacesMoved] = SOUTH; }
            if(moveDir==WEST)  { xCounter--; bestPath[spacesMoved] = WEST;  }
            if(moveDir==EAST)  { xCounter++; bestPath[spacesMoved] = EAST;  }
            
//             curX = x+xCounter;
//             curY = y+yCounter;
            
            spacesMoved++;
            recursePath();
            
        }
        
        //bestPath = new int[moveCount];
        return bestPath;
    }
    
    // find the path that has thegreatest line of sight (in order n, e, s, w)
    public int findFurthestWay(int a, int b, int c, int d)
    {
        int greatestNumber = 0;
        
        if(a>greatestNumber) greatestNumber = a;
        if(b>greatestNumber) greatestNumber = b;
        if(c>greatestNumber) greatestNumber = c;
        if(d>greatestNumber) greatestNumber = d;
        
        // NORTH=1, EAST=2, SOUTH=3, WEST=4
        if(a==greatestNumber) return NORTH;
        if(b==greatestNumber) return EAST;
        if(c==greatestNumber) return SOUTH;
        if(d==greatestNumber) return WEST;
        
        return 0;
    }
        
    // reset recursePath vars.
    public void resetCounters()
    {
        xCounter = 0;
        yCounter = 0;
        spacesMoved = 0;
        neededExtraMoves = 0;
        moveCount = 0;
        bestPath = new int[moveCount];
    }
    
    // record the positions of the walls
    public void storeWallLocations()
    {
        // Store the locations of the walls
        if(lookNorth!=100) wallLocations[x][y-lookNorth][0]=true;
        try{wallLocations[x][y-lookNorth-1][2]=true;} catch(Exception e){}
        
        if(lookSouth!=100) wallLocations[x][y+lookSouth][2]=true;
        try{wallLocations[x][y+lookSouth+1][0]=true;} catch(Exception e){}
        
        if(lookWest!=100) wallLocations[x-lookWest][y][3]=true;
        try{wallLocations[x-lookWest-1][y][1]=true;}  catch(Exception e){}
        
        if(lookEast!=100) wallLocations[x+lookEast][y][1]=true;
        try{wallLocations[x+lookEast+1][y][3]=true;}  catch(Exception e){}
    }
}

BestJewSinceJC - could you please elaborate? I'm afraid I don't quite understand.....

[BestJewSinceJC]

I'm just going to link you to the project that I was given back when I did it. It gives you the exact algorithm; you just need to implement it. My project was somewhat different, but the way that you get from the start to finish of the maze is the exact same.

http://www.csee.umbc.edu/courses/undergraduate/341/fall08/projects/proj2/341-fall08-p2.shtml

Go to the part where it says "the algorithm". If you don't understand why the algorithm is used, then ask me. But I do guarantee you that it works. And it's important to understand why it works correctly, so spend a few minutes trying to figure it out on your own, and then don't hesitate to ask questions if you need to.

[llemes4011]

thanks for the link, it has given me some good (I think) ideas. Some things will have to be changed because i dont have a file to read the maze from, lol. But i think i have a solution to that ;)

one question. when returning north, south, east, or west, is it every turn, return the next in the sequence, and put it on hold, or start back at north each move?

[BestJewSinceJC]

1. From whatever cell you're at, check the North cell. If you can go there, add it to your list. Check the South cell. If you can go there, add it to your list. Check the East cell. If you can go there, add it to your list. Check the West cell. If you can go there, add it to your list.

After you do that, if your current cell is named currentCell, and you're using an LinkedList called availableCells, do currentCell = availableCells.removeFirst(). In other words, set current cell = the first cell in your availableCells list, and remove the first cell from the availableCells list. Now go back to step 1. and repeat until you find the finish.

And if you don't have a file to read the maze from, then how are you getting the maze?

One more thing - if you still don't understand how the algorithm works, create a small maze and follow its steps. Once you do that you'll definitely understand. Here's an example, where # are walls, x is start space, o is goal space, and * are spaces you can go to.

#####
# x** #
#*#*#
#** o#
#####

Ok. You initially have a queue. Using a LinkedList for the queue, called availableSpots. You also have a currentCell Object which is initially the start cell. Now, doing the algorithm

1. We look at our current cell (the start cell / the x). Looking to the North, we cannot add anything to our list. Looking to the South, we add that space. Looking to the West, we cannot add it. Looking to the East, we can add it.
2. Now that we've added everything around our current cell, the next step of the algorithm says to get the next cell from the list. Remember, we added the S then the E of the start space. So we will remove the S (since its the first thing in the list).

#####
#x** #
#*#*#
#** o#
#####

We're now at the place I bolded above. In our list, we have the cell that's to the right of the x which I marked with a "1". I'm going to start using numbers to denote what place in the list they are.

#####
#x1* #
#*#*#
#** o#
#####

Now, looking around, we can only add the cell to the South to the list. So the list now contains 1, 2.

#####
#x1* #
#*#*#
#2* o#
#####

Following the algorithm, we "walk to the next cell" (set our current cell to the first thing in the list, which is 1). Now our list only contains 2.

Is that making any sense?

[BestJewSinceJC]

If that explanation didn't make sense, which I doubt it did, use the maze I gave you above and go through the algorithm. The maze I gave you above is small enough to do quickly but it demonstrates what you need to know about the algorithm. Just go through it step by step and you'll understand it by the time you finish the maze. And yes, the algorithm I gave you is definitely correct. Google Maps uses a more sophisticated, but similar, algorithm.

[llemes4011]

The maze is being randomly generated in another class, and displayed through yet another. Therefore, you have to gather information from the maze as you navigate your way through it.

I understood your explanation pretty well ;)

[BestJewSinceJC]

Therefore, you have to gather information from the maze as you navigate your way through it.

In any case, you somehow have a representation of a maze. If you figure out a different way [other than using a stack or a queue and the algorithm I suggested] to do this program I'd be very interested to see it. But good luck on your project.

[llemes4011]

Sorry for the late reply,

I think i found a fairly good way of solving it, my friend sent me this: http://www.cs.bu.edu/teaching/alg/maze/

In conjunction with what you gave me, what i have turned out pretty well. It doesn't make it to all of the exits every time, and sometimes gets stuck... but i knew i'd have problems like that, i always do, lol.