• Advertisement
Sign in to follow this  

A* graphical heuristic examples

This topic is 4280 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
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
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
Sign in to follow this  

  • Advertisement