I''ve never written any pathfinding stuff before, and I''m having some troubles with it. It compiles and runs and everything is good in that aspect, but when it''s searching for the paths, it really does some stupid searching. Below is a screenshot of it''s search for a straight line path: The green dot on the far left is the start, the red on the far right is the goal. There are no obstacles in this picture. The red component of the tiles represents their g value, and the blue component represents the h value. So the more pink areas in the top left and bottom left must mean that the algorithm searched, and then went looped back around over to those squares, decided it wasn''t a good idea, and looped back, eventually making it to the correct goal. You can also see that the path it chose isn''t exactly the shorteset path. Here is my path finding function:

void CPathfinder::FindPath()
{
	for(int i = 0; i < 25; i++)
	{
		for(int j = 0; j < 25; j++)
		{
			grid[i][j].movementCost = playSpace->grid[i][j].movementCost;
		}
	}

	topGVal = 0;
	topHVal = 0;

	int loopCount = 0;
	SNode node;
	node.coord = start;
	node.gVal = 0;
	node.hVal = hCost(node.coord, goal);
	node.fVal = node.gVal + node.hVal;
	node.inOpen = true;
	open.push_back(node);
	if(node.gVal > topGVal)
		topGVal = node.gVal;
	if(node.hVal > topHVal)
		topHVal = node.hVal;

	while(!open.empty())
	{
		std::cout << "Loop Count: " << loopCount << std::endl;
		GetFirst(open, node);
		grid[node.coord.x][node.coord.y].inOpen = false;
		visited.push_back(node);

		if(node.coord == goal)
		{
			std::cout << "Broke for goal." << std::endl;
			break;
		}

		// i is the direction

		for(int i = 0; i < 8; i++)
		{
			SNode node2 = Neighbor(node.coord, i);
			SNode *n2 = &grid[node2.coord.x][node2.coord.y];

			if(!Valid(node2.coord.x, node2.coord.y))
			{
				std::cout << "found invalid block" << std::endl;
				continue;
			}

			int mCost = gCost(node2.movementCost, i);
			node2.gVal = mCost + node.gVal;
			node2.hVal = hCost(node2.coord, goal);
			if(node2.gVal > topGVal)
				topGVal = node2.gVal;
			if(node2.hVal > topHVal)
				topHVal = node2.hVal;
			// hasn''t been visited

			if(!node2.beenVisited)
			{
				n2->beenVisited = true;
				n2->parent = &grid[node.coord.x][node.coord.y];
				n2->gVal = node2.gVal;
				n2->hVal = node2.hVal;
				n2->fVal = n2->gVal + n2->hVal;
				n2->inOpen = true;
				open.push_back(*n2);
				push_heap(open.begin(), open.end());
			}
			else
			{
				// it''s either in open or closed, if it''s in open, check to see if the gVal is lower with this path

				// else if it''s in closed then just ignore it, we don''t want to be looping around in circles

				if(node2.inOpen)
				{
					if(node2.gVal < n2->gVal)
					{
						n2->parent = &grid[node.coord.x][node.coord.y];
						n2->gVal = node2.gVal;
						std::vector<SNode>::iterator n2inOpen = FindInOpen(node2.coord);
						n2inOpen->gVal = n2->gVal;
						push_heap(open.begin(), n2inOpen+1, comparisonObj);
					}
				}
			}
		}
		loopCount++;
	}

	if(node.coord == goal)
	{
		CVector c = goal;
		while(c != start)
		{
			std::cout << "Workin on the path" << std::endl;
			path.push_back(c);
			if(grid[c.x][c.y].parent->coord == c)
				std::cout << "Parent points to self." << std::endl;
			c = grid[c.x][c.y].parent->coord;
			playSpace->grid[c.x][c.y].partofPath = true;
		}
		path.push_back(start);

		ColorCells(playSpace);
	}
	else
	{
		std::cout << "No valid path found." << std::endl;
		ColorCells(playSpace);
	}
}

