next »

[tiktokbob]

So I have a simple path finding demo set up on a 2D grid using A*; I have one question and one interesting bug.  

The question ... in a strategy game when a unit is selected, typically the available range of movement is shown for the selected unit.  The idea of scanning every single map tile to see if it's within range and accessible to the unit seems pretty inefficient; granted you could limit it easily by distance but even then you're doing a lot of A* work.  If a unit has a movement range of 6 then that's 6 squares in every direction which is 168 squares (if I'm not mistaken?) to each run A* on.  Is there a better way?


The bug ... a picture is worth a thousand words ... I'm not entirely sure why A* has chosen a longer route here?  I've tried to reproduce this with different, but similar, layouts and I am not able to.  

[PompiPompi]

Err, yea A* is kind of a greedy algorithm, there are other faster versions of it like fast marching, sweaping and etc. Don't remember exactly.
You can make A * more efficient if you keep a map(2D array) in which the algorithm marks how many steps it took it to reach that cell. And if the A* reach the same cell from another direction, it can stop this search because it's already marked as visited with fewer steps.
You can also limit the A* algorithm to an allowed number of steps.
About the bug, that's what you have a debugger for, heh...

[Rob Lach]

just step through the alg's decisions with a debugger

[tiktokbob]

Err, yea A* is kind of a greedy algorithm, there are other faster versions of it like fast marching, sweaping and etc. Don't remember exactly.
You can make A * more efficient if you keep a map(2D array) in which the algorithm marks how many steps it took it to reach that cell. And if the A* reach the same cell from another direction, it can stop this search because it's already marked as visited with fewer steps.
You can also limit the A* algorithm to an allowed number of steps.

Thanks for the suggestions, I will have a look at fast marching, sweeping and play with some optimisation. 

About the bug, that's what you have a debugger for, heh...

For sure!  I just thought it might be something to do with A* rather than my implementation of it as I've read that at times A* does not always chose the best route and someone may have seen similar behaviour before.

[PompiPompi]

You probably don't need to optimize it that much, I just mentioned thre are faster algorithms.
But you can use the 2D Map to not make the fast marching algorithm have an insane complexity order. Because if you implement it the most straight forward way it will travel the same places many times, eventhough you already found a shroter path.

[randomnine]

A* will find the shortest route unless you implemented it incorrectly. You've got some bugfixing to do. Don't worry about optimisations until you've got it working - it should be finding the path you've indicated.

If a unit has a movement range of 6 then that's 6 squares in every direction which is 168 squares (if I'm not mistaken?) to each run A* on.  Is there a better way?

You don't have to run A* for each square. You just have to do something like A* once, flooding out to touch every square within six steps of the starting position. Use a flat heuristic (so the 'distance to the goal' is always assumed to be 0), ignore all nodes with costs greater than 6 and you'll hit every single node the unit can reach in a single pass.

[tiktokbob]

A* will find the shortest route unless you implemented it incorrectly. You've got some bugfixing to do. Don't worry about optimisations until you've got it working - it should be finding the path you've indicated.

Well as it happens, it's fixed, by fixing an apparently unrelated bug.  I am some what confused by the interaction between the two and at some point I'll take a closer look at what was happening.

You don't have to run A* for each square. You just have to do something like A* once, flooding out to touch every square within six steps of the starting position. Use a flat heuristic (so the 'distance to the goal' is always assumed to be 0), ignore all nodes with costs greater than 6 and you'll hit every single node the unit can reach in a single pass.

That makes a lot of sense, thank you!

[tiktokbob]

A* will find the shortest route unless you implemented it incorrectly. You've got some bugfixing to do. Don't worry about optimisations until you've got it working - it should be finding the path you've indicated.

In association with this:

Reading this description, you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target "as the crow flies." This isn't the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an "inadmissible heuristic."

Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short.

Taken from: http://www.policyalmanac.org/games/aStarTutorial.htm

I realise this is an issue with using Manhattan distance than A*, but worth bearing in mind for corner case debugging where it's being used.

[Dacke]

Err, yea A* is kind of a greedy algorithm, there are other faster versions of it like fast marching, sweaping and etc. Don't remember exactly.

I just thought it would be good to put a little extra emphasis to what randomnine said.
A* is not a greedy algorithm. It is in fact guaranteed to give an optimal solution, as long as you use a heuristic that never-never-ever overestimates underestimatses the distance left to travel. The heuristic should only give the exact distance left or underestimate overestimate it.  (Which, as tiktokbob pointed out, is not true for the Manhattan distance. But this is really easy to fix.)

But it's actually even better than that! A* is guaranteed to give an optimal solution while at the same time looking through the lowest number of states possible (given a specific heuristic). So once you have decided to use a specific heuristic for estimating the distance left to travel, you can never-ever-possibly outperform A* (if you want to find the optimal solution)

edit: Fixed a horrible error where I mixed up overestimation and underestimation

[ham and brie]

It is in fact guaranteed to give an optimal solution, as long as you use a heuristic that never-never-ever underestimates the distance left to travel. The heuristic should only give the exact distance left or overestimate it.

I think you've typed the opposite of what you meant. The heuristic should not overestimate the cost left.

[ekun]

It is in fact guaranteed to give an optimal solution, as long as you use a heuristic that never-never-ever underestimates the distance left to travel. The heuristic should only give the exact distance left or overestimate it.

I think you've typed the opposite of what you meant. The heuristic should not overestimate the cost left.

Indeed. A pathfinding heuristic function is admissible only if it doesn't overestimate the cost.

Common heuristics used are euclidean distance, and Manhattan distance (in the case where movement is restricted to the four grid aligned directions).

[Dacke]

Whoopsiedoopsie!
Thank you for pointing out my error

[PompiPompi]

Hmm, I think you can do better than A* and still get the optimal solution.
There is this 4 directions sweaping algorithm... I don't recall.

[Dacke]

Given that the assumptions inherent to A* hold true for a specific problem, it is theoretically impossible to outpreform it when it comes to exploring as few nodes as possible (= as few squares as possible in a grid). A few years ago I could probably have recited the mathematical proof to you, but I forget

A* is also optimally efficient for any heuristic h, meaning that no algorithm employing the same heuristic will expand fewer nodes than A*, except when there are multiple partial solutions where h exactly predicts the cost of the optimal path. Even in this case, for each graph there exists some order of breaking ties in the priority queue such that A* examines the fewest possible nodes.

...

But if you have a problem where A*'s assumptions are false, you can do better. For example, A* only goes from point A to point B once. But if you are running a game where new enemies keep spawning all the time (and they all want to go to B), you may be better off with something like Dijkstra's algorithm. Dijkstra's algorithm can also be a superior choice for a racing game, where you can pre-compute the best route to the goal from every point on the track.

[Dacke]

Use a flat heuristic (so the 'distance to the goal' is always assumed to be 0)

That makes a lot of sense, thank you!

I just noticed this!
A* with heuristic=0 is another name for Dijkstra's algorithm