17 replies to this topic

[Paratron]

Hey,
this is my first post here on gamedev.net

I am currently writing a tilebased map engine which I want to use in a small HTML5 game - so the engine is written in JavaScript.

I want to load tilebased maps of different sizes and thinking about how to transfer them efficiently to the users browser, I came up with the idea of storing them inside PNG files.

Every pixel of the PNG image can be translated to a field on the map. Also, the compression of such a PNG file is quite good, so I can easily store a 500x500 fields map (this is incredibly huge!) inside a PNG with about 185kb. This loads fairly quick even on mobile phones.

After retrieving the PNG file, I would read the map (sort of) pixel-by-pixel and use the extracted RGB color values to convert them back to palette indexes so my engine knows which field from a sprite palette to draw on which position on the map. Things like prettifying field type transitions (sand to grass or grass to water and so on) are calculated clientside so they don't have to be stored in the map.

My problem is: to create pretty detailed maps, I want to utilize 3 layers for each field, like the RPG maker does: bottom layer is the base field type + autotiles for transitions. Second layer are elements like walls, fences, trees and every other stuff you cannot walk over with a character. The third layer is for additional decoration like cracks in walls or windows.

I could merge the third layer down to the second layer but that would mean I have to store many many more element tiles (i.E. have to store each map with the crack already rendered onto it) and thats not very flexible.

So however - I have have 4 channels per pixel with a range from 0 to 255 (r,g,b and a). If I convert that 4 channels to an integer, I can get a number with the max height of 255*255*255*255 = 4.228.250.625

I would happily throw the billions away and split the remaining max 999.999.999 on thousands for each of the three layers, giving me 999 possible indexes per layer (no, not 1000 since a 0 means: empty layer). I really thing thats more than enough, otherwise the palette to load with the map is just too large.

What do you think about that storage method?
Do you have any other ideas on how to efficiently store large tilebased maps so they can be read by JavaScript?

[Ravyne]

That's probably a reasonable approach, assuming that indexing the pixels isn't too difficult. PNG is also the right way to go since it's lossless, jpeg is lossy and wouldn't work.

If you can do the bit-twidling in javascript quickly enough, you can divide the 32-bits however you'd like. For example, you could have 3 layers with 10 bits each, or 4 layers at 8 bits each. There's also no rule that layers have to have the same number of indices -- layer 0 might have 10 bits, while layer 1 and 2 might have 11 each.

Another possibility, and I'm not sure what the browser support looks like, but I believe the actual PNG format supports more formats than are usually used -- I believe it supports other layer counts and bit-depths. Also keep in mind that you might want to encode other data into the image, like collision data, triggers, etc.

If I were to do it, I'd probably also divide the map into square chunks (say, 32x32 or 64x64) and stream them in like google maps. You could also consider having layers being encoded by separate images -- it might seem wasteful at first, but the compression is such that any mostly-empty image will be quite small -- a 64x64 image I just tested was white with 4 separate black pixels placed randomly, and weighed in at just 340 bytes.

You could also encode the image as a sort of linked list to add additional layers.

[Paratron]

JavaScript bacame a quite fast thing since interpreters like V8, Nitro or Tracemonkey are around. So its no problem to convert the values around when I need them.

I have successfully written two JavaScript functions today which convert three layers for a field to an RGBA value and back.

It might be possible to store real layers and other stuff inside a PNG file (Adobe Fireworks stores all that stuff inside PNG files), but I am obly able to access flat RGBA values per pixel in JavaScript. No layers or metadata access.
If I really want to incorporate some additional data, I still have a few bytes available in the RGBA space.

The idea of splitting a map into chunks is interesting, but imho not neccessary. Even a multiplayer-game wouldn't have a world with thousands of thousands of fields in size. And if so, there is no need to having the whole world stored inside ONE map file.
My engine is designed to be capable of loading multiple maps and then nicely transition between them, i.E. fading from one to another when walking down stairs, or sliding from left to right, when you leave a map thorugh a gateway on its left border. So you would basically divide such a huge world in multiple region maps.

[slayemin]

That's an interesting idea. You could use each color channel as an index value for a tile look up
Red values could be your bottom layer of tile textures/types
Green could be colliable objects, like trees and rocks layer
Blue could be doodads and other aesthetic effects layer
Alpha could be creatures or spawning points

You'd be limited to 255 different tile types per layer, but that's probably more than enough (Rayvne had a good suggestion of using more bits than the standard 8 bits).

Alternatively, you may be able to just send a binary file instead of a PNG. This would probably give you more flexibility with your data storage format and allow you to shrink the file size down to just the data you need, and give you room for feature/capability growth. It may be overkill though, so use your best judgement.

