Navigating through a 2D array based maze
Ok guys, I know you all hate being asked for outright answers so I hope this isnt the case, but i really need help.
I've been designing a maze that loads up a properties file into a 2d array called coOrdinates. These coordinates relate to a bunch of static ints (Wall, Inner, Sprite, EndPos, Visited and Blocked). Having created a Gui to show the maze incorporating the MVC framework, i should eventually be able to get it to update on screen (though I should be able to figure out that one myself). What i need is an algorithm using recursion that will take the sprite (Which i have also begun falteringly to create in a class called MySprite which has more static ints for the directions)around the maze, and backtrack out of dead ends if necessary. I know what my algorithm should do, but not how it should do it. Without writing too much more, i need to look at the coOrdinates, see if it is one of the above positions in the grid, and act accordingly. My main problem is relating the coordinates to a set of values that will let me make the Sprite the next position on the Inner (or Path). I can give more details (believe it or not) to anyone who is willing to help me. I would be endlessly obliged and will stop brownnosing.
static class Position{
public int x,y;
...
}
//matrix with "walked" positions
boolean[][] walked;
//trail from the start of the walking sprite.
ArrayList trail;
//code that just chooses any path that doesn't lead to a already walked path
Position currentPos=startPos
//try up
while(!Position.equals(endPos)){
//up
if(!walked[currentPos.x][curretnPos.y-1] && (/*code to determin if there is a path "up", eg not a wall etc*/)){
trail.add(currentPos);
currentPos=new Position(currentPos.x,curretnPos.y-1);
//right
}else if ...
//left
}else if ...
//down
}else if ...
//back in trail
}else{
currentPos=(Position)trail.removeLast();//use a s a stack
}
walked[currentPos.x,currentPos.y]=true;//mark it walked
}
The "walked is not necessary if you always have only 1 posible path to get to a point, that is no circles. Then instead for each Position remember which alternatives you've already taken, eg a position can be marked to already have walked "up" and "right".
Hope this helps.
Gil
Ok, here's what i got so far, but i stink at java, even though I am trying my hardest.
import java.util.ArrayList;
/*
* Created on 29-Nov-2003
*
* To change the template for this generated file go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
/**
* @author David Price
*
* To change the template for this generated type comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class MySprite
{
public Maze maze;
public int spritePos = Maze.Sprite;
public int nextPosY;
public int nextPosX;
public static final int NORTH = 1;
public static final int SOUTH = 2;
public static final int EAST = 3;
public static final int WEST = 4;
public MySprite() throws ArrayIndexOutOfBoundsException, NullPointerException
{
super();
}
/////////////////////////////////////////////////////////////////////////////////////////
static class Position
{
public int x,y;
... //NOT SURE WHAT I NEED HERE!
}
//matrix with "walked"
positions boolean[][] walked;//trail from the start of the walking sprite.
ArrayList trail;
//code that just chooses any path that doesn't lead to a already walked pathPosition
currentPos=startPos
while(!Position.equals(endPos))
{ //up
if(!walked[currentPos.x][currentPos.y-1] && NORTH == 0)
{
trail.add(currentPos);
currentPos=new Position(currentPos.x,currentPos.y-1); //right
}
else if (!walked[currentPos.x][currentPos.y-1] && EAST == 0)
{
/////DUNNO IF ANY OF THIS SURROUNDING BIT IS RIGHT!
trail.add(currentPos);
currentPos = new Position(currentPos.x, currentPos.y-1);
}
else if (!walked[currentPos.x][currentPos.y-1] && SOUTH == 0)
{
trail.add(currentPos);
currentPos = new Position(currentPos.x, currentPos.y-1);
}
else if
{
//back in trail (NOT SURE HERE EITHER)
}
else
{
currentPos=(Position)trail.removeLast();//use as a stack
}
}walked[currentPos.x,currentPos.y]=true;//mark it walked
}
I really am quite bad at this, im not able to relate what the solve algorithm does with the coOrdinates of my Maze class. You are an absolute star for all you've given me so far, its helped more than you could imagine.
How do you want the maze to be navigated?! One way is the 'flood fill' algorithm which works as follows:
#: Wall
E: Exit
S: Starting point
Initial situation
#####
#S#E#
# # #
##
# # #
# ###
#####
Iteration 1
#####
#S#E#
#1# #
##
# # #
# ###
#####
Iteration 2
#####
#S#E#
#1# #
#2 #
# # #
# ###
#####
Iteration 3
#####
#S#E#
#1# #
#23 #
#3# #
# ###
#####
Iteration 4
#####
#S#E#
#1# #
#234#
#3# #
#4###
#####
Iteration 5
#####
#S#E#
#1#5#
#234#
#3#5#
#4###
#####
Note that each cell of the matrix will contain the minimum number of steps required to go there (for this example I assumed that you cannot move diagonally).
If you 'paint' a certain cell with a number you can also record the predecessor for that cell i.e. the cell you have to go to to reach the starting point.
If you want to know the shortest path to the Exit from _any_ cell, all you have to do is execute the algorithm with the exit as starting point and continue as long as there are empty cells to label.
By backtracking from end to start using this information you can construct a list which describes how to reach the exit.
Hi,I am not giving any code, but I can help you with a strategy to get out a maze. A strategy that works (if there is a way of getting out) is to turn right whenever you can. You do not have to backtrack in this way. Just turn right and you will get out.Good luck.
> A strategy that works (if
> there is a way of getting out) is to turn right
> whenever you can. You do not have to backtrack in this
> way. Just turn right and you will get out.
Sure ... +-+-+-+-+
in-> -> out
+ +-+ + +
| | | | |
+ +-+ + +
|| |
+-+-+-+ +
||
+-+-+-+-+
kind regards,
Jos
I did not say that you get out the quickest way, but you get out. Of course you have to turn back if you cannot go further or turn right.
Unfortunately we've been told we cannot go right all the time, it has to be a randomly generated number between 1 and 4 (i figured using math.random). This method needs to involve recursion, and has to have a wall, a path, an end position, a sprite, and a way to mark a block as visited. Plus, if i visited block leads to a dead end, it needs to backtrack through those blocks, and mark them as unvisitable.
> I did not say that you get out the quickest way, but
> you get out. Of course you have to turn back if you
> cannot go further or turn right.
Even then ... my first example contained a small 'ASCII-art' error; have a look at the following little maze --
+-+-+-+
in->-> out
+ +-+ + +
| | | | |
+ +-+ + +
|| |
+-+-+-+-+
As you can see, the topology of this maze causes your algorithm to cycle and cycle and ...
Your algorithm would work if the maze could be 'un-tangled' as a tree (i.e. no cycles), otherwise
backtracking is unavoidable.
kind regards,
Jos
ps. I hate to guess where my characters are positioned when I need some fixed char width stuff and all
I get is this lousy proportional font editing area ... (hint, hint)
Backtracking is allowed, in fact its positively recommended, as what our algorithm is supposed to show is the use of an unbounded stack and/or recursion. Im going for recursion, which uses an internal stack, so basically, as I hit each square/coordinates, i need to mark it as visited and push it onto the stack. I'm seriously at my wits end, as i have no clue how im supposed to implement the recursion, of exactly how i make the sprite move to the next path block, while marking the previous block as visited. I know its cheeky, but what im basically asking for is what elements/variables i need to pass into my algorithm. Then i should be able to manipulate them at will. I just cant get a clear picture in my head how to do this. If any of you would like to see all the code, i can send you it, though obviously im not expecting anyone to do my work for me. After all, i'd just end up back in this situation when the next assignment rolls around.
Imagine yourself being dropped in some rectangular room with at most four doors and an infinite pile
of PostIts (those funny little yellow sticky papers) and a magic pencil that lasts forever. Before you
start running in circles, you observe that every room has connections to at most four adjacent rooms --
North, West, South and East, each connected by a door that can or can't be opened, i.e. you seem to
be trapped in a maze ...
First you decide that directions are ordered, say, N < W < S < E, so you can define a 'next direction'. Next
you want to determine whether or not if you've been in a room before or not. And, most important of it all,
you want to determine if your current room happens to be the 'exit' room. If you're in a room from where
there is no way to go, you want to be able to find out where you came from just to go back and try again
from there. If you're in a room not meeting the above requirements, you want to leave a little note in
which direction you've left this room going for further exploration of this darn maze ...
does this give you some clues?
kind regards,
Jos
Jos,I agree. The strategy that I proposed would not work on your example. Funny, A long time I thought this was a good strategy. Thank you for your example showing that I was in error.Paul
kspho5,the crux of it all is that it all depends on the topology of the maze; as I wrote somewhere above, if the mazedoesn't contain cycles, your strategy works fine, otherwise some form of backtracking is still needed.kind regards,Jos
Jos,
I think you've cleared it up more succinctly than i could have hoped. My main problem was representing the direction values, but if denote each value as greater than the one previous I might be able to navigate through the maze as I hoped. Thanks for your help, I'll keep you all informed about how it goes. Deadline is thursday, keep your fingers crossed.
