I use a "flood fill" pathfinding for my mobile RTS.
(where I need fast calculations, for many units)

Its a bit similar to A*, but it has no heuristics.

Here how it works:

I have a gridbased level, with passable and inpassable areas.
(works with node-based pathfinding too)

When the pathfinder receives the target position (x,y) for
the units to go, it creates a new topographic map.

This map starts from the taget position, and
checks all neighboring squares (up to 8).
Each passable square receives a value of how many steps
where taken to reach it (the first ones get a 1 naturally,
the one in the next iteration a 2)

Each square is marked, and put on a working list.

Now for each square on the list, check its neighboring passable
squares.
If the field was not visited before, or has a higher! stepcount,
overwrite it, and give it a stepcount of my-stepcount+1,
and put it on the following workinglist.

---

As long as there is a non-empty workinglist continue.

When no more squares get added, the algorythm is finished.
it should result in a topographic map, that fills the
whole playfield with a kind of "roll down" topography
at its passable squares.

Now, every unit on a passable square can easily determine
the next best square to got to, to get closer to the taget.

(just choose the suare with the lower stepcount from
the current square.
Its like letting a marble roll down-hill towards
the goal.)

-----

This way you can let hundrets of units find the path to
the target, doing just one pathfinding run.

And: even if they block each other, you can
let them find the way without a need to rerun the
flood-fill run.
(they raise the value of previously visited suares,
making them "higher")

Damocles, thank you for describing this pathfinding method. Actually I've never thought about something that, even though it's pretty straightforward.


You could do a search for "vector field histogram". However you'll most likely find articles about robotics then. I don't know whether or how it's used or called in game AI development.

The math behind it shouldn't be that complicated as it may seem at a first glance. I'm definitely not much of a mathematician, so I must know. : )

For projecting the obstacles (I assume a 2D world to make it more simple) I would treat each obstacle as a spherical bounding volume. I then would compute the two tangents to each bounding volume through the ship's center. The tangents define the light brown areas depicted in the image of my previous post. Depending on their angles, the tangents can be assigned to corresponding array indices. The distance to the obstacles can be stored in the array indices accordingly.

For your space game you would most probably want to add a third dimension to this method, of course. This could be a bit trickier, though, as simply computing two tangents for each obstacle wouldn't be sufficient anymore. Perhaps you could just project the bounding volumes onto a plane that is orthogonal to the ship's viewing direction instead. In order to find the most promising direction for avoidance you could (for example) rasterize the plane to get a two-dimensional array and then apply the clearance algorithm to it (as shown in the previous post). Just as an example. Perhaps this is too overkill or unnecessarily complicated. ; )

I'm not sure whether I understood your problem b) correctly. But maybe it was already addressed above?


To dwell a little bit on the potential field method that was already mentioned in this thread, you also could influence your ship's velocity by adding attracting and repulsing forces (which is probably very similar to your original idea?). Asteroids would naturally repulse all ships while nodes placed between the asteroids would attract them. However, a ship would only be attracted by a node whose range is at least as large as the ship itself.



Note, that these forces should only influence a ship's velocity. Nodes behind a ship can be ignored.
Presumably it requires some trial and error for tweaking the forces. It also requires a method for placing the attractor nodes properly (perhaps by placing a node between each pair of asteroids?). Each asteroid could store pointers to the adjacent nodes. So whenever a ship encounters an asteroid on its way, it could check whether it gets attracted by one of the nodes in the asteroid's node list.

Edit: Of course you could also connect each pair of nodes with line of sight to generate a small waypoint graph. Then you could go without the attracting/repulsion forces and a ship would never be steered into a dead end.