Pathfinding A* pathfind - shortcuts in gridbased-paths?

Recommended Posts

suliman    1652
Posted (edited)

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?

Edited by suliman

Share on other sites

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.

Share on other sites
Nanoha    2682
Posted (edited)

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.

Edited by Nanoha

Share on other sites
Nypyren    12065
Posted (edited)

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 on other sites
Kylotan    9877

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 on other sites
suliman    1652

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[i] and p[i+2]
if you can go directly between p[i] 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 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 on other sites
alvaro    21247

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 on other sites
Nypyren    12065
Posted (edited)

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 you posted but did not see any mention of any-angle pathing.  However I could see how it might be extended it to any angle pathfinding if you allowed more than 8 jump links per node. (i.e. links to all visible intersection/corner nodes).  I looked at the source code and I don't see anything about any-angle support.  Do you have a specific spot where an any-angle implementation is mentioned?

Or did the example he gave in the video just happen to align with 8-direction, and the four diagonals are actually allowed to be any diagonal direction?

Edited by Nypyren

Share on other sites
ferrous    6137

Something to mention is that Jump Point Search only works on Uniform cost grids.  So if you have mud tiles that cost more to traverse than road tiles, or whatever, it won't work.

Share on other sites

You are correct Nypyren -- my bad. At that point, of course, stringpulling and similar are your solutions. An LOS check up the next nodes on the path list until one fails is the simple explanation. Then you just steer towards the last one you can see.

Share on other sites
suliman    1652

I pathfind first. The path it finds prefers road and avoids forest and swamp. But when i start string pulling the found path it will not take terrain cost into consideration. It will find a walkable shorter line shortcutting diagonally over the swamp but it might be slower if the terrain is slower. Right?

Share on other sites
Alberth    9508
3 hours ago, suliman said:

I pathfind first. The path it finds prefers road and avoids forest and swamp. But when i start string pulling the found path it will not take terrain cost into consideration. It will find a walkable shorter line shortcutting diagonally over the swamp but it might be slower if the terrain is slower. Right?

Yes. You should verify that the cost does not increase when you change the path.

