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

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.

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

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

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  

  • Forum Statistics

    • Total Topics
      628288
    • Total Posts
      2981843
  • Similar Content

    • By Luqman Ibrahim
      Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.
       
      The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer. 
       
      I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!
       
      https://goo.gl/forms/S0etAlAAHL6S5kTI2
    • By baabaa
      Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
      Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
      So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
      Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
      If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
      Any thoughts?
    • 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
  • Popular Now