Saving entire maps

ID:1315878
 
Jul 6 2013, 1:28 pm
For a new game I'm working on, I need to save/load the entire game map. After brainstorming for a bit, I came up with a great way to do this. I convert every tile into a pixel and save it as an image, effectively creating a minimap in the process. Every object (that can be placed on the map) has a matching rgb value in a list. Here's an example of some of it:

var/list/MapConversions=params2list("\
    #592c00=/obj/Block/Wood&\
    #663300=/obj/Block/Dirt&\
    #009900=/obj/Block/Grass&\
    #909090=/obj/Block/Stone&\
    #0066ff=/obj/water&\
    ")


When I save the objects that need more information, such as direction or icon_state, I just add an alpha value to the rgb and "decode" it when it loads. It ends up being very very fast, saving a 300x300 map (90,000 objects) in 1 second and loading that same size map in under 10. I am going to be using huge maps (3,000x3,000 or so) so I am going to need to be able to access all that information quickly.
Here's a little snippet of the map loader:
//"map" is a reference to the image file being loaded
for(var/X in 1 to map.Width())
    for(var/Y in 1 to map.Height())
        var/T=map.GetPixel(X,Y)
        var/turf/TURF=locate(X,Y,1)
        for(var/obj/OLD in TURF) if(OLD.x==X&&OLD.y==Y) del OLD
        if(copytext(T,1,8) in MapConversions)
            var/PATH=text2path(MapConversions[copytext(T,1,8)])
            var/obj/O=new PATH(locate(X,Y,1))
            SpecialLoadCase(O,copytext(T,8))

It basically just scans over each pixel of the map image, and loads the corresponding object to whatever that pixel is. Making the rgb-object association list is a bit of work, but I think its worth it to have a super fast proc.

Screenshot of the save/load time:
Image and video hosting by TinyPic

Any comments/thoughts/ideas?
Jul 6 2013, 1:33 pm
For loading the giant map, I am gonna load the map in chunks as the player(s) move around, instead of loading the entire map at once. For a 3000x3000 size map, loading it all at once could take over 15 minutes, so that is definitely out of the question. I think that loading chunks 100x100 at a time would work without causing crazy lag
Jul 6 2013, 3:25 pm
In response to Gunbuddy13
From my understanding of how computers work, saving and loading small chunks of a map would actually be slower than simply saving/loading it all at once.

Fair enough, a small chunk will save/load faster than the entire map, but at the end of the day you're saving/loading the exact same amount of data either way, but using small chunks brings up an issue with the way hard drives and computers work in general. I don't know the technical details behind it, but it's just faster to have one large file than it is a lot of smaller ones.

Probably wont make a major difference with small maps like 3000x3000, but the more files there is, the slower it will go.
Jul 7 2013, 2:18 am
It isn't faster to just save the types down?
Jul 7 2013, 5:50 am
I'm confused. Are you actually saying that it's faster to use icon procs to convert the map's atoms into pixels and save them as an image, than it is to just save the instance locations as text? If this is true, then it changes everything! There's only one explanation I can think of as to why this would be the case. The data would be getting compressed into a format that's natively designed for saving coordinates, and since this happens within the RAM, which has a very fast read and write speed, this will ultimately result in less work needed to save it to the hard drive. I don't know if this theory is correct though, because it still seems unrealistic to me.

The Magic Man wrote:
From my understanding of how computers work, saving and loading small chunks of a map would actually be slower than simply saving/loading it all at once.

That may be, but I think the concept here is that you would be "buffering" the map data from the hard drive in such a way that the player never notices any loading at all. I think the ideal way to do this would be to have 2 or 3 map chunks loaded at a time, so that when the player covers a certain distance of a map, the next chunk is loaded, and the previous one unloaded. The map chunks should be long enough that the player is unable to cross them before the time it takes to finish loading the next chunk, that way the player never notices anything, since the loading map would always be beyond their view.

It really makes no sense at all to load an entire map, when 95% of it will go completely unused for the time the game is being played, and it will just take up rediculous amounts of RAM. No player will want to sit there and do nothing for 15 minutes while the map is loading anyway, and I wouldn't blame them if they quit.

The goal when it comes to making an efficient game is to balance the amount of CPU and RAM that is used. With most procs, what you have to worry about is the CPU, and it generally results in more speed and efficiency if you can trade more of that CPU usage for RAM. Store more and process less! This rule generally only applies to procs. In the case of things like very large lists, you will want to sacrifice some CPU to manage that before it takes up too much RAM. Process a little and store a lot less! The same is the case with huge maps. If you can manage them just like you would lists, then you will end up with far more efficiency than you would have otherwise.

Fair enough, a small chunk will save/load faster than the entire map, but at the end of the day you're saving/loading the exact same amount of data either way, but using small chunks brings up an issue with the way hard drives and computers work in general. I don't know the technical details behind it, but it's just faster to have one large file than it is a lot of smaller ones.

Probably wont make a major difference with small maps like 3000x3000, but the more files there is, the slower it will go.

It's true that when data is spread out across a hard drive, rather than in one place, it will be slower to read it. There is a name for this. It's called fragmentation.

Every file that is created within a file system exists as its own separate fragment. If for some reason, there is empty space between different files, but one space isn't enough for a single new file, then that one file must be split up into separate fragments in order to successfully place it in the file system. This is the problem that defragmenters fix, by consolidating the fragments of each file into a whole, which is done by relocating the files on the hard drive. However, this problem is much less significant than it once was, because hard drives are so much faster now, but even then, the fragments will still exist as long as the file systems write files in the way they currently do.

The point here is that saving the map chunks as separate files would create separate fragments, so yes there might be some loss of speed from the file system needing to check separate locations for the map chunk data, but this is some pretty technical stuff that most people probably wouldn't care about. Either way, I think this particular issue, if it is an issue, could be mostly eliminated by saving and loading maps to and from the DMI format. Each map chunk image could be saved to a separate icon_state within the icon, and in this way, the hard drive will still see the whole thing as one single file, which would hopefully remain in one whole fragment as well.



Anyway, I had thought about doing something like this in the past, but I just figured it would end up being very slow, and be a waste of effort. Even then, it surprises me that no one has tried to implement this before. The first advantage that comes to mind is that you could open your map image in any image editor, and literally edit the map from there, or even make whole new ones!

Unsurprisingly, this creates a lot of feature creep. You could expand the image parsing methods to support things like tile "gradients". What this means is that in image form, there would literally be color gradients, and when the image gets converted to an actual map, the gradient values could be interpreted as a large range of icon_state values. There are all sorts of ways of doing things like this, but ultimately, if you can automate the formation of maps from extremely complex images, then you can create some unbelievably awesome worlds!
Jul 8 2013, 6:50 am
In response to Multiverse7
It really makes no sense at all to load an entire map, when 95% of it will go completely unused for the time the game is being played, and it will just take up rediculous amounts of RAM. No player will want to sit there and do nothing for 15 minutes while the map is loading anyway, and I wouldn't blame them if they quit.

The way BYOND works means those parts of the map are always using RAM. Even if they're empty of everything, they exist and use RAM.

Also, I believe the topic title was "saving entire maps". So it's not unreasonable that the person wants to save an entire, massive map. Whether it's done in one huge chunk, or lots of small pieces, it's going to take a very long time to save a very big map.
Jul 8 2013, 7:18 am (Edited on Jul 8 2013, 7:30 am)
In response to The Magic Man
The Magic Man wrote:
The way BYOND works means those parts of the map are always using RAM. Even if they're empty of everything, they exist and use RAM.

You are misunderstanding something. How does "saved to the hard drive waiting to be used" == "taking up RAM"? This process involves a lot more than just saving and loading the map's contents. The size of the real map in game would only be equal to a few screens in size and would never change. The whole perceived map however could be thousands of times larger than that. I am assuming that the OP has implemented some kind of "conveyor belt" type system, where either the entire map's contents is moved around dynamically, or there is a z level parsing system that simulates this effect. I think you were overlooking this point. In this way, the map is dynamically loaded and unloaded as the player moves around, and the total amount of RAM used never actually changes. 99% of the map will always be stored on the hard drive, not taking up RAM. I hope this makes sense.

Also, I believe the topic title was "saving entire maps". So it's not unreasonable that the person wants to save an entire, massive map.

I never really said it was unreasonable. I am just wondering if using images is really the fastest method to go about it.

Whether it's done in one huge chunk, or lots of small pieces, it's going to take a very long time to save a very big map.

While it would take the same amount of time to load a map as a whole or in chunks, you seem to be making the assumption that you would actually want to load the entire map during the time the game is being played. Unless someone can beat your whole game with a gigantic map in just a few minutes, you probably don't need to load the whole thing at once. Just unload the map as they go, while they are playing the game. The old areas will be unloaded, and the newer ones will be loaded. We don't literally want to load the entire map all in one go while someone is just going to play one level. That's insanity!
Jul 9 2013, 1:16 am
Saving the map into an icon would be a generally bad idea, it would take more space than it should, consider it that the icon is an image file *.png in fact, it has to stores the pixel color into a list as you would in any other way.

Something like this.
var/map[maxx][maxy]=list(red,green,blue,alpha) //A list of 4 values 0-255, unsigned char data type. 4 times 1 byte.


It will have to save every single bit of data, if you want to reduce the amount of space used you can just go with
var/map[maxx][maxy]=anyNumber //When using values 0 to 65535, it would be 2 bytes.


You can assign each object or turf a specific number, which it translates into, instead of using the slower and more space using alternative, you can go with a list, which only contains the minimum data required.

PS! I am aware that the list calling doesn't exactly work that way, just making a point.
Jul 9 2013, 3:14 am
Yes, that does make more sense. Loading and saving should be much faster that way. It would be almost the same as the native *.dmm format.

This is why I'm wondering what the motive would be for the OP to implement this using pixel colors instead. I suppose that if you wanted a minimap in your game, in addition to the actual map, then there might be some advantages to using a color coded method, such as reusability within the procedures. Also, as I mentioned before, you could make maps using any bitmap editor, although you could probably just convert the numbers to colors using a separate utility, so that wouldn't really be an incentive. Whatever gets the job done with the highest efficiency possible should be the way to go.
Jul 9 2013, 3:38 pm
looks like terraria