Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

User avatar
Miquel
Very interested
Posts: 330
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.
Perhaps the sunny thing was an excuse, but the “flashes” were real, did you see them? Afterwards, next day or so, a spaceship from the same people send something to us, a radio message I believe.

User avatar
Sik
Very interested
Posts: 709
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: 407
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.

User avatar
Miquel
Very interested
Posts: 330
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?
Perhaps the sunny thing was an excuse, but the “flashes” were real, did you see them? Afterwards, next day or so, a spaceship from the same people send something to us, a radio message I believe.

ob1
Very interested
Posts: 407
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 ;)

User avatar
Miquel
Very interested
Posts: 330
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.
Perhaps the sunny thing was an excuse, but the “flashes” were real, did you see them? Afterwards, next day or so, a spaceship from the same people send something to us, a radio message I believe.

r57shell
Very interested
Posts: 475
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: 229
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 757 times

Chilly Willy
Very interested
Posts: 2593
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.

User avatar
Miquel
Very interested
Posts: 330
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.
Perhaps the sunny thing was an excuse, but the “flashes” were real, did you see them? Afterwards, next day or so, a spaceship from the same people send something to us, a radio message I believe.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest