# Pathfinding A* pathfind - shortcuts in gridbased-paths?

## Recommended Posts

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

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

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

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

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

2nd link in my post is his code on Github.

##### Share on other sites
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

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

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

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

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

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

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

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

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

Yes my units are single-point entities

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628288
• Total Posts
2981843
• ### Similar Content

• 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?

• 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

• 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

• 11
• 10
• 10
• 11
• 17