Sign in to follow this  
wildbunny

Tracking empty space in 2d

Recommended Posts

Hi guys,

The game I'm working on has a 2d world map with lots of islands in the sea, the islands are bounded by AABBs - as each user joins the game, they get given their own little island on the map in empty water.

The problem I'm having is how to efficiently (both speed and space wise) track empty areas in the sea so I can dish them out to new users - it would be easy except that users can edit the map and expand their islands.

Anybody have any pointers or suggestions? I was thinking maybe voroni regions or something, but not sure if that's a great fit...

:)

Cheers, Paul.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
[quote name='RetLee' timestamp='1310829030' post='4836014']
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?
[/quote]

Not quite sure what you're asking :) But the updates are whenever a user decides they want to make new land/shrink old land...

Cheers, Paul.

Share this post


Link to post
Share on other sites
I apologize...as I oversimplified


Having reread your post :
[quote][color="#1C2837"][size="2"]users can edit the map[/size][/color][/quote]

Throws a nasty wrench into the spokes.

I'll see what I can dig up

good luck.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 [url="http://www.iquilezles.org/www/articles/cellularffx/cellularffx.htm"]http://www.iquilezles.org/www/articles/cellularffx/cellularffx.htm[/url] )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 :(

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
[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.


[/quote]


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.

Share this post


Link to post
Share on other sites
[quote name='raigan' timestamp='1310879931' post='4836257']
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!
[/quote]


Hi Raigan,

Thanks for the suggestion - I'll have to do some digging to see how difficult VDs are to generate :)

Cheers, Paul.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
[quote name='wildbunny' timestamp='1310896871' post='4836302']


[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.


[/quote]


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.

Share this post


Link to post
Share on other sites
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 [url="http://en.wikipedia.org/wiki/Largest_empty_sphere"]largest empty circle[/url] 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 :)

Share this post


Link to post
Share on other sites
[quote name='raigan' timestamp='1310994412' post='4836783']
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.
[/quote]

My grid is currently 2000x2000, so it is quite huge... I'm considering whether I can alter the game-play and get around this empty space problem that way! :)


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this