Tile reduction

This is an archive of a topic from NESdev BBS, taken in mid-October 2019 before a server upgrade.
View original topic
Tile reduction
by on (#115980)
Are there any programs that do tile reduction of similar tiles? Even better if one could set a threshold for how aggressive the matching is.
Re: Tile reduction
by on (#115981)
I asked a similar question a while ago, so this thread might be useful to you.

http://forums.nesdev.com/viewtopic.php?f=21&t=9586
Re: Tile reduction
by on (#115984)
Yes, I saw that, and I use grit to remove duplicate tiles and for compression.

As a way to save further space I looked for tiles that were similar and removed them by hand. It didn't seem like it was taking a long time but of course a couple of hours went by.

This freed up a lot of space in the rom (21AC2) and the images look just as good as they did before.

This seems like something somebody would have done already. If not I'll add it to my todo list.
Re: Tile reduction
by on (#115991)
Sixpack?

I personally use my own custom tools, either writing them from scratch for a particular case, or modyfing old ones if they are close enough to requirements. Writing a tool from scratch is definitely faster than sorting out tiles manually.
Re: Tile reduction
by on (#115997)
Define "similar tiles" and I'll get to work.
Re: Tile reduction
by on (#116010)
Tepples, I have thought of a simple architecture for such a program:

Code:
prompt user for difference tolerance, n (how many pixels must be mis-matched in an 8x8 tile to be considered different)
create new tile buffer for export
load tiles
for tile in tiles:
    store tile reference for comparison
    for tile in tiles:
        check for differences against stored tile reference ( in complete pixels )
        if there are equal to n or less differences:
            copy user's choice of one or the other to the new tile buffer
        else:
            copy to new buffer (this will also handle the comparison of a tile to itself without issues)
Re: Tile reduction
by on (#116011)
It's a bit harder when you consider that a similarity metric based on counting equal pixels isn't transitive. Consider the case where both A and B are similar to a later tile C, but A isn't similar to B. And even the algorithm you suggest is O(n^2), meaning it might work for a single 256-tile scene at a time but I'm not sure how tractable it stays for the 16384-tile banks of, say, MMC5 ExGrafix.
Re: Tile reduction
by on (#116014)
tepples wrote:
And even the algorithm you suggest is O(n^2), meaning it might work for a single 256-tile scene at a time but I'm not sure how tractable it stays for the 16384-tile banks of, say, MMC5 ExGrafix.

Well, this is the SNESdev forum, so he probably expects to use this on chunks larger than 256 tiles.
Re: Tile reduction
by on (#116015)
On the one hand, that's a good thing, as 1024 tiles (Super NES limit per plane) is a lot closer to 256 (NES/GB limit) than to 16K (ExGrafix limit). But flipping would complicate things, as each tile would need to be compared to flipped versions of all other tiles.
Re: Tile reduction
by on (#116030)
It wasn't a very deeply thought-out algorithm - that's why I wanted it to prompt the user to choose between tiles in question and to be able to adjust the threshold where it considers them different.

A better, more advanced algorithm would want to consider adjacency of different pixels.
Re: Tile reduction
by on (#116827)
The way sixpack handles color reduction to 16 colors looks better than the results from png-nq or gimp. I like the way it handles dithering too.

What I was thinking of was a program that would take an image (png/bmp/whatever) and just match similar tiles; anything like the attached image. Then it would just save it in the same format so that it could be used with grit/sixpack/gfx2snes. I use grit because I'm using sneskit. So in this case I'd just let grit deal with exact duplicate tiles and flipped tiles.

This is assuming that this is not massively more trouble than it's worth. Another route, I suppose, would be to use ExHiRom.
Re: Tile reduction
by on (#116835)
Quote:
The way sixpack handles color reduction to 16 colors looks better than the results from png-nq or gimp. I like the way it handles dithering too.

Sixpack uses the NeuQuant algorithm for color quantization. I've been thinking of integrating support for scolorq, since it supposedly performs better for very small number of colors (like 2bpp tiles). I also did some experiments with k-h-means quantization, but it was quite slow, and didn't yield any results worth writing home about.

The dithering algorithm is the simplest possible; select either a darker color or a lighter color based on (row ^ column) & 1.
Re: Tile reduction
by on (#117639)
I replaced 4 1/2 4bpp images with images processed with sixpack and it saved me ~1500 bytes. (The half image I used half of the image from sixpack and half from gimp.)

I still need to work on better tile reduction for 8bpp images.