Condensing of Levels

Performance Tuning
#1

Hello, everybody!

Lately, I’ve been trying to condense my levels into compressed files that sort of encapsulate everything about them, including their tile information, the world objects within, anything pertaining to quests, etc. As of right now, I only have incorporated tile information because I haven’t quite gotten the other aspects solidified in the engine to where they are ready to be hard set into the level specs (world objects are coming along, but it’ll be a little bit yet). But I digress!

Basically, I wanted to compare my methods to all of yours. Before, I was storing my level files as .png images where all of the tile information was thus very visible and fairly condensed (I find .png files are pretty tiny most of the time). However, this is somewhat ungainly for my game, as a .png can’t by itself encompass things like world objects, chests with their contents, data for liquid bodies, NPCs, and so on and so forth. Thus, I figured I would develop a level metafile that contains all of this information similar to how, I guess, Doom would store their files or whatever other example fits.

Down to process and numbers:

Step One: Convert the map to Unicode so that it can be stored in a file as a character matrix, with each character representing a relevant tile from the game engine.
Step Two: This could encompass multiple steps, but essentially this is where everything else pertinent to the level gets stored besides the tiles (i.e., world objects, liquids, quest information, NPC information, etc.).
Step Three: Convert the Unicode map and other information to a compressed “.lev” file using ZipStream. Not elegant or fancy, by any means, but it works.

Using the aforementioned process, I get about a 15-20% smaller size of the level than I would have with .png images comprising them, and not to mention the benefit of encapsulating the level’s information to boot, which will probably augment the file by maybe another 5% at most, considering the sheer bulk of the files will be the tile information.

I’m not sure if this process is exactly the most efficient or best, and would love to know of what you guys have done or what you would recommend! I’m open to all sorts of suggestions and would like the best for my level data! Thanks for all your time! :]

Best regards,
Colton

#2

Storing tile information is probably going to be highly inefficient in and of itself unless it’s little more than ‘Passable/Impassable’, ‘This collision profile’ and ‘This tile sprite/visual representation’. If you’re storing any other information, then you might want to see what you could pull out and store separately (Especially if multiple maps end up making use of basically the same information).

#3

Oh no, there isn’t anything about the tiles being stored other than their visual information, basically (that’s what I meant when I described the character matrix as each character being equivalent to one of the engine’s tiles). For example:

AAA
AAA
ABA

Would just basically mean that all A tiles are “dirt” tiles and B is a “stone” tile (for example’s sake). Anything else in the level’s metafile is basically going to be about macroscopic level features, like what objects are stored within it at what coordinates, which items are stored in what chests at which spots, and so forth. “Passable/impassable” functionality is coded into the engine and is relative to the tile, so it’s just calculated at runtime.

#4

Well then, I don’t see your files being completely tile based information, (Say 100x100 is just 10k characters, and you could probably condense that considerably by limiting the number of tiles and then do some fancy masking when you load it).

Figuring out how you’ll store data like item lists for certain tiles, enemy positions and the like will probably end up costing you a lot more (Position + item ID at the very least for each item on the screen). I mean, maybe not a large amount of the file, but most likely in excess of 5% of the total data you’re going to be storing (This statement is less true if your maps are going to be highly sparse).

However, how large do you see all of these levels being? And how many do you think you’ll have? Further, how much conversion back is going to be needed to make them easily/quickly parsed by your game’s engine? Figure out of the trade offs there as well (I mean, I don’t mind 200kb per 1mb of bloat, but I’ve gotten to the point where I glare in offended silence at long loading screens. Not that I believe that it’d end up with one, but really, you might be worrying about file sizes too soon.)

#5

so you have like two types of data

  • the level layout which is like a image
  • meta/object data

For the layout/tile data you can use simple compression on binary data.

  • give each tile type an ID
  • choose the smallest datatype to store the IDs, like if you won’t have more then 255 types a single Byte is fine
  • save the level layout as a i.e. byte array
  • then you an compress the shit out of it :slight_smile: like with LZMA, or build your own Huffman encoding^^

The other things like your game objects(NPC, cheast…) or meta data(time for level, level name …)
can be saved with normal serialisation(ByteStream, XML, JSON …)

In the end pack everything together in a Zip file and you are finished

#6

