Hi

I have a A* gridbased pathfind for a city builder I'm planning (think banished or stronghold).
Units can walk in 8 directions from each tile. But I want more free movement. Look at the example pic below. The pathfind finds the path in step 0 to 19.
But now I want to "simplify" the path so the unit goes straight from node marked 0 to 10 (and obviously also from 12 to 19; i forgot to mark this in the picture).

Any good algoritm to "reduce" the path in this way? I understand I need to check if there is a unbroken "line of walk" between two nodes but if i start with checking 0 to 1, 0 to 2, 0 to 3 until i find that 0 to 12 doesnt work and stop there (so I throw away nodes marked 1 through 8) this would be VERY slow.

Any idea?

It should be all about heuristics used and tie-breakers.

Visit Amit Patel's site about pathfinding, there's tons of options considered, with many examples. Here's one of related links: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties , see pic in Diagonal distance section.

https://qiao.github.io/PathFinding.js/visual/ is a nice online demo to quickly try a broad set of algorithms and heuristics. try a* with euclidean heuristics and a very low weight, like 0.001, allowing diagonals and one-directional. or try the non-orthogonal JPS, it produces visually pleasing paths.

I haven't tried this myself but right now you have a navigation graph. Each cell is a node and you find a route through those nodes. Instead of having nodes, you could form a navigation mesh as in this image:

This will depend on your heuristic, is a shortest path the fewest nodes or is it the shortest distance travelled? Given your regular structure you could dynamically alter and merge cells as new buildings/blockages are added which should result in more direct movement as you want and also make future path queries faster too. Those huge open areas could be merged together into few large polygons instead of many small squares.

In the image you have you could merge all of that into just 5 polygons with an algorithm.

JPS+ (or better)

http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than

https://github.com/SteveRabin/JPSPlusWithGoalBounding

I've interpreted the original question differently than all of the other posters.I believe you're asking about allowing "any-angle" paths (allowing continuous movement in arbitrary directions, not just 4 or 8 directions between cells).  None of the previous responses are applicable to any-angle pathfinding.

For a quick example, see Figure 1 in the following page: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

The options I know of are:

1. Find a path using the grid, and then use "string pulling" to straighten segments of that path.  You will not get an optimal path using this approach, though, and it can be slow to perform something that tries to be close to optimal.
2. Start with an "any-angle" algorithm such as Theta*.  The stock implementation is slower than A*, however it may be possible to employ clever optimizations that are similar to JPS+ to an algorithm such as Theta*.

Sounds like you're looking for "string-pulling" and "funnel" algorithms. Do a search on those terms (including "navmesh" or "pathfinding", for better results).

String-pulling seems really simple to implement, i'll start with that and see if it's good enough

For reference, this is what I found (it's Kylotans post from 2009):

Quote

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

Depending on simplicity of the "check if you can go directly" function, this may get slow if I redo it every time I pathfind.

Ii'm making a city builder/simulation so there is many little guys going back and forth between the same locations, so I will maybe need to save paths for them (this was another thread I started but didnt think about string pulling or similar techniques for smoother the paths once found).

So no one read my post on JPS+? That's the standard way for not only allowing any angle movement but reducing the complexity of the search space so that your pathing calls are faster to begin with. Seriously... watch the vid with Steve Rabin.

I watched the video on JPS+ and goal bounds. It's really interesting and I could probably reproduce it from the level of detail given in the talk, but it would be challenging.