Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

Miquel
Very interested
Posts: 200
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.
You saw 3, that's why I told so. After that, one went to Neptune, other remained on Jupiter, another landed on Earth for a few weeks. The things you are missing cos you haven't a voice.
There is a Gemini's spaceship closing to Jupiter presently.

User avatar
Sik
Very interested
Posts: 612
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: 400
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: 200
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?
You saw 3, that's why I told so. After that, one went to Neptune, other remained on Jupiter, another landed on Earth for a few weeks. The things you are missing cos you haven't a voice.
There is a Gemini's spaceship closing to Jupiter presently.

ob1
Very interested
Posts: 400
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: 200
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.
You saw 3, that's why I told so. After that, one went to Neptune, other remained on Jupiter, another landed on Earth for a few weeks. The things you are missing cos you haven't a voice.
There is a Gemini's spaceship closing to Jupiter presently.

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

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest