Help with implementing Dijkstra's Algorithm

tigerking (3)
Hello,
I am having trouble implementing pathfinding in my program. I am using coordinate based vertexes along with edges holding the coordinates of the related vertex. The vertexes are being stored within a map, and the edges inside of a multimap with the vertex coordinate being the key.
Here are the structures:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
double inf = std::numeric_limits<double>::infinity();
struct vEdge{
	LONG x1, y1;
	LONG x2, y2;
	bool isLadder;
	JumpType jumpType;
	double dist;
	double weight;
	vEdge(LONG x1, LONG y1, LONG x2, LONG y2, bool isLadder, JumpType jumpType, double dist, double weight):
		x1(x1), y1(y1), x2(x2), y2(y2), isLadder(isLadder), jumpType(jumpType), dist(dist), weight(weight){}
	vEdge():
		x1(0), y1(0), x2(0), y2(0), isLadder(false), jumpType(NONE), dist(0), weight(0){}
};
struct Vertex{
	LONG x, y;
	Vertex(LONG x, LONG y):
		x(x), y(y){}
	Vertex():
		x(0), y(0){};
};

std::map<std::pair<LONG, LONG>, Vertex>vertices;
std::multimap<std::pair<LONG, LONG>, vEdge>vedges;


Most implementations of Dijkstra utilize an integer ID to store information on the vertex, such as vector<double>minDist. Unfortunately, that will not work with my program as the way I am grabbing the vertex/edge information might create duplicate vertex's. That is why I store it in a map and only use the XY coordinates.
Here is what I have so far for my implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
void dijkstra(std::pair<LONG, LONG> start, std::pair<LONG, LONG> end){
	if(vertices.find(start) == vertices.end()){
		try{
			Platforms* startPlat = *getPlatform(start.first, start.second);
			struct Vertex vStart = Vertex(start.first, start.second);
			vertices.insert(std::make_pair(start, vStart));
			struct vEdge eStartLeft = vEdge(startPlat->x1, startPlat->y1, vStart.x, vStart.y, false, NONE, pDist(startPlat->x1, startPlat->y1, vStart.x, vStart.y), 1);
			struct vEdge eStartRight = vEdge(startPlat->x2, startPlat->y2, vStart.x, vStart.y, false, NONE, pDist(startPlat->x2, startPlat->y2, vStart.x, vStart.y), 1);
			vedges.insert(std::make_pair(std::make_pair(eStartLeft.x1, eStartLeft.y1), eStartLeft));
			vedges.insert(std::make_pair(std::make_pair(eStartRight.x1, eStartRight.y1), eStartRight));
			vedges.insert(std::make_pair(std::make_pair(eStartLeft.x2, eStartLeft.y2), eStartLeft));
			vedges.insert(std::make_pair(std::make_pair(eStartRight.x2, eStartRight.y2), eStartRight));
		}catch(...){
			MessageBoxA(NULL, "Couldn't find starting platform", "Error", 0);
		}
	}
	if(vertices.find(end) == vertices.end()){
		try{
			Platforms* endPlat = *getPlatform(end.first, end.second);
			struct Vertex vEnd = Vertex(end.first, end.second);
			vertices.insert(std::make_pair(start, vEnd));
			struct vEdge eEndLeft = vEdge(endPlat->x1, endPlat->y1, vEnd.x, vEnd.y, false, NONE, pDist(endPlat->x1, endPlat->y1, vEnd.x, vEnd.y), 1);
			struct vEdge eEndRight = vEdge(endPlat->x2, endPlat->y2, vEnd.x, vEnd.y, false, NONE, pDist(endPlat->x2, endPlat->y2, vEnd.x, vEnd.y), 1);
			vedges.insert(std::make_pair(std::make_pair(eEndLeft.x1, eEndLeft.y1), eEndLeft));
			vedges.insert(std::make_pair(std::make_pair(eEndRight.x1, eEndRight.y1), eEndRight));
			vedges.insert(std::make_pair(std::make_pair(eEndLeft.x2, eEndLeft.y2), eEndLeft));
			vedges.insert(std::make_pair(std::make_pair(eEndRight.x2, eEndRight.y2), eEndRight));
		}catch(...){
			MessageBoxA(NULL, "Couldn't find ending platform", "Error", 0);
		}
	}
	if(vertices.find(start) != vertices.end() && vertices.find(end) != vertices.end){
		
		
		/*int n = adjList.size();
		std::vector<double>minDist;
		//std::vector<std::pair<LONG,LONG>>prev;
		minDist.resize(n, inf);
		minDist[startNodeID] = 0;
		//prev.resize(n, );
		std::set<std::pair<double, std::pair<LONG,LONG>>>vertex_queue;
		vertex_queue.insert(std::make_pair(minDist[startNodeID], startNodeID));
		while(!vertex_queue.empty()){
			double dist = vertex_queue.begin()->first;
			int u = vertex_queue.begin()->second;
			vertex_queue.erase(vertex_queue.begin());
			auto its = adjList.equal_range(u);
			for (auto it = its.first; it != its.second; ++it) {
				int v = it->second.id;
				double weight = it->second.weight;
				double distance_through_u = pDist(vertices[u].x, vertices[u].y, vertices[v].x, vertices[v].y) + weight;
				add_log("distance_through_u: %f", distance_through_u);
				add_log("Vertex ID: %d X: %d Y: %d", vertices[u].id, vertices[u].x, vertices[u].y);
				if(distance_through_u < minDist[v]){
					vertex_queue.erase(std::make_pair(minDist[v], v));

					minDist[v] = distance_through_u;
					//prev[v] = u;
					vertex_queue.insert(std::make_pair(minDist[v], v));
				}
			}
		}
		/*int vertex = destNodeID;
		for ( ; vertex != -1; vertex = prev[vertex])
			add_log("Vertex ID: %d X: %d Y: %d ", vertices[vertex].id, vertices[vertex].x, vertices[vertex].y);*/
	}
}

