Jump to content
  • Advertisement
ccherng

Funnel Filter algorithm pathfinding

Recommended Posts

Posted (edited)

I read about Simple Stupid Funnel Algorithm at
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
That article made sense to me. You maintain one line to the left wall and one line to the right wall. When they cross in updating then you know part of the shortest path has been found.

I was reading the thesis of Douglas Jon Demyen
https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf
On pages 52 to 57 he describes a funnel filter algorithm using a deque. Is there anyone who understands the pseudo code he gives. The notation he uses is left unexplained. I don't understand how the code he gives works.

Edited by ccherng

Share this post


Link to post
Share on other sites
Advertisement
1 hour ago, ccherng said:

Is there anyone who understands the pseudo code he gives. The notation he uses is left unexplained. I don't understand how the code he gives works.

I think I've worked from that paper before. It would take me some time to get back up to speed on the algorithm and on the paper, but if there are particular notational elements or aspects of the pseudocode that you're uncertain about, you could ask about them specifically.

Share this post


Link to post
Share on other sites
9 hours ago, Zakwayda said:

I think I've worked from that paper before. It would take me some time to get back up to speed on the algorithm and on the paper, but if there are particular notational elements or aspects of the pseudocode that you're uncertain about, you could ask about them specifically.

Its not even clear to me what the state of the deque is on the first call to Add(). And once in Add() its not clear what is going on there is this notation f_{Left+1} what is that suppose to mean?

Share this post


Link to post
Share on other sites

I can't really dig into this right now (unfortunately - I have implemented this algorithm before, and I think I did work partly from this paper). Meanwhile though, I don't see 'f_{Left+1}' anywhere, although I could easily be missing it. Do you mean 'fLeft+1', like in algorithm 5, line 6?

In any case, it might be easier if you specified which pseudocode block(s) (e.g. algorithm 4 or 5) and line number(s) you're referring to.

Share this post


Link to post
Share on other sites
11 hours ago, Zakwayda said:

I can't really dig into this right now (unfortunately - I have implemented this algorithm before, and I think I did work partly from this paper). Meanwhile though, I don't see 'f_{Left+1}' anywhere, although I could easily be missing it. Do you mean 'fLeft+1', like in algorithm 5, line 6?

In any case, it might be easier if you specified which pseudocode block(s) (e.g. algorithm 4 or 5) and line number(s) you're referring to.

Yes 'fLeft+1' this f with a subscript of left + 1. I have no idea what it means.

Share this post


Link to post
Share on other sites

Again, I can't dig into this as much as I'd like, but I think the 'f' refers to the FunnelDeque argument to the function, and 'Left' and 'Right' refer to the side of the deque. In terms of subscripting, I think it might be (fLeft)+1 rather than f(Left+1), if that makes any difference.

I wish I could help more, but it would take me some work to get back up to speed on this algorithm. Although I imagine you're already doing this, maybe the best suggestion I can offer is to try to fully understand the algorithm conceptually (using multiple references if needed, as you appear to be doing), and then once you have it nailed down conceptually, try to map that understanding to the pseudocode. I know that's fairly obvious and probably not that helpful, but it's the best suggestion I can think of at the moment.

Maybe someone will jump in with something more useful though.

Share this post


Link to post
Share on other sites

Demyen's diagrams are much clearer than his pseudocode, I would use them as the main reference; there's no point in reverse-engineering undefined notation when you can understand the algorithm and implement it on your own.

Regarding the deque, it's more like two deques sharing one end than an actual deque: it doesn't have a privileged direction and it has three notable locations, the current apex in the middle ("Apex ") in addition to "Left" and "Right"  (the current end of the two sides of the funnel).

Clearly "+1" means the next vertex out (from "Apex"), i.e. "Left+1" or "Right+1" is the new unprocessed vertex and "Apex+1" is the first funnel vertex (in an ambiguous direction), which gets promoted to "Apex" when "Apex" is consolidated into the path.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!