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.

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.

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?

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.

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.

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.

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.

There is something that alludes me in his code. 
However, this resembles theta* with an extra left and right areas separation:

https://en.wikipedia.org/wiki/Theta*