Sign in to follow this  
suliman

Pathfinding A* pathfind - shortcuts in gridbased-paths?

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

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[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 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
4 hours ago, IADaveMark said:

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 this post


Link to post
Share on other sites

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 this post


Link to post
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 this post


Link to post
Share on other sites

With string pulling what about this problem:

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Partner Spotlight

  • Forum Statistics

    • Total Topics
      627686
    • Total Posts
      2978635
  • Similar Content

    • By povilaslt2
      Hello, I'm trying to implement enemy pathfinding algorihtm, but i have problem with empty tile collision when moving enemy to node.
       
      For example this image shows how it should move like shown in example:

      But it stucks at last tile:

       
      It happens because enemy collides with right side of "air" tile and then it removes from node list because it "collided", but it works with not "air" tiles of course. How do fix this problem?
      Code:
      void Enemy::generateMoveToNode(AStar::Vec2i lastNode) { auto lastSave = AStar::Vec2i{ 0.0f, 0.0f }; while (!target.empty()) { if (target.back().y == lastNode.y) { lastSave = target.back(); target.pop_back(); } else { moveToNodes.push_back(lastSave); moveToNodes.push_back(target.back()); generateMoveToNode(target.back()); return; } } moveToNodes.push_back(lastSave); } void Enemy::updateTarget(std::shared_ptr<InputManager> inputManager) { if (moveToNodes.empty()) return; // Calculate half sizes. float halfWidthA = getSize(0) / 2.0f; float halfHeightA = getSize(1) / 2.0f; float halfWidthB = 32.0f / 2.0f; float halfHeightB = 32.0f / 2.0f; // Calculate centers. auto centerA = glm::vec2(getPosition(0) + halfWidthA, getPosition(1) + halfHeightA); auto centerB = glm::vec2((moveToNodes.front().x * 32.0f) + halfWidthB, (moveToNodes.front().y * 32.0f) + halfHeightB); // Calculate current and minimum-non-intersecting distances between centers. float distanceX = centerA.x - centerB.x; float distanceY = centerA.y - centerB.y; float minDistanceX = halfWidthA + halfWidthB; float minDistanceY = halfHeightA + halfHeightB; setKey(inputManager->getKeyBinding("Move Left"), false); setKey(inputManager->getKeyBinding("Move Right"), false); setKey(inputManager->getKeyBinding("Jump"), false); setKey(inputManager->getKeyBinding("Duck"), false); // If we are not intersecting at all, return (0, 0). if (abs(distanceX) >= minDistanceX || abs(distanceY) >= minDistanceY) { if (moveToNodes.front().y > ceil(getPosition(1) / 32.0f)) setKey(inputManager->getKeyBinding("Jump"), true); else if (moveToNodes.front().y < ceil(getPosition(1) / 32.0f)) { if (getCanClimb()) setKey(inputManager->getKeyBinding("Duck"), true); } else { if (moveToNodes.front().x < ceil(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Left"), true); else if (moveToNodes.front().x > floor(getPosition(0) / 32.0f)) setKey(inputManager->getKeyBinding("Move Right"), true); } updateInput(inputManager); return; } // Calculate and return intersection depths. float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX; float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY; updateInput(inputManager); moveToNodes.erase(moveToNodes.begin()); } generateMoveToNode: recursive function to generate all nodes.
      updateTarget: updates enemy every frame to check if it hits node and then removes it from list and checks next till no nodes left.
    • By Crayz92
      Here are the two main files:
      Path: https://pastebin.com/ZkrbJ78t
      AStar: https://pastebin.com/EVGazFtU
       
      A few things I've done to optimize the search:
      1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y).  Objects have F,G,H and Parent fields, these fields are reset to default values during each search.
      2. Cheap weighted heuristic
      3. Orthogonal neighbors (searching 4 neighbors rather than 8)
      Paths don't have to be beautiful because the point reduction smooths them out quite nice. 
      In Path.cs you can see the two functions to reduce points, Incremental and Stretch.  Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners.  The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. 
      Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable.
       
      My grid is dynamic and roughly 250x250.  I tried out Theta* and JPS, both were slower than my current A*.  I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code
    • By lucky6969b
      When my program was generating navigation meshes for my geometry, and the extent is 5000x5000 (m), with a cell size of 5.0 meters, it has to generate 250,000 cells, which makes my computer halt, the target object is a truck, which has a radius of about 20 meters, should I give the cell size a value of 20, because I don't really want to use this navigation mesh on one type of vehicle only. I want to use it for vehicles like cars, which has only about 5 meters in radius... the generation speed is a problem while the memory consumption is another.
      Any ideas how to improve this?
      Thanks
      Jack
    • By Jesse "Chime" Collins
      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
      Download as an .fbx or .dae
      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
      The ability to download Control-rig scripts
      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.
      To download, sign into your (free) Adobe account at the Mixamo website and start downloading. Developers have only one week left to grab as much as they can. For a complete FAQ and how-to for the Mixamo massacre, check out the Adobe post from their Customer Care Team.
      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. 

  • Popular Now