• Advertisement
Sign in to follow this  

A* graphical heuristic examples

This topic is 4187 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 wrote - or, rather, re-wrote - my A* implementation today. Actually wrote it from scratch in just about 4 hours. To speed it up, I built the open list right into the node structure. I never have to search for the best open node; I needn't check a list of closed nodes. In fact, for a small search space, all the scratch space fits in my cache. In these images, a red square is an obstacle, a blue square is the path, and a green square is one that was searched. With a heuristic of 0 - A max-delta heuristic - max( delta_x, delta_y ) Manhatten distance - delta_x + delta_y

Share this post


Link to post
Share on other sites
Advertisement
Quote:
To speed it up, I built the open list right into the node structure.


How do you mean?

Node {
graph_children
heap_children <- internalized open list as a min-heap ??
}

Something like that? But I don't see how that would mean you don't have to check the closed list (unless you require a consistent heuristic?), so I'm confused...

Btw, that graphical representation is nice. :)

Share this post


Link to post
Share on other sites
Actually it's

struct path_grid_node
{
unsigned int state;
unsigned int cost;
unsigned int estimated_final_cost;
unsigned int direction;
unsigned int next_open_node;
};


I used a simple linked list for the open-list, and don't have a closed list at all. I may change it to a tree; I'd have to test and see if the speed up in insertion time justifies the extra memory.

Share this post


Link to post
Share on other sites
If you don't have an explicit closed list, how are you generating a valid list of successor nodes? Are you just revisiting old states and relying on the higher cost to eliminate them?

Share this post


Link to post
Share on other sites
Notice the struct above: The states are UNVISITED, OPEN, and CLOSED. :)

Share this post


Link to post
Share on other sites
In this image, orange represents a closed node.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
Notice the struct above: The states are UNVISITED, OPEN, and CLOSED. :)


That doesn't answer the question though. Are you pregenerating one node per map location (assuming that there is no relevant state except the location you're in), allowing you to just check the 8 neighbours directly?

Share this post


Link to post
Share on other sites
I'm marking nodes; not keeping a list. I don't see what's hard to understand about that...

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
I'm marking nodes; not keeping a list. I don't see what's hard to understand about that...


He understands that, but that doesnt answer his question. If you dont keep an open/close list, do you parse your whole data structure of nodes to find the next successor?

Share this post


Link to post
Share on other sites
I have an open list.

I don't need a closed list because finding a given node is nothing more than a pointer addition, then I can check it's state.

Share this post


Link to post
Share on other sites
Ok, so you 'find' successor nodes, not 'create' them. Therefore, their structure is pregenerated, presumably in a one-to-one correspondence with the map grid. Right?

Share this post


Link to post
Share on other sites
Thats suitable for a very small grid... both in terms of memory and cpu. The implementation will always have a n iterations loop, where n is the total number of possibles nodes, because you have to reset all those nodes each time you call the pathfinder. memset aint free :P

Share this post


Link to post
Share on other sites
Indeed not, but memset is damn fast. I avoided initializing each node every time. Nodes are only initialized when they are first opened, so, only those nodes that actually need be searched to find the path are initialized.

I've tested it with grids up to 512 * 512, and the running time seems to be a function of the length of the path, not of the size of the grid. That is, a path of length 200 was found in the same amount of time on a 256*256 grid as on the 512*512. There is more inialization overhead - you guessed it right; it's in a call to memset. :)

Share this post


Link to post
Share on other sites
I'm using a similar approach, that is:
- 2D-array of nodes
- node contains state used in searching
- during search, dirtied (opened) nodes are pushed on a vector, and cleared afterwards (the idea was taken from TA Spring)
- homebrew, adaptable binary heap is used as a priority queue

But I didn't really checked if the no-allocation boost is a worth gain. It "seems" so...

Quote:
Original post by Deyja
I've tested it with grids up to 512 * 512, and the running time seems to be a function of the length of the path, not of the size of the grid. That is, a path of length 200 was found in the same amount of time on a 256*256 grid as on the 512*512.


