C++

Forum

 
 
Code Not Tracing Back Through Parents

Mayday556 (8)
I have been working on A* path-finding for a couple days now trying to make it work. I have everything working as it should, except for the part where it goes through the parent of the current node, repeatedly doing this until it gets back to the source. (For those of you who do not know how A* path-finding works, this article here explains quite a bit: http://www.policyalmanac.org/games/aStarTutorial.htm) The parents are being accessed just fine, it is just that they aren't being stored correctly. Why aren't I able to store the parents of these nodes properly.

The Console is supposed to output the path from the source to the destination, it starts at the destination like it is supposed to, but for some reason it doesn't make it all the way back to the source, like so:

P = player
Z = zombie (The pathfinder)
- = path

 
 
'P-------   Z'


However, it should be displaying as so:

 
 
'P----------Z'


It seems that the parents aren't being stored correctly after a couple loops. After debugging it and tracing the parents of a node as far back as possible, it says that the parents data equals `???` or `0xfeeefeee` or just `NULL`. Why is this?
Last edited on
coder777 (8444)
Please post the code here. And don't forget to use code tags: [code]Your code[/code]

Your problem is that you use pointer to an element of a vector. When modifing a vector it is not guaranteed that the pointer references a valid object.

Read this:

http://www.cplusplus.com/reference/vector/vector/push_back/

If a reallocation happens, all iterators, pointers and references related to the container are invalidated.


better use a list for your purpose
ne555 (10692)
> better use a list for your purpose
store the index, or reserve enough space.
Mayday556 (8)
Sorry, I couldn't post all of the code here due to it being too long (over 9000 chars). Thanks so much ne555 and coder777 for helping to solve this problem. I will try these solutions out to see if they work.
closed account (N36fSL3A)
Post the code in two posts.
Mayday556 (8)
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
//////////
//main.cpp
//////////

#include <vector>
#include <iostream>
#include "AStarNode.h"

bool IsOnList(int xPos, int yPos, std::vector<AStarNode>& list);
std::vector<AStarNode>::iterator FindLowestFCost(std::vector<AStarNode>& open);
void PathFind(int xPos, int yPos, int xDest, int yDest, char* map);
char GetCharOnMap(int xPos, int yPos, char* map);

int main()
{
	char map[10 * 10 + 1];

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			map[j * 10 + i] = ' ';
		}
	}

	PathFind(9, 9s, 0, 0, map);

	map[yPos * 10 + xPos] = 'Z';

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			std::cout << map[j * 10 + i];
		}
		std::cout << std::endl;
	}

	std::cin.get();

	return 0;
}

char GetCharOnMap(int xPos, int yPos, char* map)
{
	if (xPos >= 10 || yPos >= 10 || xPos < 0 || yPos < 0)
		return NULL;
	else
		return map[yPos * 10 + xPos];
}

bool IsOnList(int xPos, int yPos, std::vector<AStarNode>& list)
{
	for (std::vector<AStarNode>::iterator i = list.begin(); i != list.end(); i++)
	{
		if (xPos == i->mXPos && yPos == i->mYPos)
			return true;
	}
	return false;
}


std::vector<AStarNode>::iterator FindLowestFCost(std::vector<AStarNode>& open)
{
	std::vector<AStarNode>::iterator lowest = open.begin();

	for (std::vector<AStarNode>::iterator i = open.begin(); i != open.end(); i++)
	{
		if (i->mFCost < lowest->mFCost)
			lowest = i;
	}

	return lowest;
}

void PathFind(int xPos, int yPos, int xDest, int yDest, char* map)
{
	std::vector<AStarNode> open;
	std::vector<AStarNode> closed;
	std::vector<AStarNode> path;
	std::vector<AStarNode>::iterator current;
	int xDirections[4] = { 0, 0, 1, -1 };
	int yDirections[4] = { 1, -1, 0, 0 };

	open.push_back(AStarNode(xPos, yPos));
	open.begin()->CalculateH(xDest, yDest);
	open.begin()->CalculateFCost();

	while (true)
	{
		current = FindLowestFCost(open);

		closed.push_back(*current);
		open.erase(current);
		current = closed.end() - 1;

		//std::cout << &(*current) << std::endl; //Prove that it is not being stored properly

		//Check adjacent squares
		for (int i = 0; i < (sizeof xDirections / sizeof xDirections[0]); i++)
		{
			char node = GetCharOnMap(current->mXPos + xDirections[i], current->mYPos + yDirections[i], map);
			if (node == '|' || node == NULL || IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], closed) ||
				IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], open)) //If it is on the closed or open list
			{
			}
			else if (!IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], open))
			{
				open.push_back(AStarNode(current->mXPos + xDirections[i], current->mYPos + yDirections[i], &(*current)));
				open.back().CalculateH(xDest, yDest);
				open.back().CalculateFCost();
			}
		}

		if (IsOnList(xDest, yDest, closed) || open.size() == 0) //Check to see if we should stop pathfinding
			break;
	}

	if (IsOnList(xDest, yDest, closed)) //If the destination is on the closed list
	{
		path.push_back(closed.back()); //Start from our destination and work backwards

		while (true) //THIS IS WHERE THE PROBLEM IS
		{
			if (path.back().mXPos != xPos && path.back().mYPos != yPos && std::find(closed.begin(), closed.end(), *(path.back().mParent)) != closed.end())
			{
				path.push_back(*(std::find(closed.begin(), closed.end(), *(path.back().mParent)))); //For some reason it isn't tracing all the way back to us
			}
			else
				break;
		} //THIS IS WHERE THE PROBLEM ENDS

		/*for (std::vector<AStarNode>::const_iterator i = closed.begin(); i != closed.end(); i++) //Displays the closed list
		map[i->mYPos * 10 + i->mXPos] = i->mParentDir;*/

		for (std::vector<AStarNode>::const_iterator i = path.begin(); i != path.end(); i++) //Display the path
			map[i->mYPos * 10 + i->mXPos] = i->mParentDir;
	}
}

