Archived

This topic is now archived and is closed to further replies.

A* - Searching all over hell to find a straight line path

This topic is 4941 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

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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Didn''t check the code but my guess as for the path.

Did you take into account that diagonal movement is longer than a straight line ? ie sqrt(2) instead of 1 ? If not, it definately found one (of them many) shortest path.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest 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. 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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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



Share this post


Link to post
Share on other sites
Guest Anonymous Poster
How do you quickly find nodes in the subtree?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
quote:
Original post by Samith
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.



Err, no, I don't believe I was saying that... but then I'm not sure what you're saying here... so I can't be certain that I wasn't saying what I think you thought I was saying. Confused? I am!



Anyway...

What I was saying was that assume you are expanding child nodes from your current node and it happens that one of these new nodes already appears in your closed list. This is a common problem with searches on regular grids/lattices. You've computed the path cost of that child node through its parent and find that this is a lower cost for that node than the path cost listed for that node in the closed list. This can happen because these two instances of the same node have different parents, representing different paths to this node. You need to decide which path to keep. Obviously you go with the path with the lower of the two costs. IF that happens to be the new node you generated, you need to look at the subtree below the node that is in the closed list, because you're about to tell that entire subtree that to get to the subtree, you need to go through a different parent node (the parent of the newly generated node, not the old one in the closed list). Since getting to the current node costs less than getting to the node in the closed list, then all the costs in the subtree below the old node need to be updated... AND, you need to tell each of the children of the old node that their parent is now the new node. This operation is called splicing. Essentially you've disconnected the subtree from the old node, stuck it under the new node, updated the subtree costs and deleted the old node (because we don't need it any more).

I hope this makes sense.

Cheers,

Timkin

[edited by - Timkin on June 2, 2004 3:31:24 AM]

Share this post


Link to post
Share on other sites
Timkin; I agree with you on the expense, but most implementations of A* I have seen don''t maintain the information you would need to do this.

Most implementations I have looked at have a pointer from a node to the parent. To propagate the costs as you are suggesting, wouldn''t the parent need to also have a pointer to all of its children?

Do you have any references to implementations that do this? I am very curious about the complexity difference. I believe most of the AI Gem implementations just reopen the node.

Share this post


Link to post
Share on other sites
Timkin: That is what I was saying, pretty much. I think we''re mixing terminologies and implementations though. In my implementation, the nodes don''t exactly have children, the "children" I guess are just all the nodes adjacent to it. There is no real tree structure. Each node does, however, have a parent, which is a node adjacent to it with the lowest g cost.

So in my old implementation, when you were searching through all the neighbors of a node, one of them, obviously, has to be in the closed list, this would most likely be the node you searched previous to the current node, so it would be the parent. Now in the old implementation, I would skip nodes in the closed list and only update the g cost of a node in the open list. In the new implementation, after taking your advice, I made the program also update the g cost of nodes in the closed list.

It''s kind of hard for me to explain since I''m not really used to the terminology, but whatever I''m doing, it''s working and it''s working well, and I''m doing it the way I am because of what you said.

Share this post


Link to post
Share on other sites
quote:
Original post by BrianL
Timkin; I agree with you on the expense, but most implementations of A* I have seen don''t maintain the information you would need to do this.

Most implementations I have looked at have a pointer from a node to the parent. To propagate the costs as you are suggesting, wouldn''t the parent need to also have a pointer to all of its children?



Whether you explicitly realise it or not the tree structure is there... ask yourself how do you generate the successor nodes of any given node in the first place, when you want to work out which nodes to open? The search space, which is a tree structure, is defined by the set of actions that can be executed in each node (the transitions) which define the directed edges between nodes. So, no matter how you represent it, the tree is there, even if you don''t explicity store a set of pointers to child (successor/neighbour) nodes. You MUST have a function that identifies successor nodes from any given node. If you have a tree, you know whether the node is open or closed by whether it is a branch or leaf node. If you don''t represent the tree with pointers (but generate successors via a function applied to the node) then you store within the node whether it is open or closed or never seen before (which is actually more information). Clearly you could apply this successor-identifying function to all neighbouring nodes (successors of the current node) to find the subtree, adjusting the costs as you go.

As for implementations that use this... plenty... I have code of my own that does this... and indeed, most implementations of search I have looked at throughout my career have started with the premise of a search tree data structure, or a graph structure of some form (for example, when implementing Dijkstra''s algorithm). There is a tradeoff between the extra memory required to store the tree and the extra computation it takes to generate subtrees whenever you have to perform splicing... but the memory method wins out, since we''re only storing pointers and that''s trivial.

Samith, we are talking about the same thing... it''s just that internal representations are probably different between our methodologies... which can lead to confusion... sorry if I contributed to this in any way. I''m very glad to hear that your search is working properly!

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Thank you for pointing out my blindness there. You are right; getting the children of the node is trivial. I wasn't thinking about the search space when you mentioned the splice; I was thinking about the node structure storing the shortest path through back pointers.

Very good explaination, thank you!

[edited by - BrianL on June 2, 2004 11:43:51 PM]

Share this post


Link to post
Share on other sites