Sign in to follow this  
Darobat

Shortest Path through A Maze (SOLVED)

Recommended Posts

Greetings, If I have a maze of a char array [20][20], how would I be able to get from point a to point b with the shortest route? A*? Where are some good tuts for doing this? Thanks. [Edited by - Darobat on December 4, 2004 1:16:41 PM]

Share this post


Link to post
Share on other sites
I'm using Dijkstra's Algorithm(http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and I have a few questions. When you call the function, the graph should be already loaded, but what goes in
DijkEdge* connections; /* An array of edges which has this as the starting node */
int numconnect;


Is connections just an array of nodes that are next to it and numconnect is the number of nodes in the array? In the DijkEdge array, whats dest and should I set weight to anything? I'm kinda lost on how to implement it. Also, how would I get a list of all the nodes in the shortest path? Thanks

[Edited by - Darobat on December 3, 2004 8:28:05 PM]

Share this post


Link to post
Share on other sites
A* certainly will do the job. This is a matrix so you can use Manhatam Distance that is

d((x0,y0), (x1, y1)) = |x0 - x1| + |y0 - y1|

this will work fine.


The Dijkstra's Algorithm is quite simple and what theses variable means is dependent of your implementation. It takes the nearest distance from the actual node and updates all the distances. In other words:

Initially you set all node as not explored and all distances to infinity. Then from all vertices that have a non-explored node as target you select the estimated nearest one, that I will call u. Mark u as visited and the distance from the source node to u is set to the edge weight. In u do the same from the source edge and choose the node with the smallest distance from the source, this time the distance is source -> u + u -> targets. After visiting all the nodes you will have the distance from the source to all the other nodes. Note that you can't use negative weights for the edges

Share this post


Link to post
Share on other sites
I'm using code directly from http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

If I have a char map[20][20] which has all the walls, spaces, source, and destination, how would I use it to navigate. Basicly, I have all the Vertex's in the graph, but what goes in
graph[i].connections.weight/dest? I figure I should fill that before I pass it to Dijkstra(). Thakns.

Share this post


Link to post
Share on other sites
You should modify the Dijkstra implementation so that rather than requiring a separate node graph in memory, it works on your tilemap, making assumptions about adjacent nodes and path cost (i.e. path cost is constant, and adjacent tiles are adjacent nodes).

For a small map, Dijkstra should be fine.

Mark

Share this post


Link to post
Share on other sites
Looking for advice on your own contest, eh? Oh dear… [smile]

I recommend that you start with a queue<T> where T holds an x and y coordinate. Start with this queue containing only the starting point. At each step, read a value off the queue and check each of the four squares around it in turn. For each of those squares, check whether it is an empty space. If it is an empty space, replace it with a marker pointing towards the previous square, and add it to the queue. Once you reach the ending point, you'll have a trail of markers leading you back to the starting point.

If you have any further questions, please refer to the entry I submitted to you. [wink]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this