The commented out code was what I used for another program, but couldn't adapt to this one.
Last edited on
markyrocks (346)
What exactly is the problem? I've looked at this a few times b4 I decided to comment but whatever it is you're doing here appears to be way more complicated than necessary. Just save all the necessary information in one created struct and then push it into a vector<struct> . Its hard for me to wrap my mind around how you even pull it back out. vedges[i].first.first .... madness.


? I have no clue, bc I've never used pairs inside of pairs, I think thats what you're trying to do at least. I have no idea if that's even possible.

Edit, yep that was wrong

Maybe try something like this..

 
 
vedges.insert({std::make_pair(eStartLeft.x1, eStartLeft.y1), eStartLeft});


Last edited on
dutch (2548)
markyrocks wrote:
I have no clue

True.
Last edited on
doug4 (1538)
If a Vertex already contains an x and a y, why are you std::mapping pair<x, y> to a Vertex? Why not just use a std::set<Vertex>? I don't see why you would be messing with std::pair<LONG,LONG> anywhere in your code. You should be passing Vertices around.

Why does vEdge contain x1,y1,x2 and y2? Why not just 2 vertices?

Why are you std::multimapping pair<X,Y> to vEdge? Why not multimap<Vertex, vEdge>? or better yet, use a multiset<vEdge> where you only consider the first vertex in your less operator.

You have so much clutter here, it's hard to see what's going on. Even you, who wrote it, have questions.

I would recommend getting rid of isLadder and jumptype for a while until you get the path finding algorithm working. And why do you have a distance and a weight? They seem to be related.
Last edited on
tigerking (3)
The reason my structure is so complicated is because I am reading platform data/rope data from memory and generating nodes/jump points through precalculation. This is created for a game and I have been using this as a reference: https://www.gamedev.net/articles/programming/artificial-intelligence/generalized-platformer-ai-pathfinding-r3924/
As I said before, I have already tried mapping by assigning an ID to vertex and accessing it's value through that, but that messes up my adjacency list because the way I grab platform data, each platform has an X1, Y1, X2, Y2, and when I move on to the next platform that is connected, it creates a new structure that has the same point as the previous platform, therefore unique id values will mess with that. Using the XY values as the key allows me to contain only unique Vertexes. I have already printed out the adjacency list/vertex list and they are accurate. I just need to find a way to implement Dijkstra's algorithm with a coordinate based structure. Trust me, I have already tried countless other methods and this is the most promising so far. The only question I have is how I can implement Dijkstra's with my current structures. I don't need further optimization. Also, the reason I have a distance and a weight is because I am assigning a higher weight to nodes that require a jump. Distance is simply the euclidean distance between two points that I am saving for the later part of the algorithm.

