Let's see if some ASCII art helps with what I'm thinking about:

Let's say for this example we can only move in cardinal directions.

6 intermediate nodes (Dxter calls these "cleared" nodes):

1.....2
   .
   3

...would be better than...

8 intermediate nodes:

1     2
.     .
...3...

...even though the number of steps found by A* is the same (10).

If we feed A* results into a MST and get: (1 -> 3 with cost 5, 3 -> 2 with cost 5),
we still don't know the best way to find the paths that share those intermediate nodes.

Yes,
A* will not be the right solution for my problem having multiple nodes. I need something for finding the shortest path between N points by reusing the same path. The whole thing can be imagined as a grid of obstacles, some are removable and some are not, and when you clear a removable obstacle, moving back on it has not cost. I was misled by the initial 2 point connecting task, that can work with A*.

I was misled by the initial 2 point connecting task, that can work with A*.

You're searching for the set of positions to take in order to reach the destination.

I need something for finding the shortest path between N points by reusing the same path. The whole thing can be imagined as a grid of obstacles, some are removable and some are not, and when you clear a removable obstacle, moving back on it has not cost.

You're searching for the set of obstacles to take in order to get a free path to all points.

A* will not be the right solution for my problem having multiple nodes.

I think you can, by seeing the initial grid as starting point, and the grid with free paths to all nodes as end-point, and in-between, grids with some partial fields taken out.

The branching factor is far beyond horrible though, and the estimate becomes an interesting problem by itself (although solvable by A*), so I am really wondering if this is what is intended :p

I have an idea for a naive single-pass solver that I'm going to try: Do Dijkstra's/wavefront/BFS traversal simultaneously starting at all of the waypoints. I suspect the optimal nodes will involve the 'ridge' that forms when wavefronts meet.

It's above my level (second year university), but I guess this is why I'm here :D . I will try Nypyren idea anyway, I understand that your solution involves starting the algorithm from all 4 points and when they meet it's the optimal path.

My concept appears to guarantee an optimal solution, BUT it's quite a bit more complicated than I'd hoped.

- Do a flood fill from each waypoint, tallying up cost-per-waypoint (distance) in each cell.
- Increment cost when you step FROM a non-free cell, rather than TO a non-free cell, to handle the case where some cells start cleared before traversal (just some disgusting nuance to the rest of the algorithm).

- After all four traversals finish, foreach cell, sum up its four costs.
- Find the cell(s) that contain the minimum of these sums (there will usually be more than one of these, but they are always contiguous). This is what I was calling the 'ridge' in my previous post, but it turns out it's not really a ridge at all once you see what it actually looks like.

- For each waypoint, find the cell within the minimum-sum-region with the lowest cost to "exit" the region towards that waypoint. Call these cells 'exit points'.
- Calculate the exit-to-exit costs by applying the same parallel-flood-fill concept, but limit traversal to the minimum-sum-region.
- Treat all eight cells (four exit points, four waypoints) as a graph and make an MST out of them using Prim's algorithm using the costs previously calculated in the flood fill.

It's instantaneous on the 8x8 examples above but would probably be pretty damn slow on game-sized graphs.

The flood-fill loop can probably be terminated the moment all four costs are available and the sum of the cell you would traverse into increases (which indicates your wavefront is exiting the minimum region).

I don't know if there's any way to use A*-style heuristics during the traversal.

Edge cases:

- The minimum-sum-region can contain one or more of the waypoints themselves. If this happens, those waypoints will effectively be their own exit nodes and you can just include them once in the graph that you feed to Prim's algorithm. This usually happens if the points are arranged in a rectangle with no obstacles between them. The resulting MST for the above algorithm if ALL points are within the minimum-sum-region will be the same as if you had A*-then-MST'ed them.