Jump to content
  • Advertisement
Sign in to follow this  
wildbunny

Tracking empty space in 2d

This topic is 2529 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

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?


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

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 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 :(

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

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.

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!



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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!