How can I speed up slow loading of big levels?

Question

I created a level loader that loads levels saved in an XML format. This means I am using an XML parser to read the levels. It works, but slightly bigger levels take too long to load. So now I am looking for a way to speed up loading. I don't need the whole file to be loaded at once, as the player can't see the whole map anyway, so partial loading would be fine.

I thought about a tile based loading mechanism where there are multiple parts of the map, and the loader only loads the part/tile where the user is standing. But I am not sure if that is a good idea.

Answer 1

First of all, you should measure where exactly the bottleneck is so you don't waste time improving things which are already good enough. The bottleneck could be any of these:

• Reading the XML file from the hard drive
• Your XML parser parsing it
• Your code which interprets the output of the XML parser and converts it into your internal data structures
• The loading of related assets (map tiles, etc.)
• Initialization of the game

But your question specifically mentions partial loading of map parts. So for the sake of this answer, let's assume that you did profile your code, found that reading and/or parsing the XML file is the problem and that partial loading is indeed the most obvious solution to your problem.

With XML-based file formats, this is usually not possible. A DOM-based XML parser will need to parse and validate the whole XML document before you can extract any data from it. A SAX-based XML parsers will at least have to read everything up to the node you are looking for. So if you want to allow partial loading, you will have to ditch the XML-based format and invent your own binary file format where map chunks start at known file positions you can selectively seek to without having to read the data in between.

When you really want to keep using XML, you could store each map chunk as a separate XML file.

Answer 2

