Data structures for a 2D multi-layered and multi-region map?

Question

I am working on a 2D world editor and a world format subsequently. If I were to handle the game "world" being created just as a layered set of structures, either in top or side views, it would be considerably simple to do most things.

But, since this editor is meant for 3rd parties, I have no clue how big worlds one will want to make and I need to keep in mind that eventually it will become simply too much to check, handling and comparing stuff that are happening completely away from the player position.

I know the solution for this is to subdivide my world into sub regions and stream them on the fly, loading and unloading resources and other data. This way I know a virtually infinite game area is achievable. But, while I know theoretically what to do, I really have a few questions I'd hoped to get answered for some hints about the topic.

1. The logic way to handle the regions is some kind of grid, would you pick evenly distributed blocks with equal sizes or would you let the user subdivide areas by taste with irregular sized rectangles?

2. In case of even grids, would you use some kind of block/chunk neighbouring system to check when the player transposes the limit or just put all those in a simple array?

3. Being a region a different data structure than its owner "game world", when streaming a region, would you deliver the objects to the parent structures and track them for unloading later, or retain the objects in each region for a more "hard-limit" approach?

4. Introducing the subdivision approach to the project, and already having a multi layered scene graph structure on place, how would i make it support the new concept? Would you have the parent node have the layers as children, and replicate in each layer node, a node per region? Or the opposite, parent node owns all the regions possible, and each region has multiple layers as children? Or would you just put the region logic outside the graph completely(compatible with the first suggestion in Q.3)

5. When I say virtually infinite worlds, I mean it of course under the contraints of the variable sizes and so on. Using float positions, a HUGE world can already be made. Do you think its sane to think beyond that? Because I think its ok to stick to this limit since it will never be reached so easily..

6. As for when to stream a region, I'm implementing it as a collection of watcher cameras, which the streaming system works with to know what to load/unload. The problem here is, i will be needing some kind of warps/teleports built in for my game, and there is a chance i will be teleporting a player to a unloaded region far away. How would you approach something like this? Is it sane to load any region to memory which can be teleported to by a warp within a radius from the player?

Sorry for the huge question, any answers are helpful!

Answer 1

First off - don't overengineer. Just build what you feel is necessary.

Large parts of your question seem to orbit around "how to handle huge worlds". From a quick search, I found several questions on gamedev.sx that may help you:

• How to handle a huge map?
• Huge procedurally generated 'wilderness' worlds
• What are the techniques used to save space with very large levels?
• Help streaming resources (maps, sounds, music, etc) from many files for contiguous world
• When to unload graphics object from main memory?

I'll briefly go through your points:

The logic way to handle the regions is some kind of grid, would you pick evenly distributed blocks with equal sizes or would you let the user subdivide areas by taste with irregular sized rectangles?

KISS. If you have no reason not to do so, keep things simple - an even grid is easy to address.

In case of even grids, would you use some kind of block/chunk neighbouring system to check when the player transposes the limit or just put all those in a simple array?

Simple array. It should be trivial to know which four "tiles" of the world are closest to the player.

Being a region a different data structure than its owner "game world", when streaming a region, would you deliver the objects to the parent structures and track them for unloading later, or retain the objects in each region for a more "hard-limit" approach?

Assuming everything isn't unique in the world, I'd keep a cache of resources and would free them on a LRU basis after some predetermined limit was exceeded. It's likely the player will walk in circles and will see the same resources again soon, so no point in unloading stuff right after it's no longer in active use.

Introducing the subdivision approach to the project, and already having a multi layered scene graph structure on place, how would i make it support the new concept? Would you have the parent node have the layers as children, and replicate in each layer node, a node per region? Or the opposite, parent node owns all the regions possible, and each region has multiple layers as children? Or would you just put the region logic outside the graph completely(compatible with the first suggestion in Q.3)

I'd keep each "subregion" as it's own "world".

When I say virtually infinite worlds, I mean it of course under the contraints of the variable sizes and so on. Using float positions, a HUGE world can already be made. Do you think its sane to think beyond that? Because I think its ok to stick to this limit since it will never be reached so easily..

Actually, you can't make a huge world with floats. You'll hit float's limits fairly soon (same goes for doubles).

Since floats are most accurate around the origin, you need to have a "moving origin".. basically I'd have two coordinate systems: one "local", for a "tile", where everything are simple floats, and one "global", integer coordinates which are offsets of tiles. Then, let's say if one tile is (-1000,1000), the integer coordinates would be in steps of 2000.

As for when to stream a region, I'm implementing it as a collection of watcher cameras, which the streaming system works with to know what to load/unload. The problem here is, i will be needing some kind of warps/teleports built in for my game, and there is a chance i will be teleporting a player to a unloaded region far away. How would you approach something like this? Is it sane to load any region to memory which can be teleported to by a warp within a radius from the player?

Fade out, fade in. Teleportation is a special event. Add some cool special effects to hide the fact you're preloading.

Or alternatively do special cases through scripting. When teleport object is loaded, it's loader script tells the resource manager that tile X is probably needed soon.