Quote:

forward flood-fill with constrained horizon.

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

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?

I do an insertion-sort. That is, the node is always inserted into the correct spot in the list in the first place.

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 openlistSortOpenList

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

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.

Here share with all of you another AI example that using A* Algo in solving 8-Puzzle problem:

http://silyeek-tech.blogspot.com/2006/03/ai-8-puzzle-solver.html