Hello, I started play around with pathfinding (A*). I'm at the point where I can get the shortest path, node to node and are about to make a character walk the path. I would like to make my character walk the blue line. Just walk from the start node to the goal node would as you can see would cross the water. My question is how I should attack that problem. The first thing that crossed my mind was to only allow nodes (each tringle is a node) that shares an edge with an nother node to become a neighbours. The difference would be that the path would require two extra nodes, the two triangles right above the start node. So do I wan't to do that or do I wan't to get the shortest path posible and once I have it alter it with some line collision or some other means of ensuring the path follows valid ground. limiting the number of neighbours per node would make a long path contain much more nodes and therefore feels like a bad idea. I'm greatfull for any hints or ideas. As said I'm new to the whole pathfinding scene. [Edited by - HermanssoN on September 6, 2009 10:07:29 AM]

Quote: limiting the number of neighbours per node would make a long path contain much more nodes and therefore feels like a bad idea.

In navigation-mesh-based pathfinding, the usual approach is to consider two polygons to be neighbors only if they share an edge. The graph nodes are then positioned either at the polygon centroids, or at the edge midpoints.

Making polygons neighbors if they share a single vertex will lead to invalid paths, generally speaking (just as in your example).

I can't quite see the logic in your concern that having more nodes per path on average is a 'bad idea'. It's kind of like saying that 'limiting the number of neighbors per node will make my agents go around brick walls rather than through them, which feels like a bad idea'. How can building correct paths (and avoiding incorrect ones) be a bad idea? :)

So in summary, yes, you only want to consider polygons to be neighbors if they share an edge. Once you've built a rough path using A* (or whatever), there are methods you can use to then smooth the path out a bit and get something closer to your blue line (which, you'll notice, doesn't follow the graph nodes but rather curves smoothly around a corner to reach its destination).

thnx, I also tought that it felt kind of overkill neighbouring every connected triangle, but I just wanted to be sure.

I also have a question concerning the density of the nodes. Right now I have few but big triangles, searching trough the nodes is fast .But on the other hand, even with the least amount of nodes, say three, the path won't be very, optimized, thare are lots of valid terrain that the player won't cross simply cause there is so few nodes.



I tought of using more triangles in the mesh, automaticly generating "better" paths even before smoothing them out. But after reading several articles it seems that a lot of effort to do the opposite is made, e.g everywhere it's posible to merge several nodes into one big you should do so.
Is it a better idea to improve the path with postprocessing, rather than adding more nodes to the mesh?

The standard approach (as far as I'm aware, at least) is to keep the number of graph nodes to a minimum, and then improve the path via post-processing if necessary.

The two approaches to path smoothing that first come to mind are line-of-sight based node reduction (fairly easy to code, quality of results varies) and string-pulling/funneling (harder to code, results are generally optimal - that is, the smoothing algorithm will return a perfect geodesic path).

Right now I'm smoothing the path by:


this is string pulling, isn't it?
the path i painted on the last picture is the result i would end up with.

Path Planning in Triangulations.
Efficient Triangulation-Based Pathfinding.
Efficient Triangulation-Based Pathfinding presentation slides.

Quote: Original post by HermanssoN
Right now I'm smoothing the path by:

*** Source Snippet Removed ***
this is string pulling, isn't it?
the path i painted on the last picture is the result i would end up with.

Right, sorry, you're already doing line-of-sight-based node removal (it's clear from your image - I just didn't notice).

I'm actually not sure what the 'official' definition of 'string pulling' is (or if there is an official definition), but what I was referring to was the 'funnel' algorithm for generating a geodesic path between two points in a (possibly non-convex) polygon.

Let's say that your agent was simply a point (i.e. no size). The (non-modified) funnel algorithm would return an 'idealized' path that, in this case, would go directly to the near end of the left bridge railing, follow the railing, and then head directly for the goal point. It sounds like this is more or less what you're after.

Of course in practice you'll want to take the agent's radius into account. There are at least two solutions to this problem that I'm familiar with:

1. Expand the collision geometry and use the 'unmodified' funnel algorithm.

2. Use the 'modified' funnel algorithm, which takes the radius of the agent into account (you'll also have to take extra steps to ensure that paths don't go through areas that are two small for the agent to traverse).

This can all get fairly complicated, but I've implemented a pathfinding system using the second option described above, and I can tell you that it does work. (It looks like xissburg posted some links to references that might be helpful.)

Yes, I roughly looked at the links and watched trough the slideshow, interesting stuff but quite complicated. I will definitely check out more about funneling.
btw, funneling is not a replacement for string pulling? (or what ever it's called) It's rather an extra step.
One thing i noticed from the links tough was that they placed the points/nodes on each edge rather than the center of each triangle.
It's getting late up here in Swedeen so I'l be sleeping on this.
Thank's a lot for your help guys.

Quote: Original post by HermanssoN
btw, funneling is not a replacement for string pulling? (or what ever it's called) It's rather an extra step.

No, that's not correct. The funnel algorithm and string pulling are different things, but they accomplish more or less the same goal.