I think this is something that can get overly complicated really quickly. Would knowing where the existent islands' bounds are be sufficient info to tell you where they also are not? How often are your updates?

I apologize...as I oversimplified


Having reread your post :

[color="#1C2837"]users can edit the map[/quote]

Throws a nasty wrench into the spokes.

I'll see what I can dig up

good luck.

You could use a quadtree. It's a good structure for representing non-uniform density, which seems like it applies to your task.

When adding a new island, start from the top of the tree and choose random child nodes, splitting them as you go. Each node that splits should notify it's parent of the split, which in turn notifies the parent of that node, all the way up to the root. This information is useful when deciding where to add islands. It's easy to determine the density distibution of your world - If a node has children then there's at least one island in it's child nodes. So when adding new islands, you can favour branching into nodes that are not yet split, or have fewer (recursive) splits than others.

If you assume the islands are points, you could do something like: for a given query point, find the three closest islands and then calculate the circle that passes through those three points. If you sampled the world along a grid, the grid point whose query results in the largest circle would be the "most open" point on the map.

Of course, I'm not sure if you can adjust the "circle through three points" formula into a "circle tangent to three circles" so that each island can be represented as a non-zero-area region of space. Also, obviously sampling on a grid isn't going to find the optimal position

Actually, your Voronoi Diagram idea is probably better -- if the islands are points and you generate a VD, *I think* the point in the world furthest from all islands should be located at a vertex on the VD (i.e a point where two or more VD edges meet). I can't prove this but it makes sense intuitively. Anyway, you then need to figure out how to adjust for island size -- this should be simple to do when generating the VD if you treat the islands as circles (i.e use their bounding circle). So, generate the VD and then iterate over the vertices looking for the one furthest from its supporting points. Points on the boundary of the world might have to be treated differently/ignored though.

Of course.. I think that explicitly generating a VD is a hard problem. Almost all the papers I'm aware of use sampling/rasterization to approximate the VD (e.g http://www.iquilezles.org/www/articles/cellularffx/cellularffx.htm )rather than building an explicit model of it, and I would assume that there is a good reason for this.

There was a video presentation a year or two ago from some demoscene party that was about modelling shapes using intersecting spheres -- basically 3D Voronoi Diagrams -- that I can't find right now, but it might have some ideas. Sorry I can't find it or even remember a name/title

sorry, a concise version:

IF the position farthest from a point is at a vertex of that point's Voronoi Region in the Voronoi Diagram (I'm not sure of this, it's conjecture)
THEN the position farthest from any point must be a vertex of the Diagram. So generate the VD and search for the vertex that's furthest from its neighboring voronoi-region-points (I think, according to the definition of the VD, vertices must be equidistant to all the points that are generating the regions that neighbor the vertex)

Also, when generating the VD there's a way to weight the points so that they model circles (i.e points in a voronoi region are closest to the circle that generated that region). So you could use bounding circles to model the space occupied by the islands.

Maybe this is a bit weak... sorry!

Cover the world with a triangle grid whose side is the initial separation between players. Islands are seeded from nodes on that grid. Islands can only be seeded from nodes which are linked to an already occupied node. When you seed from a node, you add its neighbouring unoccupied nodes to your free list.

When land is created, you fill in a map somewhere. But you also fill in a continental shelf some extra distance around each bit of land; it's not rendered, it's just a marker.

So, you pick a random node off the free list. Go to the map, check the position of that node. If the position is occupied by land it's a reject. If it's occupied by continental shelf it will be too close to an existing player. Reject it and remove it from the list. Repeat until you find a free one.

When you get a free one, add its unoccupied nodes (checkable by looking at the map) to the free list, seed your island from that point. And remove that node from the free list.


Why triangles? Less noticeable than squares.


You'll need a sparse map representation -- for which a quad tree is ideal.