The A* search algorithm implementation and the navigation grid (previously path grid) have been in the “astar” branch for quite a while… I’ve finally sorted things out and now they’ve been merged into master.
I don’t have any examples yet, but do note one thing – the A* implementation is a generic one, which means that it isn’t bound to any form; it works on a set of nodes, which it considers as fully abstract objects. In other words, it doesn’t care whether the nodes represent a grid, a node graph in a mathematical sense or, indeed, apples and oranges, long as there exists a cost function between two different nodes.
Both the cost and the heuristic (predicted cost, which must be optimistic – that is, lower or equal to the actual cost – in order for the algorithm to work correctly) are passed in as callbacks, which means that the user can provide whatever he wants for the cost. Furthermore, checking whether a node is the goal is also performed via a function, so one can, for example, have multiple goals.
That said, if the user doesn’t provide such functions, the algorithm tries to use decent predictions – the cost between two nodes is assumed to be 1, and the heuristic is assumed to be 0, essentially making this a breadth-first search. Why 0? This prevents cases of the user providing a cost function returning values lower than 1, with the heuristic assuming 1 – it would break the algorithm, which would return a suboptimal (not shortest/lowest cost) path. A similar assumption is made for the goal node – a node is assumed to be the goal if they are the same references, something which is not completely necessarry when “custom” functions are provided (indeed, it completely depends on the function at hand).
Hopefully, I’ll find some time to scribble together a couple of demos.