//////////////
//END main.cpp
//////////////

/////////////
//AStarNode.h
/////////////

#pragma once

#include <iostream>

class AStarNode
{
public:
	AStarNode(int xPos, int yPos, AStarNode * parent = nullptr);
	void CalculateH(int xDest, int yDest);
	void CalculateFCost();
	bool operator==(const AStarNode& rhs) const;
	bool operator!=(const AStarNode& rhs) const;

private:
	void CalculateG();

public:
	AStarNode * mParent;
	char mParentDir; //Displays a symbol pointing to the parent
	int mXPos;
	int mYPos;
	int mH;
	int mG;
	int mFCost;
};

AStarNode::AStarNode(int xPos, int yPos, AStarNode * parent) :
mXPos(xPos),
mYPos(yPos),
mParent(parent),
mH(0)
{
	CalculateG();
	if (mParent != nullptr)
	{
		if (mParent->mXPos > mXPos)
			mParentDir = '<';
		else if (mParent->mXPos < mXPos)
			mParentDir = '>';
		else if (mParent->mYPos > mYPos)
			mParentDir = '^';
		else if (mParent->mYPos < mYPos)
			mParentDir = 'V';
	}
	else
		mParentDir = '|';
}

void AStarNode::CalculateH(int xDest, int yDest)
{
	int horizontal = abs(mXPos - xDest);
	int vertical = abs(mYPos - yDest);
	mH = horizontal + vertical;
}

void AStarNode::CalculateG()
{
	if (mParent != nullptr)
		mG = mParent->mG + 1;
	else
		mG = 0;
}

void AStarNode::CalculateFCost()
{
	mFCost = mG + mH;
}

bool AStarNode::operator==(const AStarNode& rhs) const
{
	if (this->mXPos == rhs.mXPos && this->mYPos == rhs.mYPos)
		return true;
	else
		return false;
}

bool AStarNode::operator!=(const AStarNode& rhs) const
{
	if (this->mXPos == rhs.mXPos && this->mYPos == rhs.mYPos)
		return false;
	else
		return true;
}

/////////////////
//END AStarNode.h
/////////////////
Last edited on
coder777 (8444)
again: the crash occurs due to line 109: You set a pointer to an object that might or might not be valid later
Mayday556 (8)
While switching to using indexes, yet another error occurs. It still isn't tracing the parents back all of the way:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
 
//MAIN.CPP
#include <vector>
#include <iostream>
#include "AStarNode.h"

bool IsOnList(int xPos, int yPos, std::vector<AStarNode>& list);
std::vector<AStarNode>::iterator FindLowestFCost(std::vector<AStarNode>& open);
void PathFind(int xPos, int yPos, int xDest, int yDest, char* map);
char GetCharOnMap(int xPos, int yPos, char* map);

int main()
{
	char map[10 * 10 + 1];
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			map[j * 10 + i] = ' ';
		}
	}

	PathFind(9, 9, 0, 0, map);

	map[yPos * 10 + xPos] = 'Z';

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			std::cout << map[j * 10 + i];
		}
		std::cout << std::endl;
	}

	std::cin.get();

	return 0;
}

char GetCharOnMap(int xPos, int yPos, char* map)
{
	if (xPos >= 10 || yPos >= 10 || xPos < 0 || yPos < 0)
		return NULL;
	else
		return map[yPos * 10 + xPos];
}

bool IsOnList(int xPos, int yPos, std::vector<AStarNode>& list)
{
	for (std::vector<AStarNode>::iterator i = list.begin(); i != list.end(); i++)
	{
		if (xPos == i->mXPos && yPos == i->mYPos)
			return true;
	}
	return false;
}


std::vector<AStarNode>::iterator FindLowestFCost(std::vector<AStarNode>& open)
{
	std::vector<AStarNode>::iterator lowest = open.begin();

	for (std::vector<AStarNode>::iterator i = open.begin(); i != open.end(); i++)
	{
		if (i->mFCost < lowest->mFCost)
			lowest = i;
	}

	return lowest;
}

