# Shortest Path through A Maze (SOLVED)

This topic is 4824 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Try this site he has lots of links to pathfinding resources

##### Share on other sites
http://en.wikipedia.org/wiki/Shortest_path_problem

You just interpret your maze as a graph, each free field is a node, adjacent free field are connected by an edge. weight for each edge is 1.

##### 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 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 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.connections.weight/dest? I figure I should fill that before I pass it to Dijkstra(). Thakns.

##### 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 on other sites

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 on other sites
I had a feeling this would happen... lol. Eitherway, I've never done this and I am rather clueless.