Jump to content
  • Advertisement
Sign in to follow this  
StevoHolmes

Fringe Search - Better than A*

This topic is 4844 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
I recommend you implement it then benchmark it. It'll not take long if you already have an implementation of A*.

Share this post


Link to post
Share on other sites
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*.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!