C++

Forum

 
priority_queue maximum size???

sunsflower (23)
I have a A* search as this:

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
 
void apply_astar(const vec2 & src, const vec2 & tar)
{
	clear_res();
	reset_vertex();

	GraphVertex* srcvert = query_vertex(src, 5);
	GraphVertex* tarvert = query_vertex(tar, 5);
	GLFASSERT(srcvert != nullptr && tarvert != nullptr);

	priority_queue <GraphVertex*, vector<GraphVertex*>, SearchCmpAstar> frontier;

	srcvert->_cost_to_this = 0;
	srcvert->_cost_to_goal_bypass = (int)glfMath::dist(srcvert->_Pos, tarvert->_Pos);

	frontier.push(srcvert);

	while (!frontier.empty())
	{
		GraphVertex* nextvert = frontier.top();
		frontier.pop();

		if (nextvert->_Index == tarvert->_Index)
		{
			while (nextvert)
			{
				_result.push_back(nextvert);
				nextvert = nextvert->_prev;
			}
			return;
		}

		nextvert->_frontier = false;
		nextvert->_explored = true;

		for (int i = 0; i < nextvert->_Neighbors.size(); i++)
		{
			if (nextvert->_Neighbors[i]->_explored == false)
			{
				int gscore = nextvert->_Dists[i] + nextvert->_cost_to_this;
				int hscore = (int)glfMath::dist(nextvert->_Neighbors[i]->_Pos, tarvert->_Pos);

				if (nextvert->_Neighbors[i]->_frontier == false)
				{
					nextvert->_Neighbors[i]->_frontier = true;
					nextvert->_Neighbors[i]->_cost_to_this = gscore;
					nextvert->_Neighbors[i]->_prev = nextvert;
					nextvert->_Neighbors[i]->_cost_to_goal_bypass = gscore + hscore;

					/* why the fuck this must be after three lines above?!! fuck?!! */
					frontier.push(nextvert->_Neighbors[i]);
				}
				else if (gscore < nextvert->_Neighbors[i]->_cost_to_this)
				{
					nextvert->_Neighbors[i]->_cost_to_this = gscore;
					nextvert->_Neighbors[i]->_prev = nextvert;
					nextvert->_Neighbors[i]->_cost_to_goal_bypass = gscore + hscore;
				}
			}
		}
	}


	cout << "A star search failed!\n";
}

it takes two position on screen coordinate and translate them to graph nodes. With in a certain distance of the searching path it works ok. But when the earching path is more than that limit(I dont know how much), an exception is throwed at frontier.pop() with message "invalid heap". Why this is happening? thanks!
Last edited on
sunsflower (23)
is it that I change the value of object those pointers in priority queue pointing to, so the heap becomes invalid(because it use this value to sort)?
coder777 (8444)
The underlying vector does not have a limit. You will rather have an infinite loop or you are accessing an invalid pointer.
sunsflower (23)
I've checked the pointer and they are all valid even when exception is thrown...not infinite loop too, because exception is thrown only after 8 or 9 times loop..Thanks anyway
Topic archived. No new replies allowed.