TIGSource Forums

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

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?

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.

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.

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.

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.

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.

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.

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.

That makes a lot of sense, thank you!

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.

Thus we see that the formulation presented uses one function, h, to embody in a formal theory all knowledge available from the problem domain. The selection of h, therefore, permits one to choose a desirable compromise between admissibility, heuristic effectiveness, and computational efficiency.