Jump to content
  • Advertisement
Sign in to follow this  
EdvardDumansky

Best method to store huge worlds?

This topic is 2679 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

Hey everyone!

I've recently started some initial work on a platform style game (much like Terraria) and have come across a bit of an issue. The main attributes of the world is that it will need to be procedurally generated, massive in size and comprised of destructible blocks which are 20 x 20 pixels in size. It will also take inspiration from Dwarf Fortress as I'd like to have NPCs which move around your world collecting resources, exploring, etc.

Using Game Maker I've been able to create a little mock up which generates random blocks, deactivates all blocks not immediately visible to either the player or NPCs, and then activates all blocks within a certain range. This runs much better than having every block in the map active at all times, but the code has to go through and check every possible block at every step to see where they are in relation to the player/NPC. This one piece of code makes the game crippling slow, so I'd hate to think what will happen once advance AI is added to the mix.

What would be the best method to store such a massive amount of game data so that it is easily retrievable if/when the player/NPC needs it? I'm an overall programming noob so examples or tutorials of implementation would be tremendously helpful as well.

On a somewhat related note, would anyone be able to tell me if Game Maker is even able to handle a game of such massive scope? If not, are there any recommendations as to what I should look into?

Share this post


Link to post
Share on other sites
Advertisement
You generally break the world up into large chunks. For example, for a world that is 100 km x 100 km, you might decide to only have a 5km x 5km square loaded with the rest on disk to be loaded behind the scenes as a player moves. So, your 5km x 5 km chunk can be represented as small chunks, say . . . . 1/4 km x 1/4 km and those can be divided smaller if you wish. Then, when you do your checks you can exclude large chunks if there are no npcs within them or what ever criteria you decide is best.

But, I want to stress the fact of using a chunksize that makes sense. Do not attempt to store different sized chunks or do anything fancy for any reason, you will create a pain for yourself. When it comes to handling large worlds, consistency will lead to better results and less headaches for you.

Share this post


Link to post
Share on other sites
Thanks for the reply.

I should have thought of chunks earlier, having played Minecraft which has a similar scope in world size. The concept is understandable, but I'm really not 100% sure about how I'd go about it in Game Maker. The most likely option seems to be the use of grids. If I understand correctly, the game needs to generate grids as the player gets closer to them, either procedurally if it's an unexplored area or loading them from the file if they've already been there. When the grid is outside of a specified range around the player it saves and then deletes itself, freeing up the memory it was using.

Am I on the right track or is there something I'm overlooking?

Share this post


Link to post
Share on other sites
That is pretty much the basics of it. You have an area that the viewer never sees, which is like your staging area where you load from the disk and prep any data so when the user can see it, you already have it loaded. Then, you just drop the old stuff.

So, try to make your grid larger than your viewable area, and just swap around the data. You will get it.

Share this post


Link to post
Share on other sites
not sure if your tool supports it but memory mapping files can give a significant boost when working with serialized data

Share this post


Link to post
Share on other sites
Randomly saw this on a search, so:

Your basic problem is that your algorithm for checking blocks is (to use a technical term) O(N), or in other words, it takes an amount of time proportional to the number of blocks there are, so your execution time will scale up linearly with the number of blocks.

A solution to this is to use a hierarchal tree-like data structure. Basically, you split your world in half along each dimension, so if it's a 2D world, you split it into quarters. Then you split those quarters again into quarters and so on until you can't split the world up any more because each quarter is then an individual block.

Now it's a much cheaper job to find out which blocks are closest to any given entity, because you start by finding which quarter of your entire world is closest to the entity, then which 16th is closest to that player and so on. On the very first step of this sort of algorithm you immediately discount 3/4 of the world in one go.

This sort of algorithm is known to be O(logN), so it's proportional to the log of the number of blocks, i.e. a world of 10000 blocks only takes twice as long as a world of 100 blocks, not 100 times as long as it would with the naive algorithm which inspects every single block.

Share this post


Link to post
Share on other sites
Hi!
I'm not saying this is the best way, although it is an interresting approach, and I'd definately give it a try.
The idea is not to actually store the world, but to use your procedural algorithm to make up the world as you go. For a tile-based 2D-world, this shouldn't be a hassle at all.
Cache all the blocks in an "active zone" and throw everything else out. You'll end up with an (in theory) infinetely big world, while using only the memory required at each given frame.
The trick is to come up with a deterministic algorithm (i.e The same input always generates the same output), and "index" your algorithm with the x/y-values of the tile you wish to generate.
Happy fishing!

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!