Despite it being used for virtually everything, and despite it being used even in high-volume, low-latency applications, XML is an abysmal format for almost everything, but in particular for applications that have timely constraints, including games (except maybe for storing the game's settings). Even for live data, a simple binary tagged format which basically does the same as XML, just not human-readable (say, a 16-bit node type, 32-bit length, followed by contents), will be many times faster to read and write.

XML is tempting because it is human readable, and you don't need more tools than a text editor to write an XML file. However, it is also overly verbose, doesn't handle several types of data (binary data, large amounts of numbers, etc.) too well, and it takes a very non-neglegible time to process.
You can speed up parsing considerably by using a different parser, there are many alternatives (rapidxml, pugixml, whatever), however, that does not address the general problem of the format being overly verbose and human-readable to begin with.

While it is acceptable, and not even too uncommon, to use XML in one's production pipeline (though most people would rather use JSON or YAML), normally there is a custom-made tool that runs during the build process and that converts your XML files to a proprietary binary format which can ideally (not necessarily, but ideally) simply be loaded or memory-mapped as-is. No parsing whatsoever, just memory map, and set a pointer.
That same tool (or a similar one) will usually also read in other data such as e.g. textures which are stored in a variety of formats that may also be non-trivial to parse, and also put them into a binary game file in a way so they can just be mapped ready-to-go.
With the correct format, loading should be rather 0.45 seconds than 45 seconds.

Answer 3

There are a number of factors to approaching this problem, although you are on the right track.

Single Load

The first approach, as you've already tried, is to load it all at once. This puts all your load time and file I/O up front. As you've already noticed, as a map size grows, your initial load time can become annoying to the user. This also creates an upper bound on your maximum world size based on the minimum required memory of the target platform.

There are two other ways of handling this that I know of: you can chunk the world, and load them off screen as the player moves closer to them(stream loading); and you can have loading zones.

Loading Zones

Loading zones allow you to find a maximum chunk size that performs favorably, and subdivide your world into pieces no larger than that. When the player walks into a transit region (door, cave, map edge), some sort of transition graphic or animation takes place to distract the player. The new zone is loaded from the file system, while the old is saved and unloaded. This is a middle of the road approach. While it allows you to have worlds much larger than the memory capacity of the target device and puts all your I/O effort before the player is given control, this increases I/O operations over your initial approach. This can also break continuity of gameplay, which may or may not be favorable for the style of your game. The Final Fantasy series is probably the most recognizable for this type of approach.

Stream Loading

What I would consider the most recognizable example of stream loading is Minecraft. Chunks are loaded to and removed from memory as the player proximity changes. As with zone loading, stream loading removes the upper bound on world size as well. It also removes the interruptions of the loading effort from the user experience. However, this is the most file I/O heavy approach, as zones may be loaded and dropped from memory many times during a play session. Care must also be taken to load a zone at a closer proximity than they are removed from memory, in order to prevent a player repeatedly walking across a chunk boundary from burying the game in I/O operations. For 3D games, a method called doglegging is often employed which blocks the player's view of the area that is being loaded. This usually takes the form of a hallway with a turn in it, but can be any obstruction that blocks the player's line of sight.

Which of these approaches works best for your game is up to you.

Answer 4

Let's have a look at smart... what is smart exactly?

You state that you use XML as a format to store your levels. XML is a hierarchical format that is stored into a file. Thus we have 2 main factors that influence our loading times:

1. IO speed: That one is a hard constraint. You can't influence the reading and writing speed with your code. At least not too much. You can make use of things such as the processor cache size, etc. but that is low-level stuff and also different from computer to computer.

2. Your XML structure: This is where you can go wild. You can decide how you store things and what comes earlier, what later. You can even start grouping parts of a level into smaller datasets and then order these datasets in your big XML document, the earlier needed ones being closer to the beginning of the file.

So expanding on the second factor you could store your level in a format something like this:

<level>
    <name>Dragon Boss</name>
    <par-time>45</par-time>
    <sections>
        <section>
        ...
        </section>
        <section>
        ...
        </section>
        <section>
        ...
        </section>
    </sections>
</level>

Each <section> containing part of the level so it can be loaded one of these at a time.

Now that we've organized the format into something more useful the next step would be making sure that we can actually make use of this feature. One way is to load the whole file into memory, then breaking it down and only start parsing the level data after breaking it down. Thus you can load additional sections on demand without having to do all the expensive creation of textures, physics objects and what-not before you need them.

If your file is, for some weird reason, too big to load into memory then you could start using a SAX-parser instead of the DOM-parser you're likely using. The advantage of a SAX-parser is that it doesn't need to parse the whole file before you can work on it. It also reads and processes the file inherently different from a DOM-parser, so reading up on both might be good anyways.

---

Another topic that seems to boil up from your comments on other answers is that of organizing your data. You should in general strive to decouple your game logic from your game-data where possible. E.g. loading a level must not mean to read a file from the disc and create everything that is described in each line of the file. It might be (it actually is) better to, instead, store the data in an in-memory datastructure and then start working on that only where necessary.

Answer 5

Don't change your XML file if you find it a useful format for you to work with.

The trick is to keep the file you like but not have your game use that file directly. Write a simple routine (to run as part of packaging the game) to parse your XML into optimal chunk sizes to be loaded dynamically and at the same time create an index for those chunks that you can load into memory when your game starts.

As a very simplified example if your draw distance is .9km then each chunk file could represent a 1km square of your world grid.

Your parser splits your world into 1km square chunk files

In each chunk file have the parser add the filenames of the 8 chunk files adjacent to it, that way you don't need to hit the index to know which neighbours to load. Also add the top-left coordiate and bottom-right coordinate of the grid chunk so you can easily test if a players location is in that chunk

The parser then creates an index file by going through all the chunks storing chunk-file-name, top-left coordinate, bottom-right coordinate

Game loads, searches the index to find which chunk the player is in. Loads the chunk file, reads the adjacent chunk list from that chunk file and loads those chunks too. You now have 9 chunks loaded surrounding your player. As your player moves through the level if your players location goes beyond the current chunk then search the other loaded chunks for the chunk the player is now in. Use the new chunk's list of adjacent chunks to load the newly adjacent chunks and unload ones that are nolonger adjacent.

If the player moves ( teleports ) searching the loaded chunks to find out which one it is in will fail .. at which point you lookup against the index again

Answer 6

This is basically ignoring the suggestions about profiling your load time, evaluating file format complexity, etc. and is I see now a variant on Stephan's loading zones suggestion.

Consider if you had a VERY large level - like an MMO would have. Realistically you would not load the entire thing in one shot. Instead, you'd do it in pieces. Or load it at different levels of detail - low level detail (and probably thus smaller data files) for things far away, and only the high level of detail near the player.

So the approach would be something like this...

1. Break your level up into sections
2. Model these sections at different levels of detail - from very low detail which is sufficient for the player to view it from a long distance, and very high detail for where the player is.
3. Only load sections based on what level is required.
4. Dynamically load (and unload) sections as the player moves.

The assumption is that low level detail sections will load very very quickly, and high level will take more time.

This will help by allowing you to load just what you need, not everything. It also gives you some control over processor load, as you won't have to render or simulate fine details that are distant - only where the player is.

It's a generalized answer, but it's one that might work for you. It definitely is an approach for a very large level, but not really practical for a small one. Maybe your needs are somewhere in between and it will help.