vedges is acting as my adjacency list which will represent how my character can move between two Vertex points btw.
Last edited on
tigerking (3)
I managed to get it implemented by going back after my vertexes are created and assigning an ID to them afterwards. However, now my loop is stuck in an infinite loop. Any idea why?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
void dijkstra(std::pair<LONG, LONG> start, std::pair<LONG, LONG> end){
	struct Vertex vStart;
	struct Vertex vEnd;
	if(vertices.find(start) == vertices.end()){
		try{
			Platforms* startPlat = *getPlatform(start.first, start.second);
			vStart = Vertex(start.first, start.second);
			vStart.id = 0;
			add_log("Start %d X: %d Y: %d", vStart.id, vStart.x, vStart.y);
			vertices.insert(std::make_pair(start, vStart));
			struct vEdge eStartLeft = vEdge(startPlat->x1, startPlat->y1, vStart.x, vStart.y, false, NONE, pDist(startPlat->x1, startPlat->y1, vStart.x, vStart.y), 1);
			struct vEdge eStartRight = vEdge(startPlat->x2, startPlat->y2, vStart.x, vStart.y, false, NONE, pDist(startPlat->x2, startPlat->y2, vStart.x, vStart.y), 1);
			vedges.insert(std::make_pair(std::make_pair(eStartLeft.x1, eStartLeft.y1), eStartLeft));
			vedges.insert(std::make_pair(std::make_pair(eStartRight.x1, eStartRight.y1), eStartRight));
			vedges.insert(std::make_pair(std::make_pair(eStartLeft.x2, eStartLeft.y2), eStartLeft));
			vedges.insert(std::make_pair(std::make_pair(eStartRight.x2, eStartRight.y2), eStartRight));
		}catch(...){
			MessageBoxA(NULL, "Couldn't find starting platform", "Error", 0);
		}
	}
	if(vertices.find(end) == vertices.end()){
		try{
			Platforms* endPlat = *getPlatform(end.first, end.second);
			vEnd = Vertex(end.first, end.second);
			vEnd.id = vertices.size();
			add_log("End %d X: %d Y: %d", vEnd.id, vEnd.x, vEnd.y);
			vertices.insert(std::make_pair(end, vEnd));
			struct vEdge eEndLeft = vEdge(endPlat->x1, endPlat->y1, vEnd.x, vEnd.y, false, NONE, pDist(endPlat->x1, endPlat->y1, vEnd.x, vEnd.y), 1);
			struct vEdge eEndRight = vEdge(endPlat->x2, endPlat->y2, vEnd.x, vEnd.y, false, NONE, pDist(endPlat->x2, endPlat->y2, vEnd.x, vEnd.y), 1);
			vedges.insert(std::make_pair(std::make_pair(eEndLeft.x1, eEndLeft.y1), eEndLeft));
			vedges.insert(std::make_pair(std::make_pair(eEndRight.x1, eEndRight.y1), eEndRight));
			vedges.insert(std::make_pair(std::make_pair(eEndLeft.x2, eEndLeft.y2), eEndLeft));
			vedges.insert(std::make_pair(std::make_pair(eEndRight.x2, eEndRight.y2), eEndRight));
		}catch(...){
			MessageBoxA(NULL, "Couldn't find ending platform", "Error", 0);
		}
	}
	
	if(vertices.find(start) != vertices.end() && vertices.find(end) != vertices.end()){
		std::vector<Vertex>vVec;
		vVec.resize(vertices.size());
		add_log("vVec size: %d", vertices.size());
		for(auto i:vertices){
			vVec[i.second.id] = i.second;
			//add_log("vertex id: %d x: %d y: %d", i.second.id, i.second.x, i.second.y);
		}
		for(auto j:vVec){
			add_log("vertex id: %d x: %d y: %d", j.id, j.x, j.y);
		}
		int n = vedges.size();
		std::vector<double>minDist;
		std::vector<int>prev;
		prev.resize(n, -1);
		minDist.resize(n, inf);
		minDist[0] = 0;
		std::set<std::pair<double, int>>vertex_queue;
		vertex_queue.insert(std::make_pair(minDist[0], 0));
		while(!vertex_queue.empty()){
			double dist = vertex_queue.begin()->first;
			int u = vertex_queue.begin()->second;
			auto its = vedges.equal_range(std::make_pair(vVec[u].x, vVec[u].y));
			for (auto it = its.first; it != its.second; ++it) {
				int v;
				double weight;
				double distance_through_u;
				if(it->second.x1 == vVec[u].x && it->second.y1 == vVec[u].y){
					v = vertices.at(std::make_pair(it->second.x2, it->second.y2)).id;
					weight = it->second.weight;
					distance_through_u = it->second.dist + weight;
				}else if(it->second.x2 == vVec[u].x && it->second.y2 == vVec[u].y){
					v = vertices.at(std::make_pair(it->second.x1, it->second.y1)).id;
					weight = it->second.weight;
					distance_through_u = it->second.dist + weight;
				}
				add_log("distance_through_u: %f", distance_through_u);
				add_log("Vertex ID: %d X: %d Y: %d", vVec[v].id, vVec[v].x, vVec[v].y);
				if(distance_through_u < minDist[v]){
					vertex_queue.erase(std::make_pair(minDist[v], v));
					minDist[v] = distance_through_u;
					prev[v] = u;
					vertex_queue.insert(std::make_pair(minDist[v], v));
				}
			}
		}
	}
}
Topic archived. No new replies allowed.