A-star: heuristic for multiple goals

Question

Let's consider a simple grid, where any point is connected with at most 4 other points (North-East-West-South neighborhood).

I have to write program, that computes minimal route from selected initial point to any of goal points, which are connected (there is route consisting of goal points between any two goals). Of course there can be obstacles on grid.

My solution is quite simple: I'm using A* algorithm with variable heuristic function h(x) - manhattan distance from x to nearest goal point. To find nearest goal point I have to do linear search (in O(n), where n - number of goal points). Here is my question: is there any more efficient solution (heuristic function) to dynamically find nearest goal point (where time < O(n))?

Or maybe A* is not good way to solve that problem?

Answer 1

First, decide whether you need to optimize, because any optimization is going to complicate your code, and for a small number of goals, your current solution is probably fine for a simple heuristic like Manhattan distance.

Before taking the first step, compute the heuristic for each goal. Remember the nearest goal as the currently selected goal, and move toward it, but subtract the maximum possible progress toward any goal from all the other distances. You can consider this second value a "meta-heuristic"; it is an optimistic estimate of the heuristic for other goals.

On subsequent steps, compute the heuristic for the current goal, and any goals with a "meta-heuristic" that is less than or equal to the heuristic. The other goals can't possibly have a better heuristic, so you don't need to compute them. The nearest goal becomes the new current goal; move toward it, subtracting the maximum possible progress from the others. Repeat until you arrive at a goal.

Answer 2

Use Dijkstra's algorithm, which has as it's output the minimal cost to all reachable points. Then you just select the goal points from the output.

Answer 3

How many goals, tens or thousands? If tens your way will work fine, if thousands then nearest neighbor search will give you ideas on setting up your data to search quickly.

The tradeoffs are obvious, spatially organizing your data to search will take time and on small sets brute force will be simpler to maintain. Since you're constantly evaluating I think that structuring the data will be worthwhile at very low numbers of points.

An alternate way to do this would be a modified flood fill algorithm that stops once it reaches a destination point during the flood.