Fringe search

In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*).

An important difference here between fringe and A* is that the contents of the lists in fringe do not necessarily have to be sorted - a significant gain over A*, which requires the often expensive maintenance of order in its open list.

Similarly, a marker array allows lookup of a node in the list to be done in constant time.

When tested on grid-based environments typical of computer games including impassable obstacles, fringe outperformed A* by some 10 percent to 40 percent, depending on use of tiles or octiles.

Possible further improvements include use of a data structure that lends itself more easily to caches.