Test with more complicated obstacles - the proportion may suddenly change to squared (if not using some more complicated heuristic).

Share this post


Link to post
Share on other sites
Except in extreme cases (such as the big unbroken wall example often batted about) it runs pretty much the same. Oddly enough, if I penalize turning (to get it to generate straighter paths) it suddenly explores many more paths, and the complexity explodes!

In this graphic, orange is a closed node. The numbers are the cost of the path to that node (Not the estimated final cost; the 'cost so far'). This is almost the worst case I can demonstrate using my tile engine to visualize it.

Share this post


Link to post
Share on other sites
Quote:
during search, dirtied (opened) nodes are pushed on a vector, and cleared afterwards (the idea was taken from TA Spring)

This is how I originally did it. This time, I built the open list directly into the node structure. This ultimatly required me to have 1 more node than you'd expect, and start indexing at 1, not 0. Node 0 represents the root of the open list. I also always put the new open node before other nodes of the same cost already in the list. This gives it a bit of momentum, and means it tends to explore promising paths completely before exploring others.

Share this post


Link to post
Share on other sites
Hum. Could explain one more thing?
On this image, it seems to me, that, with your implementation, every node I marked with the red rectangle (except yellow ones) will have exactly the same estimated_final_cost (current cost + heuristic). How is it then, that so little nodes are being opened in the process?

deyja Astar - rect

Are there some additional penalties? Or is it just coincidence (for example, your implenetation of 'list of nodes' always pushes from the back, thus favouring nodes being already on the list)?
EDIT: Blah, I meant the other way around... Thanks for the explanation above.

Share this post


Link to post
Share on other sites
I assume my post right above answered your question?

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
I assume my post right above answered your question?


Yup, it did. Thanks.

Share this post


Link to post
Share on other sites
As with any pathfinding implementation, there is a distinct tradeoff between online computation required and information stored (obtained by either pre-computation or designed). The method presented (which, given I read the OPs posts correctly, I've seen several times before) is a forward flood-fill with constrained horizon. It shows how algorithms may be optimised to a given domain type. Such methods are only applicable to small grids on closed manifolds. That's not to say, of course, that such domains don't pop up regularly in game design problems. ;)

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Quote:
forward flood-fill with constrained horizon.


That would be an adequate description of the A* algorithm, yes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
Actually it's

struct path_grid_node
{
unsigned int state;
unsigned int cost;
unsigned int estimated_final_cost;
unsigned int direction;
unsigned int next_open_node;
};


I used a simple linked list for the open-list, and don't have a closed list at all. I may change it to a tree; I'd have to test and see if the speed up in insertion time justifies the extra memory.


I'm fairly new at pathfinding, but the only way I've seen it done is with a priority queue. Do you have to sort the linked list everytime a node is added to makes sure the correct value is as the front or do you just search for the lowest cost node when it is needed?

Share this post


Link to post
Share on other sites
I do an insertion-sort. That is, the node is always inserted into the correct spot in the list in the first place.

Share this post


Link to post
Share on other sites
I use sorting, but will change to insertion sort soon.

When using sorting: Don't sort the list after each node insertion.
Do it after the entire current node's links has been added.


for (all neighbours)
Calc costs and add to openlist.

Pop Current node from openlist
SortOpenList


I can't honestly say that sorting the list is that much of an issue anymore since people got a lot of horses under the PC-hood! :D

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
Quote:
forward flood-fill with constrained horizon.


That would be an adequate description of the A* algorithm, yes.


No, I don't believe so. A flood fill is a breadth first search of the node space. You can think of A* as a flood fill search in cost space (rather than node space) since it guarantees to expand all nodes within a given cost contour before expanding any node in a higher cost contour.

A forward flood-fill with constrained horizon is just that. Flood fill all nodes out to a limiting cost horizon, with ordering prefernce defined only by being adjacent to an already expanded node. A* is a search of adjacent nodes based on a cost ordering.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement