Modified Funnel Algorithm

Once you have the path joining the centers of those circles, move each segment by some amount in a direction perpendicular to the segment. Add arcs in between the segments. No brilliant ideas are needed. If you have trouble with any specific step, ask again.

I don't think that would work in for example a case like this one.

Case

I would have to do the offseting during the algorithm's run while I still know which side of the funnel/path the segments belong to. This would complicate things when it came to the convex portions of the funnel and the removing of them wouldn't it?

Quote:

Once you have the path joining the centers of those circles, move each segment by some amount in a direction perpendicular to the segment. Add arcs in between the segments. No brilliant ideas are needed.

I don't believe that will work in the general case (see Antonym's follow-up post for an example). When a segment of the path passes on the same side of two consecutive vertices, the entire segment can simply be moved laterally by a distance equal to the agent radius, as you suggest, but when the vertices fall on opposite sides of the segment, the segment must be recomputed to lie tangent to both circles.

It can still be done as a post-processing step, but a problem with this approach is that the agent may clip vertices that are not part of the computed path, but that lie close to the computed path (i.e. closer than the radius of the agent). The modified funnel algorithm addresses this problem by considering such vertices as the algorithm progresses and making adjustments accordingly.

I presume from your use of terminology that you’ve probably already read Efficient Triangulation-Based Pathfinding (ie TRA*), when the author talks briefly about a ‘modified’ funnel algorithm as you’ve described. The paper is low on details, but you can find the author’s thesis, which is an expanded version of the other paper, here. In it there is a detailed section on the modified funnel algorithm, including pseudo code, which might help you out.

Please note that I haven’t closely reviewed the section or the pseudo code, as I implemented the 'modified funnel algorithm' before finding the paper. The basic idea was that whenever calculating the vector between two vertices in the funnel, we need to instead calculate the vector of a tangent that connects circles placed on the vertices. For vertices on the same side of the tunnel, the tangent is the same as the vector connecting the two points, and thus this case negates itself. Therefore, we only need to alter our calculations when the two points lie on opposite sides of the funnel, where we need the internal tangent.

From memory, there are a few special-case scenarios that you might need to deal with, particularly if you consider your start and end points, which need to be handled differently, as vertices on the funnel.

EDIT: Ok, I've just seen from your other post that you've already seen the full paper.

Hope this helps,
Jackson Allan

[Edited by - jack_1313 on October 10, 2009 9:45:12 PM]

Thanks. I was wondering, do you happen to still have some code I could look at?

I think I get the concepts although I've never been very good at math, could you help me out with the formula?

I asume adding the arc/curve is a post-processing step? Is there/do I have to add/generate the vertices of the arc/curve at all?

Can anyone understand the pseudocode in the thesis?
pgs: 56, 57, 60, 61.

Thesis

How is the deque supposed to work/be used?

I am really desperate for a solution to the modified funnel algorithm.

Hey Antonym,

I just want to say that I haven't forgotten about your post and that I will post some psuedo-code ASAP. The tricky bit is that my code was well-embedded into my project, so lifting it out and making it read in a meaningful way is a bit time consuming.

Jackson Allan

The ‘funnel algorithm’ that I implemented *without* the modifications to account for circular agents follows first. I know that you've already implemented something similar, but I have included it so that you can see how my code works before the modifications to account for witdth are are made. After that, the modifications are shown and explained:

We start with an ordered list of vertices which constitute the tunnel, which is the result of my pathfinding function. No two vertices are repeated. The first and the last two elements in this list don’t actually refer to features of our navigation mesh, but are instead the start and end position. The end position is added to the list twice, one for the left side and one for the right side (see next below).

We also have another list specifying whether each vertex is on the left or the right side of the tunnel, because we will need this information.

There are three dynamic variables that we will use, which each hold the index of an element on the list that is our tunnel. They are the apex, the left feeler and the right feeler. All start as 0 (the first element, ie the start position, probably the agents current position.)

We then step through each element on the tunnel list. For each element, we first take the vector from the apex point to this element (that is, the point that this element corresponds to). If that vector shows that this element corresponds to a point on the ‘inner’ side of the line formed by the apex to the feeler for the side of the tunnel that the current element is on, we change that feeler to that point/element. We also do this if the feeler on that side is also the apex (which happens at the start and also after we advance the apex), since there would be no vector between them to use in a comparison.
Then, if either of the above to conditions were met, we check to see if the current point is on the ‘outer’ side of the feeler for the opposite side of this list. If it is, we add the index of our current apex to our path, make the feeler for the opposite side the new apex, set both the left and right feeler to point to our new apex, and start stepping through our tunnel list again from the new apex.

