[quote name='taz0010' timestamp='1310835544' post='4836042']
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.

Hi there,

That's an interesting idea - presumably because we want to identify empty space you'd need to keep splitting a quad-tree node with an island on it until a certain minimum size threshold is reached?

The only thing which worries me slightly is rebuilding the quad-tree every time someone adds some new land!

Cheers, Paul.


[/quote]

For the same of simplicity I'd store each island at the maximum preset depth for the tree. And the size of the deepest node would correspond to the unit size, or minimum block of land a player can possess. So we're not talking about dynamically optimising for node distribution or anything like that. Nodes are always split into 4 equal parts. Most operations on this sort of structure are in O(log(n)) - adding a new node, determining if a neighbour is occupied (worst case log(n)), and deleting islands.

Unless your world is huge, in 2d I doubt that you'll need the size savings of a quadtree enough to justify the complexity of implementation compared to e.g a grid.

It's not like the quadtree itself is going to answer your query directly any better than a grid or any other spatial database -- large empty regions *may* be represented by large unsubdivided nodes, but they might also not be depending on the position of islands wrt the quadtree bounds. So all you're getting is an accelerated distance query, which a grid or AABB-tree or any other structure could do just as well.

Looking into it a bit more, the Voronoi Diagram is definitely the "correct" solution; from Wikipedia, "With a given Voronoi diagram, one can also find the largest empty circle amongst a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city." The entry for "largest empty sphere" claims it can be found in O(n log n) but it's not clear whether this includes the construction of the VD.

See http://www.cs.swarthmore.edu/~adanner/cs97/s08/papers/schuster.pdf

But the best thing to try initially might be to just brute-force it: sample the world in a grid or something looking for the point where the (squared) distance to the closest island is maximized. You might also want to take distance to the world bounds into account. You could also try some sort of hierarchical refinement: sample using a very coarse grid, then subdivide the "best" cell into a grid and recurse. If you only have a few dozen islands then just testing vs all of them isn't going to be too bad.

Or, add a bit of style -- rather than the islands being fixed, give them large over-inflated bounding circles and collide them against each other with soft response to "relax" their positions until they all settle into a configuration where they're equidistant from each other