Sorry about some of that extremely ugly code in there.

I didn''t peruse the code too closely, but it seems like that output could be reasonable given a strange enough movement cost map. Of course, I''m also color blind, so I may be misreading the output in your image. In any case, does your function still act funny even with a flat search space?

Too much of your code is missing for me to make an authoritative guess, but:

- does your node have an accurate comparison operator? In other words, is push_heap definitely giving you the correct ordering? You use ''comparisonObj'' when you call it in the else clause but not in the if clause, so I''m guessing that''s one prime source of error.

If that''s not all...

- is movementCost always greater than zero for every position?

- what does gCost do? In particular, why can''t you just use ''node2.gVal = node.gVal + node2.movementCost'' ?

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Here''s your problem... (or at least, the major problem your code has

quote:Original post by Samith
// it''s either in open or closed, if it''s in open, check to see if the gVal is lower with this path
// else if it''s in closed then just ignore it, we don''t want to be looping around in circles

If you generate a child node that happens to already be in your closed list you CANNOT ignore the newly generated node. You MUST compare the cost of this node with the cost of the node in the closed list (actually its sufficient to compare just their ''g'' costs). If you find that the newly generated node (path to the node) has a lower cost then you have to splice it into the tree structure AND propogate the effect of the new, cheaper cost to that node to the ENTIRE SUBTREE below the node that was in the closed list.

If you fail to do this you will not correctly explore the contours of the cost function. A* will expand every node within a given cost contour BEFORE expanding any node in the next highest contour. Thus, if you haven''t represented the cost contours in your search tree correctly, you cannot expect your tree to grow correctly.

Cheers,

Timkin

When a cheaper path is found to a node that is already on the closed list, it is enough to update its cost, take it off the closed list, and put it on the open list. Propagation of this new value down the tree will occur automatically as A* finds new paths through this node to the nodes that it leads to.

Ok, great advice from everyone here. Thanks a lot!

Timkin: If I'm following you correctly, you are telling me I need to check all neighboring nodes to see if their g costs are lower, otherwise it won't find the fastest path. Now that I think about it, you're completely right.

xMcBaiNx: Yep, moving diagonal costs 14, moving straight costs 10.

Kylotan: gCost does this: "return (4 * (dir%2) + 10)*mCost" That way if it's a diagonal move the cost is 14*mCost and straight is only 10*mCost. About the comparisonObj, doh! That was a really stupid error, thanks for pointing that out.

SiCrane: What's a flat search space?

Anyway, thanks to all your help I got it to work. Now it finds the shortest path and it doesn't wander all over the place to find it! But one thing is still kind of odd, right now the heuristic guess takes into account diagonal moves, but if I change it to just be 10*deltaX + 10*deltaY, the search suddenly starts searching all over the place. I don't know why this is. Anyway, thanks a ton for the help guys.

EDIT: Here's a nice screenshot of the program working great:

Kind of a bland map, but hey, at least it works, and it works well!

[edited by - Samith on June 1, 2004 5:03:50 PM]

quote:Original post by Anonymous Poster
When a cheaper path is found to a node that is already on the closed list, it is enough to update its cost, take it off the closed list, and put it on the open list.

...and what if that node happens to be your root node, or some other node that is high up the tree. This is an absurdly inefficient proposal. The computational cost to update the subtree costs is trivial compared to re-exploring the entire subtree, since all that is required is the addition or subtraction of the difference in costs at the root of the subtree from all nodes within the subtree below that node... an operation that is of O(n), where n is the number of nodes in the subtree. At best, A* will perform the re-exploration in O(nlog(n)) time. That''s a BIG difference in performance.

Timkin

How do you quickly find nodes in the subtree?

quote:Original post by Anonymous Poster
How do you quickly find nodes in the subtree?

I take it this is a joke, right?

You have a tree structure (that''s what you''re searching!)...
You recurse down the subtree and update the costs...

Timkin