I-CHR: Turn an image sequence into bankswitched CHR

[Kasumi]

I made a program that can take an image sequence and turn it into bankswitched CHR: https://kasumi.itch.io/ichr

It's not super good yet, but it does fix a few tiny issues I have with other CHR tools. It doesn't require an indexed palette to be prepared (though that can still help), and it supports animation for parallax effects and whatever. It's basically one step. Drag image sequence, get nametables, chr, a palette file, etc.

I didn't forget about the needs of this topic, I have some ideas of how to get there but not for the first release.

[FrankenGraphics]

Cool! That's pretty useful for something like animated cutscenes, if you're using a pcb with enough banks to support it beside a game. And for previewing tile animations in general, of course.

Is the delay/duration configurable?

[Kasumi]

Yes, frame delay is configurable but only globally. (Up/Down arrow keys change it, R re-exports the ROM) Per frame delay isn't super high priority since the ROM thing is more of a gimmick than the purpose.

Here's some other random stuff. The Zelda "sword get" animation and Indivisible title screen show faster and slower delays:

It's not just for super gimmicky 64 frame CHR wasting animation. The Kirby Water is the kind of use case I intend to use it for.

[Kasumi]

I guess this may as well be a "devlog" of sorts of this. I made an auto metasprite thing. (Note it's not uploaded, so don't grab the program expecting it.)

Here are all the 8x8 tiles 255 frames of a color reduced Sakura used.

You'll note she's 5 colors +transparency, so overlays were involved. Currently you give it an image sequence and a palette and it creates all the tiles, and metasprites. (They just can access tiles higher than 256.) I have a plan to make it not need the palette, but that's not done yet. It's also pretty slow for that many frames!
Here's the 8x16 version: https://i.imgur.com/WRFCJhI.png
And here are all the frames, in case you were curious how many individual sprites each frame used.

(Too... many... generally. The 8x16 ones could be displayed! I think they'd even all fit in the 256KB MMC3 allows, even accounting for the the space lost due to it all not being accessible at once.)

The algorithm could use a bit more work. It currently loses pretty hard unique tile wise to what I did manually for Indivisible. (768 to 526 unique tiles for Ajna.) As far as sprites per metasprite, it does about the same.

I do have some ideas of how to improve it unique tiles-wise, but I don't think I'll get a lot closer to what I did manually. The real benefit is that it's automatic not manual. I dunno if I'll release the autometasprite thing anytime soon, but I do plan to work what it does into the background stuff so it can automatically create sprite overlays for title screens or whatever. So this topic? Maybe soon™.

[FrankenGraphics]

Coincidentally I did some rough concept work last week remodelling the barbarian from the game with the same title for the eventuality of working with the epyx guy via NOOpr as a programmer. I'm on the fence wether to use 8x16 (will result in more flickering since it is less flexible with placement, but is less CPU intense and you can use both chr pages) and 8x8 mode (where i'm always on just under the threshold with little wiggle room left). In this downsized remake and because of dynamic placement of sprites, the barbarian is usually 3 or 4, sometimes 2 sprites wide (except when the sword or kick is extended) even though it looks wider when assembled. Hand-placing tiles and their contents is more work but in this case i think it is worth it - unless the script can actually calculate the optimal minimum sprite-per-line bandwidth vs tile usage. It's hard though because you need to balance these two factors using judgment. Maybe it can be defined as "as long as it doesn't use more than n tiles in chr-space, go wild sprite-per-line optimizing", assuming all tiles are preloaded into chr-ram or is chr-rom and not updated continously.

[Kasumi]

I guess I'd say the primary goal of this program is to make changes free to try. Even using your example: Deciding between 8x16 or 8x8 sprites for the barbarian. I could see how that change would look for all frames of an object in one step. At the end of the day, I want to draw, not think about tile placements.

The average Ajna frame has 13 sprites. There are 70 of them. Ajna spans 3 color palettes. Ajna alone uses more than 256 unique tiles, uses more than 512 unique tiles. Going from drawing->tiles->metasprites->game 200 times really discouraged change. In early versions of the game, her range was bad. Which meant reanimating all the attacks. And I avoided doing that forever because it was so much work to actually try different graphics. Now I can draw a stick figure and make sure the range is right before I commit to the animation. Heck, making a change after I've committed to the animation is a snap.

I can still hand optimize too, the program imports msp/msb.

It's pretty similar for backgrounds. Imagine you could just give NES Screen Tool a PNG and have it make sprite overlays for you. No need to keep specific track of tiles (or even layers) at all. Even now, this program will let you test/check animated backgrounds with a save and a keystroke and you can work in the graphics editor of your choice. (Well, so long as it saves .PNG) Edit: I'd rather fix errors after the drawing than be confined during.