[Paratron]

@slayemin: i am currently storing 3 layers with 999 possible tile types in the PNG file

[Servant of the Lord]

It's a good idea in theory, and I've done something similar before (though not using the separate color channels as layers), but here's why I wouldn't use it.

A) You are limited to three layers... what if you want more in the future?
What if you later want layers that appear over the player. For example: The top of trees or the top of walls should appear over the player, so he can walk 'behind' them.
You might as well create your own map format where you could have as many layers as you want.

B) What about walls and other collision data?
Script triggers, wall collision data, warps, etc... where do those go? Will you augment your image file with another custom file format anyway? If so, you might as well make the entire thing a custom file format, as it gives you less limitations and more control.

C) What about special effects on tiles?
I don't know what your game requires, but my game allows me to colorize tiles, and rotate them 90 degrees, mirror them, give them varying transparency, and even use tiles as shadow-maps or light-maps to add more detail to areas. Easy enough to add... if you have your own map format.

D) Why limit what kind of tiles you could place on each layer? Why not put any tile on any layer?
This limits the possibilities available to map creators. Give the map creator as few limitations as possible, and let them worry about what seems reasonable when it comes to the type of maps they create.
Example: Bushes go on layer 2, right? What if I want a potted bush? I place the ground (layer1), the pot (layer2), but I'm not allowed to put the bush on layer 3?
Or will you insist a new tile is created, one with the push and pot merged together? That cuts into your tile limit.

And probably my biggest complaint is if you are trying to do this to avoid creating a level editor. Editing PNG files for maps, seems like a good idea in theory, "I can just use MS Paint as my level editor!", but in actuality, you can't at a glance distinguish between the different subtle shades of color, especially not when you start mixing in additional color channels for the other layers - then you won't even be able to visually notice that two tiles on layer 1 are the same, because they have different colors that were mixed up visually by layer 2's color channel.

Map editing in an image editor just doesn't really work once you start adding more tiles, and is not a suitable replacement for a map editor. And if you're going to use a map editor anyway (either your own, or a pre-built one), you might as well use a better map format.

If high compression is your goal, you could probably compress a custom map format better than PNG could, since you know things about the map format that PNG doesn't, allowing you to get rid of blocks of data that PNG can't. You could even apply PNG compression (instead of just using a PNG file) to your custom map format - PNG compression is zlib compression (according to Wikipedia).

[Ravyne]

I might be wrong, but I think HTML apps are limited to known file types and hypertext transfers; I'd actually love to hear that I'm wrong. However, most solutions I've seen to this problem either encode the data into images, or transmit binary data using base-64 encoded values over http. You can compress the data prior to base-64 encoding, but the encoding afterwards increases the size again by 33%.

Images have a further advantage of playing nicely with CDNs out of the box, which might not be the case with other content types.

[Servant of the Lord]

I wasn't aware of that limitation (I'm a C++ programmer who works on desktop applications) - that'll definitely take my suggestion off the table... Could you just treat the entire image as pure byte data? If so, you'd still get better flexibility with a custom data-type masquerading as an image, rather than interpreting each pixel as self-contained 24 bit pieces of data.

[Paratron]

Wow, thats a quite lenghty post, thanks for the detailed response

About point A)
I currently decided to stick to three layers with up to 999 possible adressable slots on a spritemap. I would be able to decrease the total amount of slots per layer (since 999 tiles is still way to much, imho) to get more layers. Its just a bit of number-shifting but I could easily go up to about 6 layers and still have ~500 possible, addressable tilemap slots left - fairly enough, imho.
I thought about your argument of having tiles sometimes rendered above, sometimes below the player and came to the following conclusion which also answers your point B):

About point B)
For now, I decided to make my maps like this: bottom layer is ground. Always non-blocking by default. Second layer is for objects, which are always blocking by default. Third layer is decorative, also non-blocking and above the player by default.

So dependend on what you place on a field, you get it automatically calculated as blocking or non-blocking. Now, you could say: well, thats very limited - what If I want to have a bush where a player should be able to walk underneath... I would reply: well. Thats a SUCH uncommon usecase, I can just neglect it.
We remember from post #1, there are still a few bytes left, which I trimmed away as "garbage". I could store information there that overrides the calculated blocking state of a field, or even which layers should go above or below the player. But with the rules I defined above, I will be able to cover 99.99% of all use cases out there.

Point C)
I am serving map-data (the PNG) apart from palette data (sprite palettes), so I am easily able to provide the same map in say - winter and summer look. My spritemaps consist mainly of a spritemap-image and a co-relating JSON file where things such as animations, autotiles and effects are defined. Thats no stuff I want to store in my mapdata-image.

