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: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.