Indexed A Star

Indexed A* is a common variation of the A* algorithm that is faster than the general A*.

In the general A* implementation, data are held for each node in the open or closed lists, and these data are held as a record. Records are created when a node is first considered and then moved between the open and closed lists, as required. There is a key step in the algorithm where the lists are searched for a node record corresponding to a particular node. This operation is somewhat time-consuming.

The indexed A* algorithm improves execution speed by using an array of all the node records for every node in the graph. Nodes must be numbered using sequential integers (see IndexedNode.getIndex()), so we don't need to search for a node in the two lists at all. We can simply exploit direct access by using the node index to get its record in the array (the record is created on the fly if it is missing). This means that the close list is no longer needed. To know whether a node is open or closed, we use the category of the node record. This makes the search step very fast indeed (in fact, there is no search, and we can go straight to the information we need). Unfortunately, we can't get rid of the open list because we still need to be able to retrieve the element with the lowest cost. However, we use a BinaryHeap for the open list in order to keep performance as high as possible.

The IndexedAStarPathFinder is a fully implemented PathFinder that can perform both interruptible and non-interruptible pathfinding.