String Pulling Explained

Quote:

Original post by Infinite_Loop84 I have tried doing some digging and I have been flooded with articles about how to generate a navigation mesh but I havent seen much on how to plot a path through the mesh once you create it. I dont have a problem A*-ing through the blocks of the mesh itself, but I am abit stumped on creating points for the AI to follow through the mesh. The string pulling technique has been suggested but outside of the AI Game Wisdom 3 book I have failed to find any decent documentation or explanations of how this technique is actually accomplished. Any other methods are more than welcome. Any links, articles, books, etc that would shed some light on this subject would be greatly appreciated.

I just finished up a 2-d navigation mesh system including pathfinding (with string-pulling) for agents of non-zero radius, so I may be able to help out a bit (or at least point you in the right direction).

I don't have the AI Game Programming Wisdom book you mention, but like you I had a hard time finding good references on the funnel (AKA string pulling) algorithm, especially the modified version that takes the radius of the agent into account.

The best reference I found (not only on the funnel algorithm, but on pathfinding in navigation meshes in general) is this paper. Unfortunately, the pseudocode for the funnel algorithm contained therein seems to contain some errors/omissions, but most of the key info is there in some form or another.

I have working code for all this, but it's got a lot of context-specific stuff in it, so I doubt it would be of much use to anyone else. If you have questions or get stuck on anything though, let me know and I'll certainly try and help if I can.

Quote:

Original post by Infinite_Loop84 The string pulling technique has been suggested but outside of the AI Game Wisdom 3 book I have failed to find any decent documentation or explanations of how this technique is actually accomplished. Any other methods are more than welcome.

As I understood it, the 'string-pulling' phase is just a method of smoothing out the paths where possible. You use it as part of a wider pathing system rather than it being something that does the whole thing for you.
Very naive version:

Let i = 1.Let p be your path, a list of 3D positions, p[1]... p[path length]while path length is at least i + 2:    Take points on your path p and p[i+2]    if you can go directly between p and p[i+2]        remove p[i+1] from the path    else        increment i

Obviously the 'can go directly' test is the complex part and how that's implemented will depend on whether you're pathing from the middle of each triangle or from one edge to another, whether you guarantee minimum sizes for each triangle based on your entity sizes, etc.

Quote:

Original post by Kylotan Quote: Original post by Infinite_Loop84 The string pulling technique has been suggested but outside of the AI Game Wisdom 3 book I have failed to find any decent documentation or explanations of how this technique is actually accomplished. Any other methods are more than welcome. As I understood it, the 'string-pulling' phase is just a method of smoothing out the paths where possible. You use it as part of a wider pathing system rather than it being something that does the whole thing for you. Very naive version: Let i = 1.Let p be your path, a list of 3D positions, p[1]... p[path length]while path length is at least i + 2: Take points on your path p and p[i+2] if you can go directly between p and p[i+2] remove p[i+1] from the path else increment i Obviously the 'can go directly' test is the complex part and how that's implemented will depend on whether you're pathing from the middle of each triangle or from one edge to another, whether you guarantee minimum sizes for each triangle based on your entity sizes, etc.

Just to clarify, the 'funnel' algorithm I referred to in my post is different than the method described by Kylotan.

The 'node removal' method actually has at least a couple of forms: one that looks more or less like what's described above, and one where you check every node from the current node to the end, rather than just the next node. The latter form gives slightly better results, but neither is perfect - the path will usually be improved, but the resulting path may still go 'out of its way' to get to the goal (especially with navigation meshes).

The funnel algorithm on the other hand is an algorithm from computational geometry that computes an exact geodesic path through a simple polygon. Given two points and a 'channel' of polygons in a navigation mesh, the funnel algorithm will return the exact shortest path between the two points.

I have no evidence to back this up, but I can imagine that the funnel algorithm might actually perform *better* than the node-removal method, since it doesn't involve any raycasting or intersection testing. (I suppose that depends though.) The main downside of the funnel algorithm though is that it's more complicated to implement than the node-removal method.

(As for 'string pulling', I was under the impression that it was just another name for the funnel algorithm, but I could be wrong about that.)

jyk@ im beginning to think that you are right about the funnel naming vs string pulling naming, they seem to be interchangeable. The biggest problem i have run into however is finding documentation that explains at least in high level the funnel/string pull algorithm and also documentation to provide for how to create a navigational mesh that would support said pathing algorithm. That seems to be my main hurdle at this point. Any white paper, information, or book links would be a huge help. Thanks!