I never did stringpulling, but since you know the exact old and new path (I assume), you can easily calculate costs, and they should be equal. (If the new path has higher cost, it's a worse path. If it is lower, your pathfinding is broken.)

Share on other sites
suliman    1652
Posted (edited)

But the whole point is that I pathfind on a strict gridbased map, and when I string pull I remove nodes so that there is still a walkable path, even though that walking will not be strictly ON nodes (i will cut over the nodes in various angles making walking look less rigid).

When units walk they check the walking speed from whatever node is under them right now. You mean I should do this ("walk" along the new path by incrementing position and check the total travel time) when stringpulling and only remove a node if the new "path" will be faster? (the walking cost CAN and should be lower since the pathfinding only finds paths using "whole nodes" and with stringpulling I will find "other paths" See the pic i posted in the first post.).

Edited by suliman

Share on other sites
Alberth    9508

Hmm, I am not sure you should compute the cost of the new path in a different way than you did previously in the grid-based pathfinding stage. It may create all kinds of subtle changes in costs if you do it wrong. (Eg since your new path is subtly cheaper, code may pull the string a bit into the swamp, right until all your cost reduction has been eaten by the swamp.)

A somewhat safer method is to still use the grid-based costs, but use the new path to decide which grid-elements you visit.

Share on other sites
suliman    1652
Posted (edited)

But if the path is not going strictly across the middle of the nodes in the grid (which is the entire point of this thread) I must use that method right? It's still based on the cost for each tile (the tile has a terrain-type, which translates to a movement cost)

Edited by suliman

Share on other sites
Kylotan    9877

String-pulling/funnel systems assume that there is no difference in the passability or quality of a path between the 2 points in question. This isn't the case for you, so you can't use it. (You didn't mention movement costs in the first post.)

Obviously you can't easily compare grid-based movement with continuous movement. The path you find across a grid is based on the assumption that you follow the grid. If you're not following the grid then you're not using the path!

It's not even practical to hack this; a naive approach might be to examine the string-pulled path and see how fast it is compared to the regular path, but you'll have to calculate how much of the path crosses each square, consider whether the unit can fit there based on adjacent blocked tiles, etc.

Share on other sites
suliman    1652

Could I not just compare the travel cost between:

1. node p and p[i+2] (stepping along all 3 nodes)
2. node p and p[i+2] (stepping along a straight line from the two outmost nodes)

both using the calculation method for continuos movement?

Share on other sites
Kylotan    9877

If you look at your initial graphic you'll see that it's not as simple as that. You would have to be able to compare a grid-based path of N nodes against a straight line route of 1..N nodes, where you have to perform several calculations on the straight line route to see how much time it spends within each grid square. It's not impossible but it is quite awkward. And it no longer guarantees that the final route is the shortest, because you've added a large number of alternatives - i.e. different 'string pulling' choices - which you're not comparing against each other.

Share on other sites
suliman    1652

Ah I see... Yes seems complicated.

But what is the normal way to do this? I mean games like banished has ( I assume since the game is grid based) grid-based pathfinding in the bottom, but units can "cut" diagonally over open fields ("continous movement", not zigzagging over perfect tile-centers). And it has terrain cost (road tiles are quicker and units prefer those).

Share on other sites
ferrous    6137

You might be able to fudge it and pretend it's a grid based path.  You might get funny results now and then, but it might do a good enough job at avoiding horribly slow tiles and staying on fast tiles.  Would require testing.

Otherwise, you probably have to do something like what Kylotan said, get the tiles under the line, find how much of the line is under each tile, do a cost * length calculation for each tile.  Hopefully your units aren't super thick, or it becomes more like casting a rectangle / capsule and doing tiles under that, which gets uglier.  If you're a city builder and it's tiny little people, you can probably get away with a single ray.

Share on other sites
suliman    1652

Yes my units are single-point entities

Create an account

Register a new account

• Similar Content

• 3D Rigger Mixamo Is Making Some Changes
Originally founded in 2008, Mixamo has been a go-to source for 3D animation and rigging for nearly a decade. On August 28th, 2013, Mixamo launched a platform called Face Plus. It was designed to allow developers or animators turn facial expressions recorded with even a webcam into top-notch 3D animation. This is not unlike what Holotech Studios’ “FaceRig” does for streamers and video creators as well.
Back this past May 2017, Adobe (publishers of the Mixamo platform since 2015) announced the end of an era. Mixamo’s Face Plus will be removed on August 22nd, 2017, as well as several other free features.
According to the Adobe post on the Mixamo website, they lay out what is changing and what is staying the same.

Set out as bullet points in the post, they seem to be cleaning house on the “free” features. But, they are keeping a small handful of their main key points, such as:
Select and use characters from Mixamo’s Character Collection
Upload 3D characters to get them ready to animate using the Auto-Rigger
Apply animations to characters
Noticeably, the list that’s getting 86’ed includes major tools and the ability to save assets from their site:
The ability to save and retrieve assets in “My Assets”.
The Face Plus facial animation plugin
The Decimator polygon reduction tool
Download types for .bvh and .biped that streamline integration with 3rd party applications
Mixamo forums will close and all help articles will be moved to Adobe’s HelpX
Don't Worry! There's still time!

They’re allowing people to still download the tools and plug-ins until August 22nd, as well as utilizing their easy-to-download features of saving Assets directly. Those that use Mixamo, utilize Face Plus, or even just do animation are highly encouraged to take advantage and download the tools for the next week.
UPDATE (8/15/17): Adobe would like to stress that Mixamo, itself, is not going anywhere, just the Face Plus features, the tools mentioned above, and a couple other features to make the platform more "streamlined and a little modernized". Once the dust is cleared next week from the changes, I'll reach out to Adobe from a more guided tour of the new set-up. Additionally, I have changed the title of this article to reflect the clarification. Apologies for the inconvenience to those that have already read the article.

• By suliman
Hi
In a game like stronghold with many workers going back and forth from a workplace to a dropoff-point for example, would I store the path and then use it backwards to not have to redo pathfinding all the time? If the moving units in the city doesnt block movement, very often I could just reuse the old path. Only if i run into a wall (if the player constructs a new building in the path of the old workers) will I recalculate the path.
Workers in old age of empires for example, do they pathfind every time they go back to drop off gold in the storage?
Thanks!
Erik

• Hi, I was reading Game AI Pro how they implemented Supreme Commander path finding and came to one question.
For the integration of cost field they are using Eikonal equation for traversing the areas.
They recommended Fast Iterative Method and it's parallel version for solving this equation.
However in all basic tutorials of flow field navigation that I found  for integrating of the cost field is used simple grass/brush fire algorithm.
My question is what would be the difference if they used in the game just grass fire algorithm?
I guess the reason was some quality/performance trade of.
Fortunately the Fast Iterative Method is very easy to implement so I can compare the performance, but what I don't understand is, what is the "quality" benefit.

• 9
• 11
• 21
• 26
• 17