Topic: Map Crunching

[DarkWolf]

Well, I've been busy this holiday season and I haven't had time to work on anything sprite or mapping related.  Anyway, before I start on possibly doing some Phantasy Star II maps, I wanted to play around with an idea.

A lot of maps have a lot of empty space that has to be compressed into the file.  Now compression works well with empty space, but I wanted to see if I could shave the file size down even more.  My first test I did with Rick Bruns's Castlevania castle map.  (Sorry, just needed something quick for a test).

Dracula's Castle

My version is HTML based and is approx. 48K smaller.  However, the output image file is 4736x1664, opposed to the original 9920x2096.  38% of it's original canvas size.  This should make it easier for lower-memory computers to display (I did some testing with the large Faery Tale Adventure map).  This is somewhat promising.

What my method does is this:
It breaks the image down into square sections.  It then loops through these sections to see if they contain 100% empty space (based on a user-supplied color).  It then breaks the image down into "strips" and then attempts to put those strips into an output image.  It records the "moves" the program makes and can then later generate an output based on the "crunched" image and XML data file.  For the HTML output, I use absolutely positioned DIVs and background image offsets.

Pros:
* Smaller file size for images with large empty areas
* Adjustable section size
* Can be applied to existing images
* Eliminates hot-linking
* Could help with google indexing (especially for VGMaps)

Cons:
* So far, file size reduction is good, but not amazing
* User needs a web browser to view map
* Could break later with browser changes
* While HTML pages could be indexed by search engines, you would loose image search (i.e. Google images)

Things to test/do:
* Test more existing maps (could use some suggestions)
* Try making a map that's set on a grid, then running it through the script
* Test viewing the map on more devices and browsers

[Revned]

Very interesting. This is more elegant than the one-tile-per-image approach I experimented with years ago.

[Maxim]

Aha, "CSS sprites" for the images so you get the advantage of compression over the whole image while allowing the image itself to be optimal.

One more con: it doesn't work with Google Images.

You could try tweaking the squashed image width. PNG uses a 32KB lookback for compression so narrower maps tend to compress better. I'm not sure how it'd interact with the algorithm you're using though.

Is there a sweet spot for the size of the squares?

[DarkWolf]

The algorithm to move the strips is fairly simple.  I take the longest strip, divide that in half, then sort all the rectangles by those that are closest to the half mark.  Then I just loop through the collection filling up rows.  Has worked so far, but I can play around with it a bit.  Thought about doing a method that allowed for rectangles of various heights instead of "strips" but then we get into more complex algorithms and I doubt the payoff would justify it.

I'm going to try and do more testing today, and maybe I can get some more info.  But theoretically if you made a map aligned to some grid, the size of the grid or some multiple of that grid would be the "sweet spot".

Very interesting. This is more elegant than the one-tile-per-image approach I experimented with years ago.

That might still be a better option for a map that has little or no empty space.

[Maxim]

Well, most maps (I'd hope) are aligned to the tile grid so you have 8x8, 16x16 etc alignment, with massive reuse of tiles (does your algorithm optimise for that?). The problem with that scale is the enormous amount of HTML produced. The biggest tile size in any map I made is 96x96 (SMS Micro Machines).

PNG compression uses a 32KB lookback (Deflate algorithm), meaning it can only compress something it saw in the last ~32K pixels (assuming 8bpp). That means it gets badly affected by blank space. My Enduro Racer SMS maps are a prime example of this. But they also fit really badly into squares...

[DarkWolf]

While most maps are made out of tiles that are perfectly square, I'm finding a lot of times the assembled images don't exactly fit the grid.  I had one map where the vertical of most areas was 201 pixels high for some reason.  And right now there's no feature to offset any margins.  If the map was made to where the different "areas" were spaced on a grid, it would be possible to eliminate even more blank space.  Or prevent the script from chopping off a small margin of map and having a strip that's mostly blank.

I did do some more testing today and the script definitely needs some tweaking.  I need to be able to implement a strip size limit.  The most fruitful crunches I did today were one of my Blake Stone maps, going from 1960 KB, to 1380 KB and Maxim's EuduroRacer maps, going from 3918 KB to 3465 KB.  Those figures include the HTML overhead.  I figure Enduro could be crunched even more after I tweak some things.

I'm curious about being able to do layers with these HTML maps.