1
\$\begingroup\$

Let's just say you have a massive world that isn't loaded into RAM all the time, and is streamed from the hard drive storage.

How would that world be stored on the hard drive? Is it serialised?

Let's say you have a serialised buffer which holds the data on the world, and you add an object or a component to something in the middle.

How would you do that in a way that doesn't require the entire buffer to be resized after that insertion? Or deletion?

\$\endgroup\$
4
  • \$\begingroup\$ Minecraft's world chunk format is publicly documented, which may give you one starting point. \$\endgroup\$
    – DMGregory
    Commented Feb 17, 2023 at 4:50
  • \$\begingroup\$ @Strom What if you place an object into the world. For example you drop an inventory item and now it's in the world. You want the world to maintain state, so you have to write it to the serialised buffer on the hard drive. Or an even better example you change a value of one of the components, and that item/entity is serialised in the middle of the array. \$\endgroup\$
    – Zebrafish
    Commented Feb 17, 2023 at 5:08
  • 1
    \$\begingroup\$ @Zebrafish I feel like this question is very open-ended. Different games implement features like this in different ways. Some games might hold the game world in memory, others might save chunks of the world that are far away into a file for long-term storage. Is this for a game you are making? \$\endgroup\$ Commented Feb 17, 2023 at 9:54
  • \$\begingroup\$ Yeah, an engine. I'm trying to figure out a solution to the problem that in a serialised data structure whenever you add or remove something to the buffer you need to resize the buffer (ie., move all the bytes back or forward). Since a game world can be massive we're potentially talking about moving hundreds of megabytes or gigabytes if inserting or remove an element from the buffer. So that's what I'm trying to figure out. \$\endgroup\$
    – Zebrafish
    Commented Feb 17, 2023 at 11:11

1 Answer 1

1
\$\begingroup\$

I know of at least one (proprietary) open world game engine that effectively stores its world contents as a database in the development version. These systems are made to support efficient insertions/updates/removals, without moving large swaths of the data around for each operation.

Loading a chunk of the world is then just a database query vaguely like:

SELECT * FROM worldObjects WHERE x >= xMin, x < xMax, y >= yMin, y < yMax

The trouble is, this is quite slow to load from when scaled up to millions of objects, so this was only done in dev mode (and all our dev machines had big fast SSDs to hide the inefficiency).

For players, we had a part of the build process that would do these slow database queries and bake their results out to an optimized flat file for each chunk of the world at a given level of detail. That way, as you approach a sector of the map in the released game, the engine can quickly find the file for that sector and load it in one linear pass.

So that shows two strategies you can use:

  • If this is just for development, or if the set of dynamic changes is small / short lived, consider a database system that supports random insertions and deletions out of the box.

  • For linearly-loaded data, don't store it all in one single file buffer, but divide it into separate files at regular spatial intervals. That way you can still randomly seek to a given zone by its file name, and if any chunk file needs to change in size, you have to modify only that one file, not the entirely of the world's map buffer "after" that point.

Elaborating on this, you can use the same strategies we use to support dynamically growing collections in RAM too:

  • The location of something in the data's byte order does not need to strictly map to its location in the world. To find stuff by location, you can construct a spatial lookup acceleration structure, like a quadtree, during load. That way, adding something near the "start" position of the map doesn't mean you have to move everything else's bytes down: you can add it at the end, and update your lookup structure to point to it.

  • Store the volatile parts separately from the long-lived parts. If you have a core terrain that doesn't change (often), put that part of the file first. Then adding/removing dynamic stuff only affects stuff close to the end of the file, not the whole layout.

  • Keep a little wiggle room: when you need to expand the container to hold a new item, don't expand it by just one slot, round up to a multiple. When you remove an item, you can leave a gap to fill later, rather than immediately vacuum-sealing the container to its minimal size. That way the next several adds are free, and you amortize the cost of resizing the container over many operations.

    This does waste some disc space, but your file system is likely allocating it in blocks of ~4kiB at a time anyway. You can fit a lot of game entities in 4kiB if you take that extra space all at once.

\$\endgroup\$
3
  • \$\begingroup\$ Let's just say you want to load a material from the hard drive, and you want to fetch with a string, the name of the material. The naive and simple way is to store each material as a separate file, you search the folder with the operating system using the name of the material as the filename. Or alternatively, have one serialised file, like say yaml, xml, json, whatever, and search with a string in that. The separate file for each material would have to be faster, wouldn't it? In that case why not just store everything in separate files? \$\endgroup\$
    – Zebrafish
    Commented Feb 17, 2023 at 14:45
  • \$\begingroup\$ There's some overhead to finding/opening the file itself. So usually games try to achieve some middle ground: they identify batches of assets that are likely to be used at the same time - say all the materials, meshes, textures, etc. for the "forest" biome - and pack them into one file. Then when you're approaching a map sector that contains forest, you can load the forest assets in one fell swoop, and unload the desert asset pack once no loaded map sectors are referencing it and you need the RAM space for something else. These bundles make better use of caching and linear read performance. \$\endgroup\$
    – DMGregory
    Commented Feb 17, 2023 at 14:54
  • \$\begingroup\$ I wouldn't rush to accept this answer too quickly. This is just a rough overview, and there's a good chance other users here will have other useful insights to share with you if you let the question sit for a day or two. Then you can accept the best answer that it's pulled in so far. \$\endgroup\$
    – DMGregory
    Commented Feb 17, 2023 at 14:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .