Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Algorithm for splitting sprites

Post by Stef » Fri Sep 01, 2017 8:50 am

The formula is just a cost function, then depending the user you can affect different cost to whatever you want (number of sprite, vram usage, scanline density..)
Last edited by Stef on Fri Sep 01, 2017 11:01 am, edited 1 time in total.

flamewing
Very interested
Posts: 56
Joined: Tue Sep 23, 2014 2:39 pm
Location: France

Re: Algorithm for splitting sprites

Post by flamewing » Fri Sep 01, 2017 10:03 am

Stef wrote:
Fri Sep 01, 2017 8:50 am
The formula is just a function cost, then depending the user you can affect different cost to whatever you want (number of sprite, vram usage, scanline density..)
This (which is what I had said before).

There should be a way to specify what is more important to the person writing the game. Concrete examples:

In Sonic 3 & Knuckles, you have 32 tiles for Sonic and 32 tiles for Tails. Tails VRAM is right after Sonic's, and it is further subdivided (for most frames) into 16 tiles for Tails' body and 16 for his tails (again, for most frames). There is one diagonal running sprite if Super Sonic which is not properly divided, and overwrites some of Tails' tiles. Thus, being able to specify a hard upper limit to the number of tiles is desirable.

Sonic 2 had basically the same setup. But due to competition mode, all sprite pieces must use an even number of tiles on the height. So every sprite piece is padded with empty tiles to an even number of tiles in height. The characters are still limited in the number of total tiles (32).

Sonic Classic Heroes has 3 characters each with 32 tiles allocated, and they can have shields. This gives an awful number of sprites per scanline. This, minimizing the number of sprites per scanline is a must, as is minimizing the number of sprite pixels per scanline. And not exceeding the limit on number of tiles for each character and the shields.

Big's Fishing Derby has a lot of sprites on screen, and a lot of free VRAM. Reducing tile count is not important, but reducing total sprites and sprites per scanline is. Reducing total sprites is actually the most important thing: the other measures almost do not matter.

For all of these cases, all tiles in the animation frame are transferred to VRAM by DMA, independently of whether they are shared with previous frames or not. Thus, any tile splitter that deduplicates art will be wasting effort in these cases, except for the fact that the art file will take up less space in ROM.

But this minor size reduction will add additional processing time in-game: the DMAs are pre-computed and are limited to contiguous pieces of up to 16 tiles. With deduplicated art, you will be picking up a few tiles from one place, a few more from another, a few more from somewhere else. This will cause several DMAs to be queued and then performed, instead of 1-2 larger DMAs. If you are doing something that required a lot of processing power (such as collisions with enemies and terrain for an additional character), this may be enough to cause the game to lag.

And so on. Like I had said before, a generic tile splitter is not useful if you can't specify what you are after; each game is a game, and has different priorities.

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

Re: Algorithm for splitting sprites

Post by r57shell » Fri Sep 01, 2017 10:30 am

flamewing wrote:
Fri Sep 01, 2017 10:03 am
And so on. Like I had said before, a generic tile splitter is not useful if you can't specify what you are after; each game is a game, and has different priorities.
It's too bad... We gonna die.

Btw, one more case: if tiles compressed, and uncompressed size calculated by sprite size (3x4 for example), then you can't share empty tiles, except if you add some more handling for this cases.
Image

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Algorithm for splitting sprites

Post by Stef » Fri Sep 01, 2017 11:11 am

Well, you can assume a default split mode which use a "good compromize" with a function cost where each cost are less or more equivalent (good balance between sprite usage, vram usage and scanline limite). It's what i want to implement in rescomp and later maybe i'll add an option to prioritize the split on a specific optimization (vram for instance)

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

Re: Algorithm for splitting sprites

Post by Miquel » Fri Sep 01, 2017 9:07 pm

Stef wrote:
Fri Sep 01, 2017 8:50 am
The formula is just a cost function, then depending the user you can affect different cost to whatever you want (number of sprite, vram usage, scanline density..)
Ok, then given your experience programming MD give your desired function cost. The parameters you want to include and the default values of them. Of course you can change them after, but we need some default values that can be successful for a majority of cases. Anyway right now there is no algorithm avalible for that so we are just especulating.

In my case for example, I have much less free tiles avaliable than sprites; but I don't know how common this situation is.

@flamewing, Sonic games use dynamic loading of tiles for Sonic and friends, that's another case.
Miquel wrote:
Thu Aug 31, 2017 6:07 pm
What's the price?
Let me see... what's available on this forum... members!!! we have persons available. So,

For the winner: 3 girls in case of a male, 2 boys in case of female
For the first of the losers: 1 girl/boy
For the second of the losers: a congratulations from the forum's members

