For the checking of nodes, couldn't you use a binary search tree for that?

You go and insert each node, into the bst, (at o(log2 n) time), and when searching for a node, you simply look at the bst, and find the node, in o(log2 n) time.

That would be mighty fast, and mighty easy to make.

A link

For the actual Que (the open list).
Thats a hard one.

You basically looking for the minimum, in a list.

What you could do, is you have a vector of a struct.
In that struct, you have a pointer to a node, and a value.

Now, when you update a node, you go and shove all of its sucessors onto the End of the vector.

You then search the vector, from the end to the beginning. And then compare and pick, until you find the minimum one.

This is better then the sort and pick, which averages o(n log2 n).
This would be o(n) Which is very useful.

There should be a better way.

You could make up a binary tree, and as your going, you insert each and every node that you have into it.

Its then only o(log2 n) retrieval, and o(log2 n) insertion. So it'd be pretty fast.

And as an added bonus, you could check if a node is already there, as you insert it. So that there are no circular paths.

From,
Nice coder

I expect that sorted insertions into a list can be done reasonably efficiently with a simple linked list. In theory every insertion is going to be O(N), but in practice you have a lot of coherence from one insertion to the next and you can take advantage of this.

eg. In a grid-based game, 1 node examined has 8 neighbours to put on the open list. They will tend to have very similar values due to their proximity. So you can cut down the amount of open list you have to search through by starting from the insert position of the last node, instead of the start of the list.

The simplicity of implementing this may turn out to give you significant benefits compared to using a tree.