Shortest distance out of the maze

Hi everyone:


This is not a programming language question, but a question about an algorithm. I'm making a small game and in it I need to know the shortest distance inside the maze for the object to get outside of the maze. Please see the picture attached. Here's how I was intending it to work.

Say, I need to write a function that on the input will get an object's current coordinates - for the picture example, say (3, 1) - and then the function will return a suggested next move for the shortest way out of the maze. For the example, first it should be "right", then on the next function runs it should return 5 times "down", then 2 times "right" and then 7 times "up".

It sounds like a simple thing for a human being to see, but I can't put my head around programming it.

Any help would be appreciated!



PS. If the shortest distance seems to be an issue, I'd take a suggestion for an algorithm for "any" way out of the maze.

Breadth-first-search is the usual way to solve such things. (Depth-first may be faster in the "any route out" case.)

I don't have 'fix' for you, but I remember 1 way to get out of any maze you want if you would be in a real maze. Put 1 of your hands on a wall and never let go and start walking. If you notice that you are in a loop, use your other hand on another wall, because it means that your hand is an a 'island'. You could try to convert this idea into a formula.

Hi there,

I had a very similar problem assigned to me as a question for my scholarship entrance many years ago. The question was to find the shortest distance between in steps between 2 points in a maze.

As other have said so far your best bet is to use a breadth-first search. Circling outwards from the start point set a value in each square that is equal to the minimum number of steps from the start point. Once you reach the end point, the exit in your case, You will have the shortest amount of steps and you can build a path back to your start point.

For further reading on the topic I would suggest reading about Dijkstra's Algorithm, which this is a basic implementation of.

Dijkstra's Algorithm, Wikipedia

Good luck

Thank you guys. The A-star seems to be exactly what I want (it's a variation of the one mentioned):
http://en.wikipedia.org/wiki/A-star

At this point I'm struggling understanding it though. I got this C++ example project off the Wikipedia, but it's too complicated :( I wish there was simple C or JavaScript sample of just the algorithm.

A* is pretty simple.....
1) Define a priority queue Q containing nodes to visit.
2) Initially, Q contains only your starting node.
3) At every step, pop the highest-priority node out of Q and move to it. Mark the distance traveled to get there as the distance of the node you moved from plus the move length. Add all its unvisited neighbors to Q with priorities determined by your distance traveled so far and a heuristic H, and an indication of which node they were added from.
4) If you ever pop an already-visited node out of Q, just ignore it. You've simply found a longer path to get there than you already had.
4) When you reach the goal node, you're done, since you can just trace back how you got there.
5) If Q becomes empty, your goal node is unreachable.

The only trick to it is choosing H. So long as H never overestimates the true distance to the goal, the path found is guaranteed to be optimal. The euclidean distance usually makes a good choice for H.

Maybe this link would be of any use for you, it has not only the solving algorithms but the creation too.

http://www.astrolog.org/labyrnth/algrithm.htm

gamedev.net has some good reading about the a-star algorithm (and much more).