The only thing is... @KanedaFr, have we enough female members registered?
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 Sep 02, 2017 2:43 pm

At this point we're going to end up with just requesting Google to let us borrow one of their AIs to do the job.

If we're going to account for every corner case then we'll be in Futurama's time and still be arguing over this. And arguing over what corner cases should be accounted for without also discussing how we could handle them is going to be useless. I'm seeing people here argue about parameters to adjust the splitting, but how the heck do you specify parameters if you don't even know how it's going to work? (not to mention the values would be meaningless without knowing what they affect)
Miquel wrote:
Fri Sep 01, 2017 9:07 pm
Let me see... what's available on this forum... members!!! we have persons available. So,

For the winner: 3 girls in case of a male, 2 boys in case of female
For the first of the losers: 1 girl/boy
For the second of the losers: a congratulations from the forum's members

The only thing is... @KanedaFr, have we enough female members registered?
(ノ_<)
Sik is pronounced as "seek", not as "sick".

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 Sep 02, 2017 4:17 pm

as I see, no one tried my algo. :(
I'm not PR machine of my tools / researches / developements.
Image

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

Re: Algorithm for splitting sprites

Post by Miquel » Tue Sep 05, 2017 7:44 pm

Kaneda wrote:
Miquel wrote:
Fri Sep 01, 2017 9:07 pm
The only thing is... @KanedaFr, have we enough female members registered?
Not really... 0_0'
Well, then males and a cargo of hallucinogens must do the trick... I suppose... this way brain washing us could be even easier.
HELP. Spanish TVs are brain washing people to be hostile to me.

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Algorithm for splitting sprites

Post by Stef » Wed Sep 06, 2017 8:24 am

r57shell wrote:
Sat Sep 02, 2017 4:17 pm
as I see, no one tried my algo. :(
I'm not PR machine of my tools / researches / developements.
Why don't you try it on the proposed example ?? Given your algo (from what i read) i think it won't perform really nicely too but you can prove me i'm wrong. Designing a good algorithm for sprite splitting fitting to the MD sprite capabilities is definitely not trivial.

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

Re: Algorithm for splitting sprites

Post by r57shell » Wed Sep 06, 2017 12:26 pm

Your example is not sprite. It's just "idea" of sprite.
So, I should make image first, and then feed it into my algo,
then it will return list of coords, that I should also visualize somehow.
Unless if I put it into ROM, then run in my gens mod, which may show sprite borders.

All above requres some time, that I don't wanna spend.
Image

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

Re: Algorithm for splitting sprites

Post by Miquel » Wed Sep 06, 2017 8:57 pm

Just show sprite count and the coords, don't worry, we have developed a taste for it.
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 » Thu Sep 07, 2017 1:32 am

The problem is that r57shell wants to also showcase how his code finds the best alignment for the sprite to end up with the least amount of blank tiles (which requires having the whole source image as-is, which I can't show for reasons :v) and he's being stubborn about not showing things in "perfect" conditions. That's something that can be easily tacked on top of the others (as already shown), the biggest problem right now is coming up with a good split once the covered tiles have been determined.

Also if anybody cares, none of the tiles are repeated, so feel free to go by that assumption.
Sik is pronounced as "seek", not as "sick".

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

Re: Algorithm for splitting sprites

Post by Miquel » Thu Sep 07, 2017 2:47 am

Sik wrote:
Thu Sep 07, 2017 1:32 am
the biggest problem right now is coming up with a good split once the covered tiles have been determined.
That's the point, there is no secret in shifting an image and finding empty tiles.
Sik wrote:
Thu Sep 07, 2017 1:32 am
Also if anybody cares, none of the tiles are repeated, so feel free to go by that assumption.
Talking about probabilities, there is in great amount that are going to be repeated pieces in an animation. But the problem is much more complex than that because you can overlap those pieces to reduce more tile count. Maybe it needs a different approach, like working with those unique pieces instead of the whole image. That's what I going to try next month.
HELP. Spanish TVs are brain washing people to be hostile to me.

BigEvilCorporation
Very interested
Posts: 209
Joined: Sat Sep 08, 2012 10:41 am
Contact:

Re: Algorithm for splitting sprites

Post by BigEvilCorporation » Wed Oct 18, 2017 10:20 am

Relevant to your interests, see the "Chopper" chapter:

https://gamehistory.org/aladdin-source-code/
A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Algorithm for splitting sprites

Post by Stef » Wed Oct 18, 2017 11:38 am

Yeah i saw that, unfortunately the source code of the interesting tool is not provided :-(

Post Reply