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

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. :)

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.

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?

Notice the struct above: The states are UNVISITED, OPEN, and CLOSED. :)

In this image, orange represents a closed node.

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?

I'm marking nodes; not keeping a list. I don't see what's hard to understand about that...

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?

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.