7
\$\begingroup\$

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.

\$\endgroup\$
  • 12
    \$\begingroup\$ 45 seconds is very slow to load a file. How big is this file exactly? \$\endgroup\$ – immibis Dec 6 '17 at 0:24
  • 3
    \$\begingroup\$ What kind of game is it, and what is stored in the levels? I could see different approaches work better for different kinds of games \$\endgroup\$ – phflack Dec 6 '17 at 1:26
  • 1
    \$\begingroup\$ Translating values is an expensive operation (as everything you load must be translated from a string to its real binary value). Have you considered using binary files instead? This also has the added benefit of making it hard for the player to make alterations to the file (but not impossible, given the appropriate skill and effort) \$\endgroup\$ – Flater Dec 6 '17 at 13:38
  • \$\begingroup\$ In what language are you working? XML parsers vary wildly in speed, so it may be as simple as swapping out your parser for a faster one. \$\endgroup\$ – Jack Aidley Dec 6 '17 at 14:37
  • \$\begingroup\$ The problem isn't the XML per se. The problem is in your development process, which is looking at the performance implications of architectural and implementation decisions far, far too late. Next time, set a performance budget early, build a performance test suite early, and do performance testing of proposed subsystems like serialization engines early so that you don't get in this mess ever again. \$\endgroup\$ – Eric Lippert Dec 6 '17 at 15:39
27
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hi, thanks for your reply! I am sure it is related to xml loading and i do really want to use xml. The thing is is that the file itself is loaded in 45seconds, or relatively fast. But then reading the parsed data and putting it in a array takes 12min, or way longer. So i would need a way of only reading the data wich i need, then those beginning 45 seconds and then an additional 2min approximately would be axeptable. But if i have to check every node for the right x and y cordinates i could aswell just load the entire file, \$\endgroup\$ – appmaker1358 Dec 5 '17 at 16:12
  • \$\begingroup\$ .....so i need a way to only read the nodes with the x and y within range. I think it should be possible as it takes a short time for the parser to internally parse the file. So Do you know a way to do that without having seperate files? \$\endgroup\$ – appmaker1358 Dec 5 '17 at 16:13
  • \$\begingroup\$ @appmaker1358 Is the time taken by the XML parser library included in the 45 seconds or the 12 minutes? \$\endgroup\$ – Philipp Dec 5 '17 at 16:15
  • 1
    \$\begingroup\$ To Philipp's point about storing chunks as separate files, Minecraft takes this approach. A middle ground would be to have 2 levels of subdivision. a Region file which contains data for 9 Chunks. You would load a Region file into memory, and parse and load the Chunks as needed based on th player location. In this way, at most you'll have 4 region xml loaded at a time (player standing on region corner) \$\endgroup\$ – Stephan Dec 5 '17 at 16:30
  • 3
    \$\begingroup\$ @appmaker1358 I think we need more information about how your XML file is structured. Please add that information to the question. Also mention how far you are able/willing to change the XML format if necessary. \$\endgroup\$ – Philipp Dec 5 '17 at 16:48
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ While this answer is correct, I think it's important to stress that this only gives a constant factor improvement. This is probably sufficient for appmaker1358's use case; as it would bring the load time down from 45s to something manageable. If the load time of the level map would be 450s, though, (e.g. in an Open World setting) this approach would not suffice, and the original idea of splitting up into chunks would be needed. Note that these ideas are complementary. The different chunks could even be part of the same file if it's in a parse-less binary format with explicit item lengths. \$\endgroup\$ – Thierry Dec 6 '17 at 13:34
  • 1
    \$\begingroup\$ @Thierry: Indeed. The nice thing with a binary (non-text) format where you have explicit lengths of everything is that you can just skip ahead a gigabyte worth of data if you know from the length that the stuff you want is there. XML cannot provide that. Assuming large enough address space (we're not quite in 32-bit-is-history land yet, but hopefully soon) you can even just map one single GB-sized file, and let the VM manager do the work. Touching pages a few frames before actually accessing them (worker thread) so the main thread never sees a fault, this works better than one would hope. \$\endgroup\$ – Damon Dec 6 '17 at 13:58
  • \$\begingroup\$ If you can live with an occasional small "hiccup" then you need not even worry about touching pages. Just map and forget. \$\endgroup\$ – Damon Dec 6 '17 at 13:59
  • \$\begingroup\$ We've seen almost 100x improvements in speed simply by switching parsers (from Python to C) which was extremely low hanging fruit (import a different module, change 3 lines of code.) In this benchmark, XML was almost twice (+84%) as verbose as JSON when storing the same data. Reducing it to binary would yield even better results. It takes me about that much time to load & parse files which are 4GB in size on disk (~21GB once loaded into python in RAM)... \$\endgroup\$ – TemporalWolf Dec 6 '17 at 18:48
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think i want stream loading and thus have several chunks of my world, but i would like them in a single file. Because parsing the entire file internally in the parser only takes a short time i only need a way to easely indentify wich node is what chunk. I need to do this without checking every node as that would make it take the same amount of time as directly loading every thing in. Could you help with that? \$\endgroup\$ – appmaker1358 Dec 5 '17 at 16:17
  • 1
    \$\begingroup\$ You can either break the file down into smaller segments of your world, or you can structure your nodes to make it more easily searchable. Its difficult to say which is best without seeing what you already have. \$\endgroup\$ – Stephan Dec 5 '17 at 16:40
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 1/2: Just a nitpick, but personally I would call things like 'processor cache size etc.' low-level, not high-level... perhaps these terms are used in opposite ways in different places? \$\endgroup\$ – bendl Dec 6 '17 at 17:11
  • \$\begingroup\$ @bendl I think I meant to imply that it's worrying and optimizing on the more specific / high end of the line. Changing it to low-level should imply the same and be more understandable, thank you \$\endgroup\$ – dot_Sp0T Dec 6 '17 at 17:13
  • \$\begingroup\$ 2/2: The example you give includes loads of repeats of the tag <section>. The loader has to load each of these into memory individually, so shortening all the tags to one or two letters will probably provide a significant speedup assuming there are a lot of tags. (See html tags) \$\endgroup\$ – bendl Dec 6 '17 at 17:13
  • \$\begingroup\$ @bendl shortening these to 1 or 2 letters might or might not have a miniscule impact on loading times, but writing out the word section instead of using a 2 letter string has major impacts on understanding the concept and associating it with something one already knows \$\endgroup\$ – dot_Sp0T Dec 6 '17 at 17:16
  • \$\begingroup\$ I agree completely! I only meant that that should be something the OP should consider, as it's a very cheap way to (possibly) cut back on a lot of loading time. Perhaps it should be left as a comment on the question, not on your answer. \$\endgroup\$ – bendl Dec 6 '17 at 17:19
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.