Point D)
Currently, my layers can address 999 sprite slots. I could join every sprite I have (ground, object and decorative) into one palette, so I would be able to place every available sprite on any layer. Still, my blocking rules would apply.
I would shift every tile you wouldn't want to set statically (additional frames for animated tiles, autotiles) above the 999 border, since they are placed by the engine automatically.


And about your biggest complaint:
I am NOT doing this to avoid a level editor. I am doing this because PNG brings a very good compression (basically only DEFLATE, yes but they are doing a few additional tricks to compress more effectively). And because I have not much choice in the browser world. Binary processing of custom files just isn't practicable with JavaScript because it completely lacks binary variable types. They are in draft for the upcoming version of JavaScript, but not available today. At least not in all mainstream browsers.
So utilizing imagedata for maps was just a way which is really do-able with JavaScript.

Currently a field with this layer-data:
[source lang="jscript"]field = {layer0: 12,layer1: 0,layer2: 0}[/source]
would be encoded to this RGBA array:
[source lang="jscript"][0, 183, 27, 0][/source]
Which isn't something the usual map-creator could hold in mind. So there clearly is need for a level editor.

I took a look at qTiled already and altough I think its a nice editor I decided to create my own (in HTML/JS).

[Ravyne]

The trouble with encoding arbitrary data into an image is that you probably loose the coherency that makes the compression work well, so it might increase the bandwidth bill. A map that encodes data into color channels probably resembles an image closely enough that PNG-style compression, or even RLE would work well enough -- of course, both of those break down if your data isn't aligned on those channels... BTW, OP, you appear to be doing this, so your compression rates may suffer, but it looks to be fairly difficult to predict how PNG compression will behave.

The compression itself is DEFLATE (same as zlib) but there's a pre-filtering step designed to make the data more compressible, and (optional?) interlacing of the data as well. Wikipedia has more details.

[kd7tck]

Ravyne is right, color maps tend to be 16 bits in size. With no repeating tiles, this would lead to very poor file sizes.

There are 48 bit image formats out there, this could give you the extra layers you might need.

[Paratron]

Well, I did some tests. I created a 500x500 fields "dummy map" with heavily differenciated field types on all layers. Means nearly no field is the same as its neighbours. (It would render out as nonsense-grain but the high difference will make it harder for the compression algorithms to squeeze the data). Find the image here.

Storing that data inside a PNG with my RGBA encoding resulted in a PNG file with a size of 288kb after optimization with OptiPNG.
Storing the data inside a JSON file resulted in a file with the size of 2.78mb - after a GZIP compression (which a HTTP server usually applies when serving the file), it came down to 1.09mb.

You see: even tough the PNG compression cannot work under its "natural conditions", it was still capable of recieving a MUCH better compression ratio.

[Kaptein]

you could in theory use more than one PNG though?

[EmployeeNumber8]

This is an interesting idea. If you post this on github, let me know please.

When it comes to loading resources, you'll definitely want to take a look at Web Workers (if you aren't already using them).

https://developer.mozilla.org/en-US/docs/DOM/Using_web_workers?redirectlocale=en-US&redirectslug=Using_web_workers

[Riscii]

Great topic, I have been thinking about this for a while now. Have you every heard of gif stockets? https://github.com/videlalvaro/gifsockets

[Paratron]

Yeah, I read about gifsockets on hackernews recently but I don't think you are able to make use of that. Basically a GIF animation is "streamed" from the server and I don't think you are able to access the single frames in that animation.
I also think you aren't even able to access the image object before the loading has finished, which will never happen with the gifsockets method.

@EmployeeNumber8:
Sure, web workers are interesting for processing the gathered resources, but this thread is more focused at how to transfer the information efficiently.

[Ravyne]

EmployeeNumber8 may have meant websockets, or webworkers in combination with websockets.

websockets are an interesting possibility, as the message is free-form* and the server could also push sections of the map to you pro-actively.


* websockets allow for both text and binary messages, however javascript itself has no "byte" type, and so there is no binary websocket communication to a javascript app. Text messages begin with 0x00 and end with 0xFF, with text in between, so you can use any encoding scheme that avoids premature 0xFF characters in the "string" of encoded data.

Edited by Ravyne, 26 September 2012 - 04:39 PM.

[LorenzoGatti]

Using image editors as map editors is feasible with simple cases like Worms-like games with a few coded palette indexes (solid terrain, indestructible terrain, air, spawn point treated as air, etc.).
If, instead, there are multiple layers of many tile types, plus objects, plus many types of map field metadata, the map editor has to be a dedicated program, and PNG files will be an exported file format. Multiple aligned PNG files become feasible, and I suspect that multiple 1-channel files with separate data would compress better than a multichannel file.