SpritesMind.Net

Nice to read document, but for the current matter adds no advance.

A bit off topic, but, there is always been people fascinated by Aladdin game, while is a definitely a good game, I was never been able to understand what makes it been seen above the rest. It was advertised very pompously on its launch, is still this promotion alive on players spirits or is there really something else?

Miquel wrote: ↑

Fri Oct 20, 2017 6:16 pm

Nice to read document, but for the current matter ads no advance.

Aside from the fact that it seems Chopper will occasionally include blank tiles from the looks of it.

All right.
This may not be the BEST algorithm on earth to split sprites and so on. Especially, it doesn't optimize very well "holes" in sprites (an empty tile inside a sprite), but it manages to achieve some neat results. At least, good enough for me.

https://www.dropbox.com/s/m3hctty54yox1 ... 2.zip?dl=0

Usage : java SpriteReducer spriteToReduce.bmp

(spriteToReduce.bmp has to be Windows BMP 4bpp)

The algorithm then computes around 15 seconds (SpriteReducer.main()) to guess the best sprites/tiles setup in order to minimize (sprite-list + tiles) size (my cost function). Meanwhile, it displays stuff. The only part that really matters is the last one, with the sprites and the size.

NB 0: I limited the sprite count at 25 (Canvas.NB_SPRITES_MAX).
NB 1: the algorithm first marks all empty tiles as such. This is because like aforementionned I don't have any sprites with empty tiles, and this is also to speed things up. If this is your taste, please feel free to disable this part in the Canvas constructor.
NB 2: given non 8-modulo width/size images, the algorithm creates one thread per 8 pixels-aligned image. The added offset are stored in Image class. I didn't bother to include 'em in the results, but feel free to do so.

While it definitely is not perfect, please, include credits if you use it.

Can you explain what is your algorithm about?

It's an algorithm to split big sprites.
First it loads a 4bpp bmp file.
If the image size is not 8-pixels aligned, it generates the 8-pixels aligned images, with an offset on width and height, up to 49 images (7 pixels width offset x 7 pixels height offset).
Then, for each 8-pixels aligned image, it tries to put some canvas upon it. I call canvas a list of sprites.
How does the canvas cover the image ?
Given a tile, it will try to cover the broadest area (width), then the tallest area (height).
The dimensions will be limited by the max sprite width (4 tiles), the image width, and the next tile on the current line,
and the max sprite height, the image height, and the next tile on the current row*.
When this area has been covered, the algorithm recursively calls itself and starts again until everything is covered, or too many sprites are used (by default, NB_SPRITES_MAX is 25).

As an optimization, I first got rid of empty tiles inside filled tiles.
The cost function is the size of sprite entries plus tiles, in bytes.
I let the algorithm run for 15 seconds, then take the best result. On my i5-760@2.8GHz, this is good enough.
It gives decent results for fighter sprites, such as Street Fighter III.

* Now that I'm explaining it, it occurs to me that if a lower sprite starts some rows before an upper one, I'm going to cover this tile twice. Bummer.
PS : well, not bummer that much after all. Eventually, a better answer will be found, and this overlap will be forgotten

Ok, going to the point, you first try to fit sprites into the image, and then secondly find empty tiles inside the shape of the image and rearranging previous sprite fittings. Is that correct?

One striking thing I discovered trying to find an optimum algorithm is that changing only one tile could change totally the solution. In other words, going closer to a local optimum doesn't guarantee that you are getting closer to the global optimum.

ob1 wrote: ↑

Mon Oct 23, 2017 7:20 am

If the image size is not 8-pixels aligned, it generates the 8-pixels aligned images, with an offset on width and height, up to 49 images (7 pixels width offset x 7 pixels height offset).

Either description or your algo is incorrect. It should be 64 images 8x8 offsets.

r57shell wrote: ↑

Wed Aug 30, 2017 4:21 pm

Anyone up to making testing of algorithm tool? If none, then I'm off.

Yet again, it proves: if you want to make something good, make it yourself
I'll do when I'll have spare time.

Instead of trying to come up with an algorithm, I thought I'd rather make it easy and fast for humans to do it. After all, humans tend to outdo most algos at things like this. WIP screenshot:

Yes, I think that would probably work better. You might have a button to try one of the algorithms, show the result, and let the dev do any changes to make it better.

Sik wants an automated solution (he explains why in late pages).

Also, thought a previous example, we have seen than an algorithm is slightly better than experienced humans, the problem is that this algorithm doesn't work well in some cases.
I suppose the solution is to use several methods and adopt best result.

Here is my ultimate version of sprites splitter.
It's most advanced and expensive approach that I came up with so far.
It's command line program. just run it without args to get usage.
https://www.mediafire.com/file/fm111c15 ... t.exe/file

Ah. It reads from stdin, so if you want to feed file into it, just run it like this: in file first row should be width and height in pixels, next should be data separated by spaces.
each pixel is 1 if it is opaque, or 0 if it is transparent.
example: https://gist.github.com/realmonster/c74 ... 5fa05078d9
output for given pic:
Ah, format of output:
First row is: sprites_count tiles_count
All other lines: x y width height

You may notice, that width and height may not be multiple of 8.
This means that it's up to you in which way you'll enlarge it to closest multiple of 8.
For example, you may always expand it to right and bottom,
just increase width or height while it's not multiple of 8