Modified Funnel Algorithm
September 27, 2009 06:12 AM
Hello I am trying to find a method to 'wrap' the blue segment around the green circles to give the path some offset from the vertices/to make it arc around the vertices before or after running the funnel algorithm. Any ideas?
Path
I use c++ in case it's relevant.
Thanks.
[Edited by - Antonym on September 28, 2009 7:40:06 AM]
21,607
September 27, 2009 04:54 PM
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.
September 28, 2009 04:41 AM
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?
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?
2,389
September 28, 2009 06:44 AM
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.
September 28, 2009 10:45 PM
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]
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]
-----------Autumn Fog - A 2D Action Wargame
September 29, 2009 10:56 AM
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?
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?
October 07, 2009 12:45 PM
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.
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.
October 07, 2009 06:21 PM
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
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
-----------Autumn Fog - A 2D Action Wargame
October 08, 2009 08:42 AM
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.
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.
/*’tunnel’ is our list of indices of points on our tunnel.The points themselves are stored in a separate array, ‘points’,because they are used by other parts of the program.‘tunnel_left_right’ is an array of booleans that specify if eachelement is on the left or right side of this tunnel.These lists would have been prepared already.*/USHORT apex = 0;USHORT feeler[ 2 ] = { 0, 0 }; //ie left/rightVector2D feeler_v[ 2 ]; //We store the vector from the apex to the feelers,which is a simple optimization that stops us from having to recalculatethem each stepfor( USHORT c = 1; c < num_elements_on_tunnel; c++ ){Vector2D v = points[ tunnel[ c ] ] - points[ tunnel [ apex ] ]; //Is in on the ‘outside’ of the corresponding feeler? (or is the first//iteration after advancing the apex)? if( apex == feeler[ tunnel_left_right [ c ] ] || ( v.Cross( feeler_v[ tunnel_left_right[ c ] ] ) < 0.0f ) == ! tunnel_left_right[ c ] ) { feeler[ tunnel_left_right[ c ] ] = c; feeler_v[ tunnel_left_right[ c ] ] = v; //Does it cross the opposite feeler? //Here we must first establish that the opposite feeler is not the apex, else there will be no meaningful calculation//Also, we need to account for our end position, which is the last two elements on the tunnel list (see condition 2) if( apex != feeler[ !tunnel_left_right[ c ] ] && ( tunnel[ c ] == tunnel [ feeler[ !tunnel_left_right[ c ] ] ] || ( v.Cross(feeler_v[ !tunnel_left_right[ c ] ] ) < 0.0f ) == !tunnel_left_right[ c ] ) ) { path_indices.push_back( apex ); apex = feeler[ !tunnel_left_right[ c ] ]; c = apex; //ie apex + 1 on next itteration feeler[ 0 ] = apex; feeler[ 1 ] = apex; } } }/*Now we need to post-process the results and transform them into our actual pathJust remember that path_indices now stores indices of elements on the funnel list, without the end position which you would need to add as well.For example:for( USHORT i = 0; i < path_indices.size(); i++ ) actual_path.push_back( points[ funnel[ path_indicies ] ] );<br>actual_path.push_back( end_position );<br>This should work, but I’m writing code off the top of my head now just for the sake of showing you.*/</span><br><br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>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.<br>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.<br><br>Other than that, you will see that another bit of code has been added in the section where we advance the apex.<br><br>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.<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br>USHORT apex = <span class="cpp-number">0</span>;<br>USHORT feeler[ <span class="cpp-number">2</span> ] = { <span class="cpp-number">0</span>, <span class="cpp-number">0</span> };<br>Vector2D feeler_v[ <span class="cpp-number">2</span> ];<br><br><span class="cpp-keyword">for</span>( USHORT c = <span class="cpp-number">1</span>; c < num_elements_on_tunnel; c++ )<br>{<br> Vector2D v = points[ tunnel[ c ] ] - points[ tunnel [ apex ] ];<br><br> <span class="cpp-comment">//ADDED SECTION</span><br> <span class="cpp-keyword">if</span>( v.LengthSqr() > agenthalfwidth * agenthalfwidth ) <span class="cpp-comment">//if v.length is below halfwidth, then the vertices are too close together</span><br> <span class="cpp-comment">//to form meaningful tangent calculations. This is not the case for vertices on the same side of funnel,</span><br> <span class="cpp-comment">//but they get straight-line calculations anyway, and no two vertices on opposite sides of funnel should be this close</span><br> <span class="cpp-comment">//because that would make path invalid (only start and end)</span><br> {<br> <span class="cpp-keyword">if</span>( apex == <span class="cpp-number">0</span> ) <span class="cpp-comment">//Apex is start point</span><br> {<br> <span class="cpp-keyword">if</span>( c < opensize - <span class="cpp-number">2</span> ) <span class="cpp-comment">//If not true, the current</span><br><span class="cpp-comment">//element is the end point, so we actually want straight line between the apex and it after all</span><br> {<br> <span class="cpp-keyword">float</span> len = v.Length();<br> <span class="cpp-keyword">float</span> fsin = agenthalfwidth / len * ( tunnel_left_right[ c ] ? -<span class="cpp-number">1</span>.0f : <span class="cpp-number">1</span>.0f );<br> <span class="cpp-keyword">float</span> fcos = sqrt( len * len - agenthalfwidth * agenthalfwidth ) / len;<br> v = Vector2D( v.x * fcos - v.y * fsin, v.x * fsin + v.y * fcos );<br> }<br> }<br> <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>( c >= opensize - <span class="cpp-number">2</span> ) <span class="cpp-comment">//Current point is end point</span><br> {<br> <span class="cpp-keyword">float</span> len = v.Length();<br> <span class="cpp-keyword">float</span> fsin = agenthalfwidth / len * ( tunnel_left_right[ apex ] ? <span class="cpp-number">1</span>.0f : -<span class="cpp-number">1</span>.0f );<br> <span class="cpp-keyword">float</span> fcos = sqrt( len * len - agenthalfwidth * agenthalfwidth ) / len;<br> v = Vector2D( v.x * fcos - v.y * fsin, v.x * fsin + v.y * fcos );<br> }<br> <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>( tunnel_left_right[ c ] != tunnel_left_right[ apex ] ) <span class="cpp-comment">//Opposite sides of list</span><br> {<br> <span class="cpp-keyword">float</span> len = v.Length() * <span class="cpp-number">0</span>.5f;<br> <span class="cpp-keyword">float</span> fsin = agenthalfwidth / len * ( tunnel_left_right[ c ] ? -<span class="cpp-number">1</span>.0f : <span class="cpp-number">1</span>.0f );<br> <span class="cpp-keyword">float</span> fcos = sqrt( len * len - agenthalfwidth * agenthalfwidth ) / len;<br> v = Vector2D( v.x * fcos - v.y * fsin, v.x * fsin + v.y * fcos );<br> }<br> }<br><br> <span class="cpp-keyword">if</span>( apex == feeler[ tunnel_left_right[ c ] ] || ( v.Cross( feeler_v[ tunnel_left_right[ c ] ] ) < <span class="cpp-number">0</span>.0f ) == !tunnel_left_right[ c ] )<br> {<br> feeler[ tunnel_left_right[ c ] ] = c;<br> feeler_v[ tunnel_left_right[ c ] ] = v;<br><br> <span class="cpp-keyword">if</span>( apex != feeler[ !tunnel_left_right[ c ] ] && ( tunnel[ c ] == tunnel [ feeler[ !tunnel_left_right[ c ] ] ] || ( v.Cross(feeler_v[ !tunnel_left_right[ c ] ] ) < <span class="cpp-number">0</span>.0f ) == !tunnel_left_right[ c ] ) )<br> {<br> path_indices.push_back( apex );<br> apex = feeler[ !tunnel_left_right[ c ] ];<br><br> <span class="cpp-comment">//ADDED SECTION</span><br> <span class="cpp-comment">//There is occasionaly an instance whereby the current vertex is actually closer</span><br> <span class="cpp-comment">//than the one on the oposite left/right list</span><br> <span class="cpp-comment">//If this is the case, SWAP them, because we want to move to apex to the closest one</span><br> <span class="cpp-keyword">if</span>( v.LengthSqr() < feeler_v[ !tunnel_left_right[ c ] ].LengthSqr() )<br> {<br> std::swap( tunnel[ leftright[ !tunnel_left_right[ c ] ] ], tunnel[ c ] );<br> std::swap( tunnel_left_right[ feeler[ ! tunnel_left_right[ c ] ] ], tunnel_left_right[ c ] );<br> }<br><br> c = apex; <span class="cpp-comment">//ie apex + 1 on next itteration</span><br> feeler[ <span class="cpp-number">0</span> ] = apex;<br> feeler[ <span class="cpp-number">1</span> ] = apex;<br> }<br> }<br> }<br><br><span class="cpp-comment">/*As stated, you will need to post-process differently to construct the actual path. Again, remember that path_indices now stores indices of elements on the funnel list, without the end position, and that you will use the tunnel_left_right list to know which side the points are on, and thus which side you will need to flank the point on.*/</span><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>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.<br><br>Hope this helps,<br>Jackson Allan<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - jack_1313 on October 8, 2009 9:42:38 AM]<!–EDIT–></span><!–/EDIT–>
-----------Autumn Fog - A 2D Action Wargame
October 08, 2009 01:51 PM
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