I did all of the nickle and diming for tiles in Indivisible. And it shows! It currently beats the algorithm by 242 tiles. Is the game better because of that? Nah. There's even still some planned work on the algorithm that might get it in a much more competitive range.

I'm not like... anti hand optimize. It's just... I want it not to be the only option. I certainly do have one game where I'll probably optimize by hand, mostly. But this even gives me a score to beat for that! Say I throw it a frame and it gives me four sprites that don't look beatable. Then I'm done, I don't even have to think about it. If I think I can beat it, I can try!

Even if only for prototyping before committing to the final, this whole toolset will save oceans of headache for me. I've got future plans for actual animation (and character) management too. Anything that was a pain to do in Indivisible, I'm making easier with this toolset. How much gets released, I dunno.

[Lucradan]

I didn't catch this thread until today. This is good!

I started working on an image tool in C# yesterday. Let me know if you need help with anything.

[Kasumi]

Thanks! You'll be happy to know the local version can automatically get tiles/sprite tiles for sprite overlay scenes.
And here's an actual gif of the sprite->tile process:

It does a pass to guess palettes, then a pass to take tiles. (Then takes what can be a very long time doing a deep deduplication process.) It can be specified how many palettes are available to use (so it doesn't always use all 4) but that's not exposed in the UI yet. It's also just... kind of bad at guessing a good set of sprite palettes.

It also now "holds" multiple scenes at once:

But it doesn't yet export all of them to the same ROM. It also doesn't export the sprite overlay data. Getting the exporting cleaned up is my current focus. If all goes well, it should support multiple levels with up to 256 screens each rather than one level with 8 screens.

From there I'll move to an animation/hitbox system for metasprites and then maybe use this for an actual game...

RE: Help. Well, I might steal the algorithm you described in the other topic if I end up wanting that behavior.

[Lucradan]

What language are your writing this in? C++/#/Java?

You can take the algorithm as you please. I was working on an algorithm to tackle at the sprite tile extraction. Curious how you did it and if we could overcome some of the inefficiencies and issues your having.

[Kasumi]

It's C++.

The sprite palette guess algorithm uses the same "find candidate tile" algorithm as the tile take thing. With the tile mask found, it finds the most used colors (up to 3) in that candidate tile mask and removes them from the image within the mask boundary. Then it adds the palette to a list.

After all pixels in all frames are taken, it merges the palettes and use counts. (Because the most used palette could be say... just black and red, but you want three color palettes not two.) It then takes the most used palettes until it is impossible to add all the remaining colors. Then it adds the remaining colors to the remaining palette slots such that the image remains possible to display.

The find candidate tile mask thing is... a bit complicated. And probably does less well than something less complicated. It looks for corners (a top left corner is defined as an area where the top and left edge of the tile mask are opaque, and moving the tile mask left does not result in the left column still having an opaque tile, and moving the tile mask up does not result in the top column still having an opaque column.) It does... kind of a lot of other stuff to decide which of the candidate corners to actually take.

The deep deduplication can take a while because of this:

All of those are the same tile. So they'd all get merged. But for something stupid like Sakura, it's comparing flips of some extremely absurd number of tiles to each other. For a more sane case like the red and blue Tapir above it only takes a few seconds. Since it's fast enough in sane cases, improving it is not really a focus, but I know of a lot of ways to improve it already. The easiest one is to do it after each tile rather than all at the end.

The thing I'd most like to work on is reducing tile count, but the thing I think will do the best I've just avoided programming. Here's an example:

That can be displayed with exactly one tile by overlapping same color pixels. But currently the program would grab say... the left side. And then the smaller right side would be grabbed as a separate tile even though the left side tile could be used flipped and overlaid over the opaque pixels that used to be there.

I don't care that the palette guessing is bad, because one could very quickly and easily provide a palette if one cares. I also don't care much about the speed of this, since it's not really a real time application. (Even if 255 Sakura frames takes an hour, you only have to wait once. Even updating a few frames would only involve doing the new frames, not all of them.) I care most about tile use, because one can't quickly and easily break down 255 sprite overlay frames into tiles.

Edit: If you want the wild test case, I've attached the quantized Sakura frames.

[Lucradan]

I have something that might be able to repurpose that could help. I wrote an algorithm a while back that was really fast at finding patterns (from a template) in a large image. It was designed as part of the image processing algorithm for a modernization of ROB I never finished. The output was a list of the locations where that patteren appeared on the screen. If we took all the tile candidates you parsed and ran them through that algorithm (adjusting for vertical and horizontal flipping) we could get half way.

To get the other half, we would have to solve the coverage problem. Generally this could be written as a binary/integer linear program that could be solved using lpsolve. Our objective function would just be to minimize the total number candidate tiles needed to cover the image. The variables would be

X(i) = {0,1} if the i-th candidate tile is used
Y(i,j) = {0,1} if the i-th tile is placed at the j-th location (enumerated from the first stage)
P(x,y) = {0,1} if the pixel at coordinates (x,y) is covered.

The coverage constraints would be.

1. Every pixel must be covered
2. If a tile is placed at a location, it must be used

I'd still have to account for sprite layering and scanline restrictions, but I think it can be done and still preserve linearity.

There might also be some heuristic we could apply before the optimization stage to significantly reduce the number of variables (or candidate locations).

For example, in the image you showed of the semicircle, the two candidates would be the long arc (left 8 columns) and short arc (right 7 columns). Allowing translations and mirrioring, the short arc is a subset of long arc with an offset and might be eliminated because of that.

There are some problems I forsee. One in particular is that just because 2 tiles are "same" they may not be when you add the 8 tiles per scanline constraint. If you don't include this constraint then the algorithm collapses. Think about the case of a tile with a single pixel.

I'll keep thinking about it.

[Kasumi]

You are talking way over my head. If you are capable of computer sciencing the heck out of this I will probably just end up using what you come up with! I'm not a Computer Science major, I don't think I even know many CS or advanced mathematical concepts.

Minimum sprites per scanline alone is (probably) simplish to solve. Start at the top left, grab that 8x8 section. Keep doing it. As simple as it is, it's not easy to beat in many respects. I did the corner thing because I thought it'd come out similar to how I did it manually. But it didn't really, in the end. I bet that simple algorithm would beat my current algorithm total tiles wise AND sprites per metasprite wise. My manual work had a really nice balance. I doubt I can beat it algorithmically. But I can get closer than I am currently.

There might also be some heuristic we could apply before the optimization stage to significantly reduce the number of variables (or candidate locations).

I think I only ever have 8 candidate locations max at this point. It's corners * 2 because top left and left top value slightly different things.

Think about the case of a tile with a single pixel.

Right. Any sprite ever can be drawn with exactly 3 unique sprite tiles and I'm not concerned about this. My personal priorities values fewer sprites per metasprite above tile re-use. So in the example, it'd grab either the left OR the right, then in the next iteration it would find the other side as a candidate see if it could draw the small thing with something larger. (Which it could.) I'm not too interested in trying to draw larger things with small things, so the single pixel ends up a non factor for my approach.

Basically for any candidate location I can check if any tile already in the set with greater or equal coverage in both dimensions can be placed over the opaque pixels in the candidate tile such that the other pixels in the metasprite would also not change color. It's not so much that I don't have an idea how to do it, it's that I haven't done it because it's not-so-fun a programming task for me. Perhaps constraint programming makes it easy, but I'm pretty unfamiliar.

Also, the example was just an example. The situation can come up when the two won't be found as candidates together at the same time. They can be in different frames, or in the same frame after a few iterations, or in different frames in different iterations.

If what you're suggesting is a one step thing (do all candidates for a frame at once, or all frames at once) you end up with weird cases like... a black 24x24 metasprite with a white outline. There's lots of solid black tiles in the middle, that can all be eaten out of the middle with the same 8x8 tile, but then the outline makes way more sprites in that frame than are needed. The reason my algorithm is corner focused is because it's actively attempting to eat away the boundaries of a metasprite to avoid cases where a match in the middle looks good, but really just makes more sprites.

And that is how I did all the sprites in Indivisible, but with... more awareness about certain things that I am not sure how to teach a program.

[Kasumi]

It now has multiple level support, and bank switching:

Diver by Justin Cyr, maps from Link's Awakening and EarthBound Beginnings, Spinning Beach girl by me. The EarthBound Beginnings map is 256 screens. (The whole map for that game is way bigger than even that, but it's also more than 256 tiles so I'm okay not supporting it.)

(Functionality still not available for download.)
Will now work on exporting metasprites/sprite overlays and UI, and then maybe finally update the version that's publicly available. Then finally start another game...

[Bregalad]

Wow, the animation of this girl diving is really very convincting, which contrasts with it's simple shape without outlines which reminds of the early NES games... very fascinating.

[FrankenGraphics]

I just had a first go with this tool, though maybe not for what it was primarily intended for but for one of its side features? It helped me organize a sprite overlay made in PS into a tidy chr at perhaps a quarter of the time it would take doing that with nesst

Being able to import graphics with a user defined palette was key. That’s a great feature! Since it is interpretating an rgb bitmap for selecting its palette there were a few palette misinterpretations between my (nessts’) colour definition and i-chrs’, but nothing that couldn’t be fixed in a few seconds. Any chance you might be interested making it accept a NES .pal binary as an option? I usually have those ready anyway while a bitmap strip on the other hand needs to be made. Not much of a problem, but i might as well ask.

I’m curious as to why the output chr starts (at least in this particular case) with a series of identical blanks? Are those reserved?