Algorithm for splitting sprites
Moderator: BigEvilCorporation
Re: Algorithm for splitting sprites
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?
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.
Re: Algorithm for splitting sprites
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".
Re: Algorithm for splitting sprites
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.
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.
Re: Algorithm for splitting sprites
Can you explain what is your algorithm about?
HELP. Spanish TVs are brain washing people to be hostile to me.
Re: Algorithm for splitting sprites
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
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
Re: Algorithm for splitting sprites
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.
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.
Re: Algorithm for splitting sprites
Either description or your algo is incorrect. It should be 64 images 8x8 offsets.
Yet again, it proves: if you want to make something good, make it yourself
I'll do when I'll have spare time.
Re: Algorithm for splitting sprites
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:
-
- Very interested
- Posts: 2984
- Joined: Fri Aug 17, 2007 9:33 pm
Re: Algorithm for splitting sprites
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.
Re: Algorithm for splitting sprites
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.
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.
Re: Algorithm for splitting sprites
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
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
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
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