Motion planning without a graph across an infinite plane

Answer 1

I hear this called motion planning, and pathfinding (as mentioned above)

There are a lot of algorithms, but from your description, a visibility graph might be a good start. You have a graph with points A, B, and polygons around each point in C (you could also do it with circles by calculating tangent lines from each point, I believe). You calculate edges as potential paths between the points. Here's a slide show which explains it better.

Then, on top of the visibilty graph, apply a search algorithm like A* (a heuristic search) to find the most optimal path through the graph.

However, you should consider what you are looking for. The above approach will find a shortest path by sticking extremely close to all corners, but other algorithms might better fit your idea of optimality.

Answer 2

You could consider using potential fields. This offers a way to avoid "hugging the edges" of the obstacles.

But note that, like the A* algorithm, this requires that you quantize the state space, and may therefore be quite computationally intensive depending on how much accuracy you need.

Answer 3

I found a quite verbose description of a flocking routine on this page.

Use the separation rule for all obstacles, and alignment only towards the goal position (since we have no flock mates) and (for the same reason) ignoring the cohesion rule.

I wounder if that would yield the desired effect.

Answer 4

Also on the page you linked to in your answer is a pretty good discussion of steering behaviours in general.

In particular, look at his pages for containment and path following for good examples.

Steering Behaviors for Autonomous Characters