Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Fri Oct 20, 2017 6:16 pm

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?
Last edited by Miquel on Sun Oct 22, 2017 11:52 am, edited 1 time in total.
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Sat Oct 21, 2017 12:38 am

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.
Sik is pronounced as "seek", not as "sick".

ob1
Very interested
Posts: 463
Joined: Wed Dec 06, 2006 9:01 am
Location: Aix-en-Provence, France

Re: Algorithm for splitting sprites

Post by ob1 » Sun Oct 22, 2017 10:16 am

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.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Sun Oct 22, 2017 4:13 pm

Can you explain what is your algorithm about?
HELP. Spanish TVs are brain washing people to be hostile to me.

ob1
Very interested
Posts: 463
Joined: Wed Dec 06, 2006 9:01 am
Location: Aix-en-Provence, France

Re: Algorithm for splitting sprites

Post by ob1 » Mon Oct 23, 2017 7:20 am

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 ;)

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Mon Oct 23, 2017 4:04 pm

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.
HELP. Spanish TVs are brain washing people to be hostile to me.

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

Re: Algorithm for splitting sprites

Post by r57shell » Tue Oct 24, 2017 9:28 pm

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.
Image

cero
Very interested
Posts: 338
Joined: Mon Nov 30, 2015 1:55 pm

Re: Algorithm for splitting sprites

Post by cero » Thu Feb 15, 2018 7:06 pm

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:
screenie.png
screenie.png (22.51 KiB) Viewed 24792 times

Chilly Willy
Very interested
Posts: 2984
Joined: Fri Aug 17, 2007 9:33 pm

Re: Algorithm for splitting sprites

Post by Chilly Willy » Thu Feb 15, 2018 11:17 pm

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.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Sun Feb 18, 2018 4:35 pm

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.
HELP. Spanish TVs are brain washing people to be hostile to me.

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

Re: Algorithm for splitting sprites

Post by r57shell » Sat Dec 01, 2018 10:27 pm

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:

Code: Select all

sprites_split 1 1 < qwe.txt
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:

Code: Select all

5 34
4 0 12 16
0 16 16 32
16 0 20 16
36 4 16 32
16 36 32 16
:D
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
Image

Post Reply