Hello!

I'm looking for some help regarding circle-based waypoint generation, preferably a flood/seed fill approach. Actually I'm gonna use sphere-based waypoints, but I think it'd be rather easy to extend from 2D to 3D. Any tips?

Thanks!

So, basically you want to be able to generate a path between two points along the surface of a sphere?

Well, no. What I meant was that each waypoint node has a radius that represents the walkable area, see image:
http://i252.photobucket.com/albums/hh9/PaulTozour/Stormwind_circles.jpg

Why not pathfind on the graph whose vertices are the circles, and in which an edge exists IFF the two corresponding circles intersect? Then you just need a controller that can get an agent from anywhere in one circle to somewhere that it intersects with another circle (maybe descending the gradient of an appropriate potential).

-- EDIT ---

Oh, I see your question. You want to know how to place the circles to begin with! I'll post back if anything springs to mind. You might want to google "geometric coverage problem" and related terms. Some variant of Lloyd's algorithm might be worth looking into, or simpler interaction-force-based methods...

You could always place the circles by hand.

1. Create uniform distribution of points.

for (x=-20; x x < 21; x++){  for (y=-20; y < 21; y++){    for (z=-20; z < 21; z++){       SetPoint(x,y,z) // You could kill points that don`t make sense.    }  }}

2. create springs/links to each nearby spheres
3. apply pressure to spheres
(start to grow spheres (hard pressure to sphere shrinks it and
springs try to keep everything in order)
4. you are ready: spheres are distributed, size of each sphere is set and links are made.

/Tyrian