Jump to content
  • Advertisement
Sign in to follow this  
suliman

Pathfinding A* pathfind - shortcuts in gridbased-paths?

This topic is 435 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

GCYQhQe.jpg

Edited by suliman

Share this post


Link to post
Share on other sites
Advertisement

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:

polygon-navmesh-faces.png

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.

Edited by Nanoha

Share this post


Link to post
Share on other sites

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*.
Edited by Nypyren

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

 

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!