void PathFind(int xPos, int yPos, int xDest, int yDest, char* map)
{
	std::vector<AStarNode> open;
	std::vector<AStarNode> path;
	std::vector<AStarNode>::iterator current;
	int index = 0;
	int xDirections[4] = { 0, 0, 1, -1 };
	int yDirections[4] = { 1, -1, 0, 0 };

	open.push_back(AStarNode(xPos, yPos));
	open.begin()->CalculateH(xDest, yDest);
	open.begin()->CalculateFCost();

	while (true)
	{
		current = FindLowestFCost(open);

		AStarNode::closed.push_back(*current);
		open.erase(current);
		current = AStarNode::closed.end() - 1;

		//Check adjacent squares
		for (int i = 0; i < (sizeof xDirections / sizeof xDirections[0]); i++)
		{
			char node = GetCharOnMap(current->mXPos + xDirections[i], current->mYPos + yDirections[i], map);
			if (node == '|' || node == NULL || IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], AStarNode::closed) ||
				IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], open)) //If it is on the closed or open list
			{
			}
			else if (!IsOnList(current->mXPos + xDirections[i], current->mYPos + yDirections[i], open))
			{
				open.push_back(AStarNode(current->mXPos + xDirections[i], current->mYPos + yDirections[i], index));
				open.back().CalculateH(xDest, yDest);
				open.back().CalculateFCost();
			}
		}

		if (IsOnList(xDest, yDest, AStarNode::closed) || open.size() == 0) //Check to see if we should stop pathfinding
			break;
		++index;
	}


	if (IsOnList(xDest, yDest, AStarNode::closed)) //If the destination is on the closed list
	{
		path.push_back(AStarNode::closed.back()); //Start from our destination and work backwards

		while (true) //THIS IS WHERE THE PROBLEM IS
		{
			if (path.back().mXPos != xPos && path.back().mYPos != yPos && std::find(AStarNode::closed.begin(), AStarNode::closed.end(), *(AStarNode::closed.begin() + path.back().mParentIndex)) != AStarNode::closed.end())
			{
				path.push_back(*(std::find(AStarNode::closed.begin(), AStarNode::closed.end(), *(AStarNode::closed.begin() + path.back().mParentIndex)))); //For some reason it isn't tracing all the way back to us
			}
			else
				break;
		} //THIS IS WHERE THE PROBLEM ENDS

		/*for (std::vector<AStarNode>::const_iterator i = closed.begin(); i != closed.end(); i++) //Displays the closed list
		map[i->mYPos * 10 + i->mXPos] = i->mParentDir;*/

		for (std::vector<AStarNode>::const_iterator i = path.begin(); i != path.end(); i++) //Display the path
			map[i->mYPos * 10 + i->mXPos] = i->mParentDir;
	}
}

//ASTARNODE.H

#pragma once

#include <iostream>

class AStarNode
{
public:
	AStarNode(int xPos, int yPos, int index = 0);
	void CalculateH(int xDest, int yDest);
	void CalculateFCost();
	bool operator==(const AStarNode& rhs) const;
	bool operator!=(const AStarNode& rhs) const;

private:
	void CalculateG();

public:
	static std::vector<AStarNode> closed;
	int mParentIndex; //The index in which the parent is at in a Vector/Array
	char mParentDir; //Displays a symbol pointing to the parent
	int mXPos;
	int mYPos;
	int mH;
	int mG;
	int mFCost;
};

std::vector<AStarNode> AStarNode::closed;

AStarNode::AStarNode(int xPos, int yPos, int index) :
mXPos(xPos),
mYPos(yPos),
mParentIndex(index),
mH(0)
{
	CalculateG();
	if (mParentIndex != 0)
	{
		std::vector<AStarNode>::iterator temp = closed.begin() + mParentIndex;
		if (temp->mXPos > mXPos)
			mParentDir = '<';
		else if (temp->mXPos < mXPos)
			mParentDir = '>';
		else if (temp->mYPos > mYPos)
			mParentDir = '^';
		else if (temp->mYPos < mYPos)
			mParentDir = 'V';
	}
	else
		mParentDir = '|';
}

void AStarNode::CalculateH(int xDest, int yDest)
{
	int horizontal = abs(mXPos - xDest);
	int vertical = abs(mYPos - yDest);
	mH = horizontal + vertical;
}

void AStarNode::CalculateG()
{
	if (mParentIndex != 0)
		mG = (closed.begin() + mParentIndex)->mG + 1;
	else
		mG = 0;
}

void AStarNode::CalculateFCost()
{
	mFCost = mG + mH;
}

bool AStarNode::operator==(const AStarNode& rhs) const
{
	if (this->mXPos == rhs.mXPos && this->mYPos == rhs.mYPos)
		return true;
	else
		return false;
}

bool AStarNode::operator!=(const AStarNode& rhs) const
{
	if (this->mXPos == rhs.mXPos && this->mYPos == rhs.mYPos)
		return false;
	else
		return true;
}
Mayday556 (8)
NEVERMIND, I have solved it. I just needed to change the default index to -1.
Topic archived. No new replies allowed.