Graphics in Excel (New: 'Tiled' Map Translation Tools!)

[93143]

My thought on this is that I can hopefully write a customized program specifically designed to import graphics to the SNES, which will allow you to generate a table of palettes for a much larger image and then assign each 16x16 block of the image a palette such that you're left with a completely assembled image - all you'd have to do is load the tiles, palettes and a tilemap into your game and you've got any arbitrary image file on screen.

In concept I am sure such a thing is possible, but I'm having a hard time right now coming up with a strategy for doing it. If you quantize the entire image all at once you'll end up with every tile containing mixed palettes, which is useless. If you break it down one tile at a time, each tile will generate a unique palette. What I need is a way to calculate a compromise between each piece's ideal palette to come up with a set of 2-to-3 (or up to 8 depending on whether it's just a static image or an actual "background") palettes that will best represent the whole image. I'm not sure where to start.

Does anyone have experience with this kind of project? Has it been done? Anyone know of a reason I should give up?

I have experience, in the sense that I thought about it for a bit recently.

Perhaps one could quantize each tile (8x8 or 16x16) separately, and then repeatedly pare down the number of palettes by identifying palette pairs that are the most similar in a least-squares sense, and re-quantizing the set of tiles that use them as a single image. For palettes with free entries, you'd obviously want to avoid comparing colours that aren't actually used; perhaps pixel-weighting the least-squares comparison would work...? Though that raises the possibility of botching very small colour regions; a higher error power might be more resistant to such an effect, but it might skew the overall comparison...

Or perhaps you could just compare the tiles up front and pare them down to N sets that have similar colour requirements, and then just quantize once...

You decide whether or not I'm onto something; I haven't actually tried this.

...

It occurs to me that this technique will most likely result in a visible tile structure unless you're very careful to align nearby colours in different palettes...

[Khaz]

Okay so I did it. Please find attached the excel spreadsheet that did it all, along with two proof-of-concept ROMs that just display the results.

First thing you do is import a (128x128*, 24bpp) bitmap file (using importLARGEBitmap). This creates two worksheets, one for drawing in and one to do all the calculation. Importing dumps a list of every colour used for each tile, along with how many pixels use that colour.

Next you run the initial quantization (kMeansKwantizeLARGE). This quantizes every 16x16 tile down into its own palette of 15 colours, which takes a bit of time. You need this starting point to run the next step. You can also draw this 64-palette version out if you want (redrawQuantizedLARGE, click "No").

Once you have that, you start eliminating palettes (crunchPalettes). You input a number of palettes to eliminate (up to 20 at a time), and the program will merge that many pairs together. This way you can reduce your image to as many or as few palettes as you want. So far I've been reducing each image to 8 palettes, for maximum quality in a single background layer (without getting fancy). I initially tried palette elimination by running a full quantization of each pair of tiles, then merging the two that resulted in the smallest increase to their average colour displacements. This turned out to be absurdly time-consuming and would have taken days to process one image. So, I took a more direct approach kind of like 93143 suggested:

For each pair of palettes, the program renders their set of tiles in the OPPOSITE palette, and calculates the increase in average colour displacement that would result from switching the two palettes. The palettes with the lowest increase from this swap are then merged and re-quantized together. If a palette has empty slots then the colour displacements for mapping tiles to that palette are all taken to be zero, to encourage the program to merge palettes with empty colour slots first. Colour displacements are also weighted per-pixel, not per-colour (ie/ if you have 83 of colour A and 1 of colour B, colour A is counted 83 times more than colour B. This distinction didn't seem to make much difference that I can see.)

Finally, when you've crunched it down to 8 or fewer palettes, you can export the results (exportInclude). This will generate a 16-color tile set and your palettes in one file, and a corresponding tilemap in a second file. At that point, it's as simple as cramming it into your program.

I have to say I'm very impressed with the results I got from this. I was expecting an ugly grid of barely recognizable garbage. All in all I'm hardly seeing any degradation as compared to every tile having its own palette, I could easily miss the grid pattern if I weren't looking for it, and my cat looks amazing. If only I'd written it in not-excel, so it could finish in less than 4 hours or so.


*For the record, 128x128 seems a convenient size but any bigger and not only will the calculations start to take days again but you start running out of tile space on your BG layer. 128x128 takes I believe half of your available tile space for one BG layer. You could do 256x256 by using 2 BG layers in mode 1 using basically the same technique, to fill the screen.

Alternately, if the processing of each image were sped up considerably such that you could do hundreds of them, I bet you could store frames of a 128x128 colour video and flip through them at at least 30fps. Tiles for a frame would be $2000 bytes, you only use $40 bytes of the tilemap and $100 for palettes so $2140 per frame... So uncompressed you should be able to get a full 16 seconds of video out of a 4MB ROM. Cool! That would be neat to see.

[93143]

Awesome! It worked!

That squirrel pic has 112 colours, and the cat has 107. I fiddled around in cq to try to get them to look decent in 16 colours (to get a feel for how big the improvement is), and it kinda works on the cat, but the squirrel looks awful no matter what. And the squirrel is the one where it's harder to see the tile boundaries, at least on my monitor. Very impressive.

128x128 takes I believe half of your available tile space for one BG layer. You could do 256x256 by using 2 BG layers in mode 1 using basically the same technique, to fill the screen.

Not half. A quarter. The tile index is 10-bit. One layer is more than enough to fill the screen with unique tiles in any mode except 7.

I notice you seem to be using 16x16 tiles. If the method could be sped up, using 8x8 tiles would probably improve the quality a bit; it's not like you're hurting for tilemap real estate...

[Khaz]

I should note that there's a bug in the spreadsheet I just posted I noticed just now. If palettes 0 and 1 are the best ones to merge it screws up and merges the previous pair again. I thought something wasn't quite right.

Not half. A quarter. The tile index is 10-bit. One layer is more than enough to fill the screen with unique tiles in any mode except 7.

I notice you seem to be using 16x16 tiles. If the method could be sped up, using 8x8 tiles would probably improve the quality a bit; it's not like you're hurting for tilemap real estate...

Right, of course. I can't think of any reason not to use 8x8 tiles, I'll probably give that a try when I get the motivation to rewrite this again, as well as finding a way to make processing a 256x256 image viable. I think this could actually be useful.

[Ramsis]

Wow, very impressive work, Khaz. I especially appreciate your color demo. :3

Please keep up the good work (and please, please do make it open source).

[Khaz]

(and please, please do make it open source).

Heh! This is the main problem here. I've already tried looking into converting my existing code into something open source, but the options aren't very promising. LibreOffice has been ruled out completely. I spoke to their community, support for Visual Basic code exists but is incomplete and will never be finished. Their only option is spending several months studying first python, then how python interacts with Libre of which there is little to no documentation, THEN re-writing it all over again, which simply isn't happening. Has anyone tried OpenOffice? I'm not expecting better from them but I haven't tried yet.

(Side note: Proper documentation to work from is the absolute most important factor. EVERY excel problem is fixed by one google or a quick look in the "MSDN". Every other programming language I've ever seen seems to give you absolutely -nothing- to work with.)

What I need is a language completely independent of a spreadsheet program, but I haven't tried to use such a thing in over a decade. I used to know C++ but it was a living hell for me. Java seems slow and useless. Once again I come back to Python, but for how popular it is there sure isn't anything out there to help a person get started from scratch. Excel has the entire user interface naturally built into the program; something like Python I would have to DESIGN that from scratch, which is more months of nothing but studying and no useful progress. It's just too convenient having the spreadsheet available to store and manipulate all your data. I could store everything in arrays and do all the math behind the scenes... Not only is that once again completely rewriting everything from scratch again, but god help me if I have a single bug in the finished product because I will NEVER find it.

If somebody has a suggestion for something that would be ideal for this, let me know. I'm tryin' but at this point I don't think it's going to happen and the words "Open Source" are starting to give me panic attacks.

[tepples]

Something like this (an automatic color reducer) might be done as a command line tool. Python has import argparse to parse command lines, and it has Python.org for docs and Stack Overflow for searching similar problems that others have had.

[Khaz]

Something like this (an automatic color reducer) might be done as a command line tool. Python has import argparse to parse command lines, and it has Python.org for docs and Stack Overflow for searching similar problems that others have had.

Okay I see Python actually does have some documents on their website. Fine... I will try this one more time. If anyone here has actually used Python before I would appreciate them just telling me what IDE to use because there are too many choices and I'm tired of wasting hours on irrelevant decisions like that (I mean seriously, their website not only has a list of like two dozen of them but also another 15 articles exclusively about how to choose between them).

If an open source version of this tool is actually coming it won't be anytime soon so please don't hold your breath. This is going to take way more time than I have available at the moment.

Please excuse my less than pleasant mood as I'm not having the best day today...

[tepples]

Okay I see Python actually does have some documents on their website. Fine... I will try this one more time. If anyone here has actually used Python before I would appreciate them just telling me what IDE to use

I just use IDLE, the one that comes with Python for Windows and is an apt-get away on Debian or Ubuntu. For loading images, you'll probably need either Pillow (Python Imaging Library) or Pygame (Python wrapper around SDL).

[Khaz]

I've just spent basically the last day trying to figure out how to write one byte to an output file using python.

I cannot possibly understand what the people who designed this language were thinking when they created the "byte" object. When you read the file in binary, you get these stupid objects that you then have to convert through some needlessly convoluted means into anything useful. That I can at least do. Then when you want to write a file you have to convert your values back into byte objects. I literally have nothing but numbers between 0 and 255. Every programming language ever made should have an expression no greater than ten characters that converts a number into a byte.

Python's only option is apparently "struct.pack". Once you figure out you need to import struct, then you need to figure out what "formatting expression" to use. You have 10 different choices for "integer", NONE OF THEM is a single byte. I somehow get the idea I'm supposed to store it as an unsigned character, since that's basically your only one-byte format. I try using "c" for char, but no, that expects a "byte object" as input which is what I'm trying to pack here in the first place. Try "B" and that doesn't work either because "required argument is not an integer". What does that even mean? Are they saying what it needs isn't an integer, or that what I'm giving it isn't an integer?

I used ord() to convert the byte objects into integers in the first place. Their official documentation states that chr() is the inverse of ord(), but I can't take the output of a chr() and write it as a byte into a file. Why not? Are they aware of the definition of "inverse"?

I can't even just do something like "bytes(n)", because that doesn't create a byte with value n. It creates a list of n bytes with value zero, which is useless. But oh, you can do "bytes([n])", which should give you a single byte of n. (What IS that syntax? I don't understand these "iterators" or whatever is going on in this language.) But then I can't put my number inside the []s because apparently a 'type' object is not subscriptable. And if I ord() it inside there, it says it expects a STRING of length 1. So I try using chr() again and I'm back to the first error.

What in the hell, this is unbelievable. This is why I hate higher level programming languages. In my entire time learning 65816 I never ONCE ran into frustration like this. I don't have enough information here. The official page is not helpful because I don't understand what the program is looking for and I have no indication of what it is that I've done wrong so far. I understand that Python has "strongly enforced types" but if that's the case it's absolutely unforgivable to not have convenient methods to convert between said types.

Most of the rest of the program is done already, but until I can make it output something I can't even tell if it's working yet. This is stupid.

[Drew Sebastino]

That whole thing, in a nutshell, is why I'm not trying to learn any high level languages. People always act like they are easier to use, and then you see something like that. I just like to "be in control", I guess.

[Khaz]

OKAY. I seem to have figured THAT out. You have to use int(), not ord():

f.write(struct.pack("B", int(byteOfColour)))

Nnngh.

Now I have to diagnose this output:

...Without being able to examine my lovely spreadsheet of RAM to see where something went wrong. This could take a while.

EDIT: I thought I fixed it, but nope:

EDIT: Okay I have no idea what the hell is going on now.

EDIT: So tiles with less than 16 colours weren't being written right. I have a Quantizer again. Now I have to finish the Palette Crusher.

[thefox]

I've just spent basically the last day trying to figure out how to write one byte to an output file using python.

Here's how:

Code: Select all

open( "foo.bin", "wb" ).write( "x" )

or (this one makes sure the file is automatically closed when the "with" block exits):

Code: Select all

with open( "foo.bin", "wb" ) as f: f.write( "x" )

Every programming language ever made should have an expression no greater than ten characters that converts a number into a byte.

Code: Select all

b = chr( 123 )

Well, it's not really a byte, but a character (or in fact, a string), but in practice it behaves the same.

Python's only option is apparently "struct.pack". Once you figure out you need to import struct, then you need to figure out what "formatting expression" to use. You have 10 different choices for "integer", NONE OF THEM is a single byte. I somehow get the idea I'm supposed to store it as an unsigned character, since that's basically your only one-byte format. I try using "c" for char, but no, that expects a "byte object" as input which is what I'm trying to pack here in the first place. Try "B" and that doesn't work either because "required argument is not an integer". What does that even mean? Are they saying what it needs isn't an integer, or that what I'm giving it isn't an integer?

No need to use use struct.pack/unpack. They can be handy though if you need to store/read values that are longer than a byte and may have varying endiannes.

but I can't take the output of a chr() and write it as a byte into a file.

Yes you can (see above).

I can't even just do something like "bytes(n)", because that doesn't create a byte with value n.

The "bytes" type is a Python 3 thing. You don't need to use it (I never have, although I'm still on Python 2.x for the most part), but I'd assume there's a reason why it exists.

The problems you have encountered are quite typical in dynamically typed languages. Dynamically typed scripting languages can make it faster to write programs, but that comes at a cost of more runtime errors, often very obscure ones.

[Khaz]

Code: Select all

b = chr( 123 )

Well, it's not really a byte, but a character (or in fact, a string), but in practice it behaves the same.

I don't know if this is a difference between python 2 and 3 but I'm pretty sure they don't behave the same. ".write" in "binary mode" expects these particular byte objects, I couldn't make anything else work. In retrospect I should probably have been using text-write mode and encoding each integer as a character and doing it that way... In any case, I have that particular problem solved now. Naturally I can go all day without any headway but the second I complain about it it fixes itself...

I'm having palette problems still but at least I have all the bits of python I need working now. Hopefully I can get some results soon. On the negative side of things, python doesn't seem to be executing all THAT much faster than Excel (with screen updating turned off). It's a noticeable improvement, but the added comparisons from 8x8 tiles and a fullscreen image are going to make it very slow... We'll see how much I can do to it.

[thefox]

Code: Select all

b = chr( 123 )

Well, it's not really a byte, but a character (or in fact, a string), but in practice it behaves the same.

I don't know if this is a difference between python 2 and 3 but I'm pretty sure they don't behave the same. ".write" in "binary mode" expects these particular byte objects, I couldn't make anything else work.

You're correct it seems, they did change the behavior in Python 3. I'm kind of surprised about that, but then again I have next to no experience with Python 3.