http://www.cs.ualberta.ca/~jonathan/Papers/Papers/fringe.pdf Have any of you ever used Fringe search for Path Finding? I'm considering using it for a game I'm working on and wondered if people have actually found it to improve on A*. The paper would suggest it's faster and easier to implement, but I'd like a bit more to go on before I jump in and use it. Cheers, Stevo

Any further information than the link I provided would be usefull also, as currently this is all I have to go on.

Thanks,
Stevo

I was at IEEE 2005 where Yngvi presented the paper. The fringe search method is an improvement on vanilla A* (and IDA*) and it is easy to implement since it's based upon the principle of caching the cost to the fringe nodes during an iterative deepening search. (thereby preventing duplicated processing)

He told me at the time that there is source code and an executable available for download from the website.

Maybe i missed something, but is this really novel?
Caching to avoid duplicate processing and not fully ordered lists. These optimizations have been around for a while for priority queues.

Are you comparing it to A* here?

One thing I noted was that Yngvi et als version of the A* search they were comparing Fringe search to used a "ballanced binary tree" for the open list. Surely this is slow. Ballancing binary trees in real time is not cheap. I thought there were better ways to go here (unsorted open list with a smaller priority queue for only the cheapest nodes, buckets, etc)

I recommend you implement it then benchmark it. It'll not take long if you already have an implementation of A*.

Yes I feel the same way actually, I haven't implemented either algorithm yet. Although I've used A* for previous games.

I think perhaps the best way to go here is to implement A* search initially and then consider Fringe search when I'm optimising the A*.