This loop will leave us with a list of indices of the tunnel list that correspond to the points from which we will derive the final path, minus the end position. From here it is an easy task to build the final path as a list of points.

Note: by ‘inner’ and ‘outer’ side I mean in relation to the tunnel. The ‘inner’ side of the left feeler is its right side, the outer is its left, and vica-versa for the right feeler.

It might be difficult to picture when explained with text, but if you use a pen and paper you can probably see what is happening. As you process the points in order, the left and right feelers, which always correspond to the most ‘inner’ point processed on either side of the tunnel, will converge until they cross, thereby advancing the apex and adding to the path. You will notice some differences from the algorithm as described in the papers. Most obviously, I do not keep a left or right list, but am instead only interested in the most relevant point on each side as denoted by the ‘feelers.’ I have done this because it means I can run the entire algorithm without using dynamic storage containers, as well as simplifies the code. The down side is that some points will be processed more than once, since each time we advance the apex we are starting anew and discarding whatever information had already be processes beyond it.

Here is my code for my version of the basic funnel algorithm. Please not it is untested in this form. It’s the code from my app, but I’ve changed the names of variables so that it makes more sense to a reader, removed the allowances for circular objects, and added some comments.



Ok, now for the modifications that allow us to account for agent width. Since we only even calculate the vector between two points in one place, adding the modifications is pretty simple. In fact, other than that, we only need to add one other bit of code, and of course post-process differently in order to generate the actual points on the path.
The first bit comes directly after calculating the vector from the apex to current point. If the apex and the current points are on opposite sides of the funnel then we need the relevant internal tangent of circles centered on our two points whose radius corresponds to the radius of our agents. There are two special situations we must account for – the start and end node. In both situations we need the tangent of a circle placed on the feature of the navigation mesh, which passes through the start or end point. The maths you see in the code is the tangent calculations.

Other than that, you will see that another bit of code has been added in the section where we advance the apex.

Finally, we need to post-process our path differently and add each point modified by the information we have. How you want to do that is up to you and will probably depend on how closely your agents follow the path. For instance, you can represent the circular curves around the vertices exactly by breaking them into points, or you can just use one point as a general approximation, which will be fine if your agents use some kind of steering behavior.



I apologies in advance for any typos or bugs in the code. As I said, its more or less directly lifted so its should be ok. Also, there seems to be some formatting issues in both the code and the post itself.

Hope this helps,
Jackson Allan

[Edited by - jack_1313 on October 8, 2009 9:42:38 AM]

Thanks a lot for the code. I had several mistakes in my implementation which your example helped me correct, I really appreciate it ^_^.

I have a question though, if I understand correctly that code doesn't generate and/or offset the vertices taking into account the radiuses does it? It just tells what will be the new path if we take into account the radiuses? My main problem is that I have no idea how to generate the path taking into account/wrapped around the radiuses.

[Edited by - Antonym on October 8, 2009 3:51:19 PM]

How you do that will depend on what you want to use the path for, but in any case it is a comparatively trivial and mainly mathematical problem. As you’ve noted, my code will give you not the actual path, but a list of the vertices that will be used on the actual path as well as the knowledge of whether the agent should go around those vertices on the left or right based on the side of the tunnel they are on.

In my case, I only need an approximation of the path. It’s a simple matter of looking at each vertex between the start and end, taking the vector from the previous vertex to it and the vector from it to the next one, normalising them, adding them together and then rotating the result 90 degrees either clockwise, if the vertex if on the left side, or counter clockwise if on the right (you wont even need trig functions to do this). This vector is then sized to our agent’s radius and added to the original point. Thus, each vertex relevant to the path becomes one offset vertex in the final path. The start and end positions remain unchanged. This method is sufficient because my agents use steering behaviours to follow the path, and thus follow natural looking curves in practice. It is neither necessary nor advisable for me to generate a literal path whereby the circular curves around vertices are plotted exactly.

However, if your agents move along the path in a 100% literal sense and don’t deviate at all, then you may want to generate a more accurate representation. You will need to do the tangent calculations again. For every two successive vertices on the path given by the code I posted above, you’d want to either a) add a segment to your final path that is these two vertices displaced by half your agent width along the segment’s normal, if the two points are on the same side of the funnel, or b) add the segment that is the two points where the relevant internal tangent connecting two circles, placed on each point, intersect the circles themselves. That is exactly the same theory that you use when running the funnel algorithm. In addition to that, for each vertex, you also need to generate a series of points which will be the sector of the circle that fills the empty space that connects the segments described above, all of which can be achieved fairly easily using standard trigonometry functions. Although this approach generates the most literal path, it is probably less useful for most game environments.

