Jump to content
  • Advertisement
Sign in to follow this  
suliman

Adjacency matrix and dijkstra pathfining? (c++)

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi

Im trying to understand dijkstra pathfinding. But i need to use it on a grid which im only used to doing on a star. Most implementations look something like this:

const int inf = 1 << 30;

// given adjacency matrix adj, finds shortest path from A to B
int dijk(int A, int B, vector< vector<int> > adj) {
	int n = adj.size();
	vector<int> dist(n);
	vector<bool> vis(n);

	for(int i = 0; i < n; ++i) {
		dist[i] = inf;
	}
	dist[A] = 0;

	for(int i = 0; i < n; ++i) {
		int cur = -1;
		for(int j = 0; j < n; ++j) {
			if (vis[j]) continue;
			if (cur == -1 || dist[j] < dist[cur]) {
				cur = j;
			}
		}

		vis[cur] = true;
		for(int j = 0; j < n; ++j) {
			int path = dist[cur] + adj[cur][j];
			if (path < dist[j]) {
				dist[j] = path;
			}
		}
	}

	return dist[B];
}

What is A and B? Indexes to the start and goal node? It's a graph and not a grid I assume. Can I build a adjacency matrix from a grid and use the above implementation or would there be a completely different implementation for using dijkstra on a grid?
Lets assume my map looks like:

1 0 1
1 0 1
1 1 1

And "0" means impassable node. And I need to pathfind from topleft to topright. How would I setup "vector<vector<int>> adj" so it described this map? A and B? Or is it a stupid way of doing it? I need a minimal pathfind but they seem to always look like the one above.

Thanks for your input!
E

Edited by suliman

Share this post


Link to post
Share on other sites
Advertisement
First of all, don't use vector<vector<int>>. Your data will not be laid out contiguously in memory and it complicates identifying a node, which should be as simple as using it's index in the array. Two dimensional arrays are just one dimensional to the computer, so array[n][m] is the same as array[n*m] which means all you need is vector<int>. To compute the index of the 2D coordinate [x, y] you can use x * m + y.
 

What is A and B? Indexes to the start and goal node? It's a graph and not a grid I assume.

Yes, they're just indexes to the start and goal node. A grid is a type of graph, this doesn't matter to the algorithm.
 

Can I build a adjacency matrix from a grid and use the above implementation or would there be a completely different implementation for using dijkstra on a grid?

No need to build an adjacency matrix if you're using a grid, you can easily compute the indices of the adjacent nodes. The indices of the adjacent nodes are i +-1 and i +- m + <-1, 0, 1>.
 

How would I setup "vector> adj" so it described this map?

vector<int> { 1, 1, 1, 0, 0, 1, 1, 1, 1 }
 

I need a minimal pathfind but they seem to always look like the one above.

Minimal in what sense and why?

Share this post


Link to post
Share on other sites

Dijkstra is equivalent to A* with 0 for the estimate.

That estimate makes that the algorithm doesn't care about the estimate at all, it simply always expands the nearest unexpanded node. On an regular grid that makes it expand in all directions equally fast.

For a path from A to B, Dijkstra only makes sense if you cannot compute an estimate for the remaining distance to B. It is also useful for getting many distances from A (a single Dijkstra run gives all of them, a single A* run gives you just 1 distance).

Share this post


Link to post
Share on other sites

Thanks for your help!

Im trying to change the code to understand what's going on. See below.

I try to make it to go from A=(0,0) to B=(2,0), is this correct? Where is the found path stored? I want the map to be described row by row. In my example below again:

1 0 1
1 0 1
1 1 1

So I need to go down, then right then up to start at (0,0) and reach the tile at position (2,0).

int dijk(int A, int B, const unsigned char* pMap, const int mapW, const int mapH) {
	int n = mapW*mapH;
	vector<int> dist(n);
	vector<bool> vis(n);

	for(int i = 0; i < n; ++i) {
		dist[i] = inf;
	}
	dist[A] = 0;

	for(int i = 0; i < n; ++i) {
		int cur = -1;
		for(int j = 0; j < n; ++j) {
			if (vis[j]) continue;
			if (cur == -1 || dist[j] < dist[cur]) {
				cur = j;
			}
		}

		vis[cur] = true;
		for(int j = 0; j < n; ++j) {
			int path = dist[cur] + pMap[cur+j*mapW];
			if (path < dist[j]) {
				dist[j] = path;
			}
		}
	}

	return dist[B];
}

int main() {
	unsigned char pMap[] = {1, 0, 1, 1, 0, 1, 1, 1, 1};
	int ans = dijk(0,2,pMap,3,3);
}
Edited by suliman

Share this post


Link to post
Share on other sites

Is the dist-vector used to hold the path? It seems to just calculate costs (distances) for each tile (with very high distances for node [3] and [4]).

Share this post


Link to post
Share on other sites

Why would you need the path if you know the minimal distance to the starting point for all nodes?

From any node (with a non-zero distance) find the direct neighbour with the smallest distance.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!