Quote:

The biggest problem i have run into however is finding documentation that explains at least in high level the funnel/string pull algorithm and also documentation to provide for how to create a navigational mesh that would support said pathing algorithm. That seems to be my main hurdle at this point. Any white paper, information, or book links would be a huge help. Thanks!

Actually, the paper I linked to in my first reply has all of this information. As I mentioned there appear to be some errors or omissions in the pseudocode (and some of the article is a bit hard to follow), but the information is all there in one form or another.

I spent quite a while looking for information on this topic, and the paper in question was the best overall reference I found (I don't have any of the AI Wisdom books though - they might have some good material as well).

Sorry I can't be more helpful than that, but if there's anything about the paper that's unclear, post back and I may be able to help.

jyk: that paper is really nice, thanks for the link! I just finished implementing something similar (for fun) and must say that there are lots of fairly non-trivial parts and the OP is correct that it's hard to find a good reference for doing this mainly because the implementation of the methods require quite a bit of thinking.

To me, string pulling and the funnel algo are two different things. The funnel algo is used when you have a channel (single path through a set of triangles), while the string pulling algo is meant to achieve the same thing as the funnel algo but when you don't have a nice channel to follow.

For the OP, the thing to look at would be to see what kind of nav mesh you have - are all the polygons convex or are there some that are concave? If your navmesh is a bunch of triangles, then the A* path through the triangles can be used directly with the funnel algo to find the shortest path within the channel. As mentioned in the link jyk sent, though, A* through triangles doesn't guarentee you will find the most optimal path, so you'll need to "keep looking" for better paths (which the paper mentions). Doing this is intensive though since you basically will need to find an initial path + funnel of that path, which is fast in itself, but then you'll need to find other paths that aren't the same, and then check the results of the funnel algo on those paths to see if they are shorter than your initial path, which gets expensive the more ways around there are (ie the more obstacles you are potentially weaving through along the path). I have code for the funnel algo if you're interested, though (has two main functions, one that adds verts to the channel, and another that collapses back verts/the apex when a vert was added that is "inside" the current cone.)

Hi,

I've been having the same problem. Finding a good description of the funnel/string pulling algorithm is not easy if I want to implement it. Also, the algorithm seems to be used in a number of places but I haven't managed to find an implementation of it (apart from the first hit in Google - http://www.cs.wustl.edu/~suri/cs506/projects/sp.html - for which the java classes are accessible - http://www.cs.wustl.edu/~suri/cs506/projects - I just don't know how to use the classes). I'm looking for an existing implementation because I don't really trust my coding abilities and it would be nice to use a code that's proved to be working well.

If anyone of you has a working code that I could use to find a shortest path inside a (2D) polygon I would be very happy. I already have the triangulation, I just need the funnel algorithm. As my work will probably produce some research articles I would also be happy to put an acknowledgment in the papers.

Thanks

Quote:

Original post by zmokus Hi, I've been having the same problem. Finding a good description of the funnel/string pulling algorithm is not easy if I want to implement it. Also, the algorithm seems to be used in a number of places but I haven't managed to find an implementation of it (apart from the first hit in Google - http://www.cs.wustl.edu/~suri/cs506/projects/sp.html - for which the java classes are accessible - http://www.cs.wustl.edu/~suri/cs506/projects - I just don't know how to use the classes). I'm looking for an existing implementation because I don't really trust my coding abilities and it would be nice to use a code that's proved to be working well. If anyone of you has a working code that I could use to find a shortest path inside a (2D) polygon I would be very happy. I already have the triangulation, I just need the funnel algorithm. As my work will probably produce some research articles I would also be happy to put an acknowledgment in the papers. Thanks

Just out of curiosity, is it the unmodified funnel algorithm (that treats the object as a point) that you want to implement? Or do you need the 'modified' funnel algorithm that takes the radius of the object into account?

Only the basic (unmodified) one. Thanks!

Quote:

Only the basic (unmodified) one. Thanks!

My first suggestion would be dive into the implementation, and then post back here if you run into specific problems.

I do have working code for both the unmodified and modified versions, but it's pretty application-specific and might take some work to make presentable (and unfortunately I'm short on extra time these days).

If you really get stuck though, let me know and I could at least post the code in its 'raw' form. (Who knows - it might be enough to base an implementation on.)