If you want this method, you easily optimise it by not doing this as a post-processing step, but doing it as you run the funnel algorithm. I’m speculating now, but regarding the left and right ‘feelers,’ in addition to their indices and the vectors from the apex to each of them (the information we store while running the loop) you’d want to store the points of the tangent intersections, and then add them to the final path each time you advance the apex, also generating the ‘in-between’ curves around each vertex as you go (in each case where we find a new apex, you'd first generate the curve for the previous apex).

Otherwise, there would still be another option – simply use the original vertices without post-processing them, and also allow your agents to access the information of what side they should pass each vertex on.

Hope this helps,
Jackson Allan

Quote:

However, if your agents move along the path in a 100% literal sense and don’t deviate at all, then you may want to generate a more accurate representation. You will need to do the tangent calculations again. For every two successive vertices on the path given by the code I posted above, you’d want to either a) add a segment to your final path that is these two vertices displaced by half your agent width along the segment’s normal, if the two points are on the same side of the funnel, or b) add the segment that is the two points where the relevant internal tangent connecting two circles, placed on each point, intersect the circles themselves.

Just for completeness, I'll go ahead and point out that this approach may still generate invalid paths where the agent collides with vertices that are not part of the path, but lie close to it. The actual modified funnel algorithm treats the vertices as having a radius as it finds its way along the channel, adjusting the path as necessary to avoid any collisions (in this sense, the generated path is always guaranteed to be 'perfect', provided the input is valid).

As you note though, whether perfectly accurate paths are really needed depends on the circumstances.

Quote:

Original post by jyk Quote: However, if your agents move along the path in a 100% literal sense and don’t deviate at all, then you may want to generate a more accurate representation. You will need to do the tangent calculations again. For every two successive vertices on the path given by the code I posted above, you’d want to either a) add a segment to your final path that is these two vertices displaced by half your agent width along the segment’s normal, if the two points are on the same side of the funnel, or b) add the segment that is the two points where the relevant internal tangent connecting two circles, placed on each point, intersect the circles themselves. Just for completeness, I'll go ahead and point out that this approach may still generate invalid paths where the agent collides with vertices that are not part of the path, but lie close to it. The actual modified funnel algorithm treats the vertices as having a radius as it finds its way along the channel, adjusting the path as necessary to avoid any collisions (in this sense, the generated path is always guaranteed to be 'perfect', provided the input is valid). As you note though, whether perfectly accurate paths are really needed depends on the circumstances.

Actually, with all due respect, I’m talking about post processing the information returned by the initial code and explanation I posted above, which is basically the modified funnel algorithm without using dynamic storage containers. In fact, it does *exactly* what you’ve described here, and gives index references to all the points on the path that you think I’m talking about and all the ‘nearby’ points that would infringe on that path if we simply took the path from the non-modified funnel algorithm and applied the latter part of my explanation on this issue (which you’ve quoted). That is, the information that this part is supposed to be applied to is the list of vertices identified as being on the path by the modified funnel algorithm. I think you might have misread my post or posts.

I just want to point out again that this doesn’t really need to be done as a post processing step and can be done as you run the funnel algorithm, which might have been a point of confusion. In my case, where I’m not using literal path, doing it as a separate step afterwards doesn’t really make difference in terms of speed because it involves new calculations. However, if you were using a literal path you’d be running basically the same calculations both in the funnel algorithm and in the final plotting of the path, so it would be faster to do it all together. The funnel algorithm stage would then give the actual path, not a list of indexes of mesh vertices which will be involved in the final path.

Quote:

Actually, with all due respect, I’m talking about post processing the information returned by the initial code and explanation I posted above, which is basically the modified funnel algorithm without using dynamic storage containers. In fact, it does *exactly* what you’ve described here, and gives index references to all the points on the path that you think I’m talking about and all the ‘nearby’ points that would infringe on that path if we simply took the path from the non-modified funnel algorithm and applied the latter part of my explanation on this issue (which you’ve quoted). That is, the information that this part is supposed to be applied to is the list of vertices identified as being on the path by the modified funnel algorithm. I think you might have misread my post or posts.

Sure, it sounds like I must have misread.