Quickest Maze Solve Algorithm?
Hello all.
I am a high school student and regularly go to contests that involve problems of finding the shortest path to solve a maze. The path inputs will be from file, a grphical representation of the maze, with each grid either being a wall character (say, ' * '), a path character (say, ' . '), or a start or end character ('S' or 'E'). I have experimented with various maze algorithms (recursion and Bellman's flooding algorithm, for example) but am convinced that there are quicker maze solve methods out there. Could you please post a quick walkthrough of your algorithm ( some code snippets would help) and the running time to solve a 100x100 blank maze, with the start at one corner and the end at the opposite corner.
Thanks!
And what exactly is it that leads you to be convinced that there are quicker methods out there?
You think that perhaps "we" are keeping the best algorithms to ourselves so that we can win the maze running competitions, but all you need to do is ask nicely and we will tell you our secret algorithms?
Is there something that Bellman's algorithm is doing that strikes you as wasted effort giving you room to improve on that method?
What's the benefit of Bellman's algorithm over Dijkstra's? Isn't it the ability to handle negative-weight cycles? If so, you may as well use Dijkstra's.
> And what exactly is it that leads you to be convinced
> that there are quicker methods out there?
>
> You think that perhaps "we" are keeping the best
> algorithms to ourselves so that we can win the maze
> running competitions, but all you need to do is ask
> nicely and we will tell you our secret algorithms?
>
> Is there something that Bellman's algorithm is doing
> that strikes you as wasted effort giving you room to
> improve on that method?
First of all, I want to say that I'm not here to rip you of your secret maze solving algorithms; I was simply trying to see if there were more efficient algorithms, possibly on the internet, that I had not known about.
Perhaps I didn't make myself clear: the competition problems that I encounter are largely simple mazes, bidirectional and without weighted edges. The algorithm that I'm looking for is one that is A) quick to run, so that the judges who are grading my program will not think that my program froze; B) quick to type because there is a time restraint on all contest problems; and C) able to print out one of multiple shortest paths from one point to another.
Therefore, I am not trying to find exactly the best possible sorting algorithm, but the quickest to type and run in a contest setting. And after reading a bit more on Bellman-Ford and Dijkstra, I realized that those methods were entirely unnecessary for the type of maze problems that I encounter. Now I am clueless as to which algorithm to use; several of my team members use a recursive solution (which is fairly quick to type--around 25 lines but which takes forever to run for mazes past 10x10, much less 100x100). Others suggested using a flooding-type algorithm, and while those solutions are quick to run, they take quite longer to type( around 90 lines). So I am looking for one that is both quick to run and quick to type (I am willing to sacrifice efficiency for typing speed, especially if the time discrepancy for 100x100 or less mazes is unnoticeable). Memory constraints are usually not a problem.
If you know of any algorithms that fit my needs, please post them!
Thanks
100x100 mazes are 10000 nodes, which can be searched through in the most stupid way in less than 10 ms.
Dijkstra and Bellman seem overkill
Use your own stack, recursive solution is much more expensive in time and memory. If your maze has round-walks, have a BitSet that remembers walked paths.
If you reach a wall, you can discard all positions on the wrong side of the path.
Gil
> 100x100 mazes are 10000 nodes, which can be searched
> through in the most stupid way in less than 10 ms.
Could you show me how to search through in less than 10 ms? Even the quickest way that I've seen right now take at least 5 seconds.
>
> Dijkstra and Bellman seem overkill
>
> Use your own stack, recursive solution is much more
> expensive in time and memory. If your maze has
> round-walks, have a BitSet that remembers walked
> paths.
>
> If you reach a wall, you can discard all positions on
> the wrong side of the path.
>
> Gil
Could you explain what you mean by "have a BitSet" (how would you structure it) and "discard all positions on the wrong side of the path"? How would you know which side was the wrong side? And your way would seem awfully long to type; could you post how many lines (approximately) it would take to fully implement your algorithm?
Thanks
Ah, fast to type, now there is a decent optimization parameter.Are you allowed to look at written down code or does this have to be typed in from memory?
Here is my shot at a minimal encoding of the Bellman's flood algorithm.
It wastes memory (dual large arrays), passes parameters by global allocation, and uses single letter names, none of which are recommended coding practice but were done to minimize the typing in of the algorithm.
May require a bit of reading to see how it works, but once you get it, it is not too hard to produce from memory on demand.
Primary reduction is to encode 2D array as 1D, to eliminate double subscripting, and to use maze array itself as the queue for the frontier.
public static class Maze2{
int a,b,x,y,ss,gg;
int[] s,g;
void solve(String[] maze){ // maze MUST have solid border of *
x = maze[0].length();
y = maze.length*x;
s = new int[y];g = new int[y];
for(int i = 0; i<y; i++){
s[i]=-1; g[i]=-1; // path
char ch = maze[i/x].charAt(i%x);
if(ch=='*')s[i]=-2; // wall
if(ch=='S')ss=i;
if(ch=='E')gg=i;
}
a = gg; b=gg;
while(a!=ss){add(a,1); add(a,-1); add(a,x); add(a,-x);a=s[a];}
while(a!=gg){System.out.print(sv(g[a])); a+=g[a];};
System.out.println();
}
void add(int p, int o){if(s[p+o] == -1){s[b]=p+o; b=p+o; g[p+o]=-o;}}
String sv(int o){if(o>0) return (o==1)?"E":"S";return (o==-1)?"W":"N";}
}
This sample code:
Maze2 ma = new Maze2();
String[] maze = {
"****************",
"*.*.*.**......E*",
"*...*.**.*.***.*",
"*.***.**.*..**.*",
"*.....**.****..*",
"*.***.**....*.**",
"*.*.*.**.*.**.**",
"***.*.**.*.**.**",
"*..*.....*.**.**",
"*.*.**.***.*****",
"*.*.**.***.*****",
"***.**.***...***",
"*...**.*****.***",
"*.******...*.***",
"*S.......*...***",
"****************" };
ma.solve(maze);
produces output
EEEEEEENEESEENNNWWNNNNNNWWNNNNEEEEEE
I don't know if it breaks 10msec but it runs so fast it makes your eyes bleed!
As you can see it takes 10 lines to convert the input into an array, but Once you have your array, A one line while loop (which calls a one line subroutine) does the entire flooding. Similarly a single line while with its one line subroutine dumps the output.
Since the guts of the code is really only 5 lines long (counting the two one liner subroutines) That is why it is not so difficult to spew this entirely from memory if that should be necessary.
I was teasing earlier about "secret" algorithms, but I was convinced at the time and this little writing exercise leaves me even more convinced that it is unlikely that there is anything that is either easier or faster than Bellman's algorithm.
Enjoy!
> Could you show me how to search through in less than
> 10 ms? Even the quickest way that I've seen right now
> take at least 5 seconds.
1. Read bytes, don't create Strings - much more code but so much faster
2. Convert your '*'s and '.'s to a boolean[][] array representing the maze
3. Have a position stack (int[] x, and int[] y) back through stack when you get stuck
> Could you explain what you mean by "have a BitSet"
java.util.BitSet
If the maze is 10x10, the position x=7 and y=3 could be represented by the bit 10*7+3=73. So when you walk at x=7 and y=3, call .set(73). Next time walking toward x=7 and y=3, .get(73) wil tell you that you've already been there.
This is also the way you discard positions on the wrong side of the path. When comming the the wall, you can take all the positions on the other side of the current path and set those bits to false.
> And your way
> would seem awfully long to type; could you post how
> many lines (approximately) it would take to fully
> implement your algorithm?
There is no shorcuts to good programs. My maze solver took 80 lines to build maze from the file and 80 lines to solve the path.
Gil
This is what I've managed to come up with after much deliberation. Simply storing all possible shortest paths starting from the start and radiating out. Fairly quick to run and type, and the middle 4 if statements are simply copy/paste with minor editions.
public void solve(String maz, int r, int c) //maz=maze contents, no separation; r = # rows; c = #columns per row
{
String[] ar = new String[r*c];
int s = maz.indexOf('S'), e = maz.indexOf('E');
ar[s] = ""+(char)(s);
lp: for(int i=0;i<r*c;i++)
{
for(int x=0;x<r*c;x++)
{
if(ar[x]!=null)
{
if(x==e) break lp;
if(x%c!=0 && ar[x-1]==null && maz.charAt(x-1)!='*') ar[x-1]=ar[x]+(char)(x-1);
if(x%c!=c-1 && ar[x+1]==null && maz.charAt(x+1)!='*') ar[x+1]=ar[x]+(char)(x+1);
if(x/c!=0 && ar[x-c]==null && maz.charAt(x-c)!='*') ar[x-c]=ar[x]+(char)(x-c);
if(x/c!=r-1 && ar[x+c]==null && maz.charAt(x+c)!='*') ar[x+c]=ar[x]+(char)(x+c);
}
}
}
if(ar[e]==null) {out.println("Cannot reach");}
else
{
out.println(ar[e].length()); //prints out length of shortest path
char[] ar2 = maz.toCharArray();
for(char b : ar[e].toCharArray())
ar2[b]='+';
String ar3 = new String(ar2);
// I have the program print out a graphical path instead
for(int x=0;x<r*c;x+=c) out.println(ar3.substring(x,x+c));
out.println();
}
}
This method works without * boundaries. So for input ( I've added "\n" for clarity, but remember that in the parameters there are no delimiters)
solve(
****************
*.*.*.**......E*
*...*.**.*.***.*
*.***.**.*..**.*
*.....**.****..*
*.***.**....*.**
*.*.*.**.*.**.**
***.*.**.*.**.**
*..*.....*.**.**
*.*.**.***.*****
*.*.**.***.*****
***.**.***...***
*...**.*****.***
*.******...*.***
*S.......*...***
****************
, 16, 16);
would yield
37
****************
*.*.*.**+++++++*
*...*.**+*.***.*
*.***.**+*..**.*
*.....**+****..*
*.***.**+++.*.**
*.*.*.**.*+**.**
***.*.**.*+**.**
*..*.....*+**.**
*.*.**.***+*****
*.*.**.***+*****
***.**.***+++***
*...**.*****+***
*.******+++*+***
*++++++++*+++***
****************
What are your opinions? Please try running them on the some huge data (my computer at home is a Pentium II 366, so I can't do much beyond 100x100) and please tell me what you get.
Also, any possible improvements?
Thanks>
Please take a closer look at the algorithm that I supplied.
I would guess that the reason that you can't do much more than a 100x100 is that your version is an N^2 algorithm and the one that I wrote is N. The result is that for a 100x100 maze yours need about 100 million operations and the one that I wrote will take about 10 thousand. Yours will run about ten thousand times slower than mine for problems of that size.
Take a closer look at what the add routine does. I do NOT just store a back pointer that marks the path. I do that in the g array. The s array is being used to store a forward pointer, a list, showing the frontier of points that I need to grow by one. It is by maintaining and running that list of pointers that I get the order N behavior.
Also, just for the record, the reason my routine is called Maze2 is because Maze1, my first attempt, used a single array to both maintain the frontier list and to hold the path back pointers. It used less space, but required more code.
So my opinion, for what it's worth, is that I prefer what I wrote to what you wrote. Not that it matters. I am not going to be entering any contests and trying to cough up maze solving programs that require little typing. If you can remember what you did better than you can remember what I did, then by definition, your code is better for your real problem which is having something that you can type quickly.
I have not tested my algorithm on large mazes because I have no routine to generate large mazes and have no interest in writing one, so if you want comparison tests you will need to run them yourself.
You chose both a different input format and a different output format from the ones that I used, and also chose to eliminate boundary conditions with code instead of with data, which makes it difficult to compare the two routines directly just in terms of typing required.
Clearly the version that I supplied could be mushed around to match the formats of you choice, in particular, my method for unpacking the solution could be modified to unpack into plus signs in the original maze char[] if that is your prefered format.
I have not much interest in hacking out the glue code to match vaguely specified formats, not that I in anyway diminish the importance of that code. That is most of what programming is, converting data from one poorly sepcified format into another. The code that I wrote was 18 lines, only 2 of which "solved" the maze, the others were all converting the input into the format that would let me solve it in 2 lines or were used to unpack it into my output format.
So if you want to hack up my algorithm to use a different format feel free to do so.
Also for the record I saw another place in my routine where I could trim size by passing through a global variable. (Hard to unlearn years of good habits!)
I could have eliminated the parameter p in the add routine and used:
while(a!=ss){add(1); add(-1); add(x); add(-x);a=s[a];}
void add(int o){if(s[a+o] == -1){s[b]=a+o; b=a+o; g[a+o]=-o;}}
Tested on my HP notebook with AMD Sempron 2800+, 512 Mo RAM: average time on 50000 iterations gives less than 1 ms per iteration.
> Tested on my HP notebook with AMD Sempron 2800+, 512> Mo RAM: average time on 50000 iterations gives less> than 1 ms per iteration.Which algorithm were you using, and what was the sample input (how big was the maze)?
> > Tested on my HP notebook with AMD Sempron 2800+, 512
> > Mo RAM: average time on 50000 iterations gives less than 1 ms per iteration.
>
> Which algorithm were you using, and what was the
> sample input (how big was the maze)?
Sorry for late reply, i was using the code posted in reply #9
I think the maze was 32 x 32.
Brilliant code, works on my robot :)how do u do a graphical trace on the maze?I am a bit confuse withString sv(int o){if(o>0)return(o==1)?"E":"S";return(o==-1)?"W":"N";}
Four months! You expect me to be able to decode purposefully obfuscated code 4 months after it was written? There are no comments in it because that would take up too much typing. The variables are one letter names to reduce typing time. I have very little idea at this point how this code works?
Rather, I only recall how it works, I have no memory of how I mapped the algorithm to code. If I recall correctly, and I refuse to look at the code, I have an array that started out with numbers in it, that marked walls and open space (and start and stop). I have a list of cells in one of the arrays that marks the frontier or border (cells whose neighbors should be examined). Upon initialization the stop point is the only element in the queue. I pull an element from the front of the queue and add his empty neighbors to the back of the queue. I only add empty neighbors because some neighbors have walls and some neighbors were already in the queue meaning that they were closer to home and have already been evaluated. When I am examining a neighbor of a frontier cell, that direction that you must walk from that neighbor to get to the frontier cell is known, either NSEorW. I write a number which encodes that direction into the neighbor cell in the second array to indicate which way to walk if you are ever in that cell. The result, every marked cell in the second array is marked with the direction to step in order to get to a cell that is closer to stop.
At some point in time, the neighbor being investigated is the start cell (if there is a solution and my code does not as I recall waste any code testing for a valid maze). When you reach that point, you can just walk the second array because each cell is marked with which direction to march next. The sv() routine you asked about is decoding the number that was written into the second array as a compass direction. The number in the array is actually the offset that you need to add to a given index to move to the next cell index. (OK, so I did look at the code.)
IF you want to modify the code so that it changes the maze strings to have little plus signs instead of dots at each of the points on the solution path, you need to keep an X and Y value, initialized to the start coordinates, and as you generate the letters, NSEW, of the solution path, you increment or decrement the X or the Y value and then mash the Xth character in the Yth string into a plus.
haha marlin - chill man, its all cool, I got it all working :DI found out those 1 -1 x and -x are directions, I love that piece of code :-)thx for that man, save me heaps of time.