If you’re interested in getting your map size as small as possible, why are you storing them in a text/ascii based format and not binary (and then compressed)?

Although to be honest I’m not sure that optimising levels for storage size is a worthwhile use of time. Storage space is cheap these days unless you’re going to have humongous levels.

#7

Well, the levels are procedurally generated. At this point, the hugest size world one can generate creates roughly 30,000 levels. These levels aren’t actually instantiated and specified until the player ventures into them, at which point it will make the level and save it and all that; before this, nothing except the name of the level will exist on disk. If the user really wanted to, though, they could spend a very long time exploring the world and thus instantiating all of these levels. The levels themselves can also grow to be fairly large, hypothetically, though I haven’t a solid idea of just how big they will be at maximum because not everything is implemented yet, though I can make rough estimates; I highly doubt levels will exist over a meg in size.

Enemies will be instantiated at runtime, so that stuff won’t be involved in the level files. Item lists will be stored for chests, and I’m not altogether sure just how much this will add to the file, though I’m willing to wager not an incredible amount.

It’s not strictly about sizes; I’m also concerned about loading times as well. That’s why I offered why I was choosing the implementation I am, in case anyone knows of a more sensible way of storing information in a way that will load and remain on disk efficiently; it would seem that having to parse less information to achieve similar results would involve less computation, and since worlds can hold so many levels, it makes sense to me that the data should be compressed so the game doesn’t take up a huge amount of space.

I am interested in what you mean by using fancy masking to condense the tile information! Thanks for all your other advice, as well. I suppose I could have elaborated a little more on my game and its levels and so forth :stuck_out_tongue:

Wow, that sounds tantalizing! I’ll have to look into all of that! I’m not sure yet if there will be less than 255 types of tiles (I hope so!), but if there are, then that sounds like a nice route! Thanks!

Well, to be honest, I’m not altogether sure how to go about compressing levels in binary format! If you could offer me a reference source for such a thing or offer some more tips, I would be grateful! :smiley: Thank you!

Best regards,
Colton

#8

Basically just use a DataOutputStream and write bytes/ints/floats/whatever as appropriate, and pipe it through a zip output stream. And use the smallest data type for each bit of data - so if you only have a few different tile types then just use a byte (or even the lower few bits of the byte and pack some other info in the spare bits).

#9

Wow, that’s pretty tricky stuff! Sounds really cool, though; I’ll have to experiment with it and see what I can come up with! Thanks a ton!

Colton

#10

also^^
when everything is procedural then why do you need to save anything?

The only thing you need is the starting seed.
And you would have to save changes the player made to the world.

Same thing what is done in games like minecraft, you just save the things the player changes the rest gets generated every time the game starts.

#11

Minecraft only generates the first time you see a piece of level, after that’s it’s saved and loaded to disk, regardless of whether the player changes it or not. I’m guessing Colton wants to do the same - it does make things a lot more straightforward and robust.

#12

Precisely :]

#13

A lot of tile maps use repeating adjacent tiles (e.g. many grass tiles together) which can be “compressed” using the same filtering techniques that PNG and GIF encoders use. You would use an “indexed color” format, but your “palette” would be tailored to tiles (sprite index, blocked, flipped, etc) rather than colors. Writing this kind of complex encoder/decoder would be overkill for simple tiled maps, but it’s a cool idea.

The easiest thing to do would just be to pack as much information as you can in each byte/int.

#14

I had seen something similar to that in a compression post I saw somewhere a few days ago, and indeed, I think it would be very interesting! I’m still slightly confused about how to go about packing more information in a byte than the tile’s ID!

#15

cough Huffman encoding cough

#16

Or Rice encoding.

#17

You can do all this encoding by hand, or just use simple run length encoding, but really, are you learning how compression works, or do you want a compressed map? Use GZIPInput/OutputStream and be done with it.

#18

I’m already using GZInput/OutputStream for all my compression, but I figured the guys above were referring to a way to get compression down even further. :]

Colton

#19

well, a simple replacement for GZIPInput/OutputStream would be to use LZMA Input/ Output Streams ( https://github.com/league/lzmajio/downloads ) depending on your input it should give a decent reduction

#20

Hm, Slick comes with a library in the form of LZMA.jar. Perhaps this is the same type of thing?