OverlayPal: A graphics tool for automatic sprite overlay creation

[Bananmos]

A while ago I was getting fed up with figuring out how to best partitions colors in an image to make a good background + overlay split from an existing image. I found it tedious even with a test image dumped from an emulator, and even trickier to know if an arbitrary image could be decomposed at all or not.

So I decided to try and automate this process.

I tried a few greedy algorithms, but none would be consistently successful, so I eventually ended up using the CMPL mathematical modelling language, to model this an an integer linear programming problem.

A Qt GUI on top of that, and we've got OverlayPal: https://github.com/michel-iwaniec/OverlayPal

Windows and Linux build can be found here:



And here's a few screenshots of it in action:

TBH I'm not 100% sure artists will actually prefer this top-down method, compared to just designing overlays in a bottom-up fashion. But I'd love to hear from you if you do

Future improvements I can think of:
* Optimisations! The CMPL solving is very slow ATM. But there's a lot of ways the problem could be simplified before passing it to the solver
* True offgrid sprites. The current simplication of keeping everything on a grid works kind-of-ok, but means the total solution space is artificially constrained
* Support for 8x8 sprites
* Possibly support rewriting palette colors to extend total palette space

[Bananmos]

Gosh, still not a single comment...

C'mon folks. I'd appreciate some honest feedback on this. Even if it's nothing more than "you seem to have solved a problem nobody ever had"...

[Macbee]

The idea is excellent and this can be very useful to NES artists.
Right now I'm not doing stuff related to NES - however I'm downloading Windows version to take a look!

[Bananmos]

The idea is excellent and this can be very useful to NES artists.
Right now I'm not doing stuff related to NES - however I'm downloading Windows version to take a look!

Cheers - would really like to know what you think of it when you get some time. Particularly if the whole indirect approach of automated background conversion is actually useful in practice, rather than just in my automation-focused-mind...

[Banshaku]

I wasn't aware of this thread thus not answering.

I will check the details later but if I understood from the quick read it's takes a picture, extract and do sprite overlay when not possible. If this is the case, this is something that Kasumi is quite familiar with since it's own i-chr has this feature which I used in my own projects.

I will see if I can understand more about it and test it once some time free up

[Bananmos]

I wasn't aware of this thread thus not answering.

I will check the details later but if I understood from the quick read it's takes a picture, extract and do sprite overlay when not possible. If this is the case, this is something that Kasumi is quite familiar with since it's own i-chr has this feature which I used in my own projects.

I will see if I can understand more about it and test it once some time free up

Wow, you're right... Kasumi did work on trying to solving this problem a few years back. I just found these threads:
viewtopic.php?f=21&t=17082 (about Kasumi's tool)
viewtopic.php?f=21&t=16921 (thread by Lucradan about the same overlay-split problem)

(almost embarassed to admit I followed this thread back then, yet only remembered the CHR tile count optimisation part and not the palette overlay problem. Memory refresh rate goes downhill with age I guess... )

And these threads involved not only have Kasumi talking about ways to solve it the BG+overlay problem, but also forum veterans like rainwarrior, tepples, tokumaru, FrankenGraphics, Bregalad... looks all the cool kids were into it back in 2018!

However, it doesn't look like Kasumi ever released this feature into the wild, so I suppose you have a unreleased version?

I did try downloading the latest version of Kasumi's I-CHR tool, but couldn't really make it work with any test images. Even the converted ones. So either the feature isn't there, or I'm just understanding how to trigger it? It'd be interesting to know how the output compares, even if the unreleased(?) version can't be shared.

Also, from what I read with the thread Kasumi tried a greedy algorithm, or potentially using a greedy algorithm with lookahead / some promising heuristic, but wasn't satisfied with the result.

Lucradan already did suggest formulating this as an LP problem to get around the limitations of greedy algorithms... which is more or less what I've done here. Although using CMPL rather than lp_solve. I haven't actually looked at lp_solve yet, but I did try PuLP before converting my app from Python to C++.

Why I really ended up with CMPL was due to two things:
1) It has its own self-contained programming language which looks quite similar to the prohibitively expensive AMPL. This makes the optimisation problem really simple to formulate and add upon in the future: https://github.com/michel-iwaniec/Overl ... tPass.cmpl

2) CMPL internal programming language also features automatic rewriting of products of binary / small-range integer variables. With PuLP I had to use the widely used but rather hacky "big M" method instead to achieve these things manually. And the PuLP-based code ended up being a mess that I don't think anyone else could easily follow.

Arguable downside of CMPL could be that it's GPL rather than LGPL, for those who prefer a less "viral" copyleft license.

A disclaimer is that OverlayPal doesn't always find a solution as of know if you're pushing against the sprites / scanline limit, as I am using a grid for both BG and sprites, and artificially constraining the problem space and making certain solutions invalid. I imagine it could get there with two improvements:

1) Having the second CMPL pass solve a coverage problem for all 64 sprites on a pixel granularity, instead of forcing sprites to use a grid. (could be very slow...)
2) Merging these two passes into one - to avoid the first pass creating infeasible solutions for the second pass. (ditto for speed problem)

But working with every image was only one of the goals I had. The other was to test the theory of whether drawing pixels in your favorite pixel editor with automated conversion - and not having to worry about explicitly duplicating colors across BG / sprite palettes - is actually useful to pixel artists in practice. And spending time on making the program more exact but slower would currently work against that goal.

Anyway, FWIW OverlayPal's code is openly available for any readers of this thead to study and improve in the distant future if they don't mind GPL:d code, if interest in these things ever swings back to 2018 levels.

[rainwarrior]

In my own work I've done semi-automated solutions for this a few times.

What I tend to find most useful is a tool that does the automated part in a simple/predictable way, and then has a way to look at the result and manually give hints to it. "Start your row of sprites here. Come from the left instead of the right. Use a substitute tile here that I know will look the same. Use this specific palette in slot 2." etc.

I don't have any fancy generic tool that does this visually to share, but I've done more or less this in disconnected pieces, e.g. script that tells it how to build sprites + inspecting the result in a debugging emulator, etc.


When I think about what is possible for optimization, there just seems to be too much search space to really cover all the issues (detecting symmetry, optimizing for unique tiles vs. lowest overlap, ambiguous tiles due to layering or shared palette colours, etc. etc.). Ideally I have an automation that works reasonably well out of the box, and then gives me ways to hand tweak it for optimization if/when I need it. Even more ideally it'd be an all-in-one tool with a GUI that shows me the results instantly and lets me do the hints visually, but creating such a thing has always seemed like much more overall work than just manually entering the hints in text or something.

One thought re: grid of sprites, what I did in my current project was work in rows rather than a grid. I start the row at the edge where non-transparent pixels start and proceed across the line from there. If there's a gap in the middle of the row it keeps moving until it finds more non-empty pixels on that row. By doing it in rows they don't vertically overlap, and within the row by snapping each tile to the first non-empty pixel it automatically is using the minimum number of tiles, at least. (Similarly, rows don't need to be contiguous, just non-overlapping. It could skip some lines between rows if they don't have any non-empty pixels.)

[Banshaku]

Regarding Kasumi's version, I was testing some beta version in 2018 when working on the mm9 project and it helped for a few screen I converted. As for being released, I do not think this specific feature was and it may not be either since the main issue with it is most people expect magic and this is not: there will always be case when the picture cannot be converted because of the current constrain.

The tool itself was giving feedback for specific case, error where it failed etc. It was going well but like I said, people are expecting too much and I think it was put away because of that. I'm mostly using it these days for automatically extracting unique tiles for sprites, which is quite useful and I think was the original goal of the tool unless mistaken.

I will try to test a few screen with OverlayPal later to see how it goes. If it shows were it cannot convert , too many color etc then it's quite close to Kasumi one then. There was a "optimization" mode where it tooks more time and tried to remove as much as possible tile too, which was interesting to see.

Kasumi would be better placed to talk about it than me though, that's for sure, since I was just using the tool and don't know the inner working. I was just happy that it saved time since converting by hand would have been too complicated with my current skills.

[Kasumi]

I haven't checked this forum in quite some time. If you're interested in trying out the new I-CHR, I'm happy to give anyone interested access, PM me. It's probably not better, but how it does sprites is not grid or row based which might have academic appeal. But... it's also not open source. It does a lot of things that public version does not, and handles lots of that stuff better, at least.

I'm planning to release it soon, it's done/stable features-wise, but I want to make a slightly nicer UI and a trailer to hopefully build some excitement to get people to use it.

Browsing this forum, it seems lots of other things have come out since I've started and not released that seem to solve similar problems, probably better.

edit: Trying your program, it fails on one I-CHR also fails on that is clearly possible, at least with the default settings:

From Legend of the Ghost Lion. This almost makes me think I've made an error in how it was grabbed. I should check that.
As far as the things it succeeds/fails on, it seems similar. But I don't think I want to really compare them right now, lest I feel even more bad about not releasing mine
Edit 2: Well, I couldn't resist, I guess. I-CHR seems decently faster, but it's hard to compare output otherwise because the output is pretty different. I-CHR does OAM/CHR/Nametables/ROM, this gives a PNG. This does seem to do better with sprites per scanline, (I-CHR is actually not programmed to care about that), and is actually out, though!

[Bananmos]

I haven't checked this forum in quite some time. If you're interested in trying out the new I-CHR, I'm happy to give anyone interested access, PM me. It's probably not better, but how it does sprites is not grid or row based which might have academic appeal. But... it's also not open source. It does a lot of things that public version does not, and handles lots of that stuff better, at least.

I'm planning to release it soon, it's done/stable features-wise, but I want to make a slightly nicer UI and a trailer to hopefully build some excitement to get people to use it.

Browsing this forum, it seems lots of other things have come out since I've started and not released that seem to solve similar problems, probably better.

edit: Trying your program, it fails on one I-CHR also fails on that is clearly possible, at least with the default settings:

From Legend of the Ghost Lion. This almost makes me think I've made an error in how it was grabbed. I should check that.
As far as the things it succeeds/fails on, it seems similar. But I don't think I want to really compare them right now, lest I feel even more bad about not releasing mine
Edit 2: Well, I couldn't resist, I guess. I-CHR seems decently faster, but it's hard to compare output otherwise because the output is pretty different. I-CHR does OAM/CHR/Nametables/ROM, this gives a PNG. This does seem to do better with sprites per scanline, (I-CHR is actually not programmed to care about that), and is actually out, though!

Hey Kasumi, and thanks for trying OverlayPal out!

In its current state, OverlayPal will actually fail on quite a few images, so your example is by no means a unique case.

Like I mentioned earlier in this thread, the assumption of sprites being on a grid is the most limiting factor with OverlayPal once you start pushing against the limitations in terms of overlay colors where very tight sprite fitting / off-grid sprites would be needed. It's a simplification I needed at the moment to reduce the problem size, but also artificially limits the solution space.

I believe I know how to rewrite the mathematical problem to make the conversion "perfect"... at least in the sense of always finding a palette if that is possible - ignoring the fact that different solutions can still differ in tile count.

But I am worried it'll slow down an already slow conversion process even further. And the other goal I had with this tool was the automated background conversion, which would in theory allow an artist to just draw colors in a pixel program, with OverlayPal re-running in the background whenever the input file is overwritten. And the slower the conversion gets, the less useful that background-conversion feature would be.

So these two goals work a bit against each other, and I'm not sure how to find a compromise unless I find opportunities to speed up the solver. Then again, neither of goals seem to have generated that much interest... so it'll probably just be one of those OCD problems I'll try out for fun in the future. Perhaps by trying a simplified optimisation process first, and only going full-force with the "perfect" solution when the simplified one fails.

With that "Legend of Ghost Lion" image in particular, it's an interesting one because the original design does follow a simple grid layout so should fit my current simplified model in theory. But two things are probably keeping it from being successful:

1) OverlayPal only tries to use 8x16 sprites at the moment. An earlier version in Python used the opposite mode of 8x8. It really ought to auto-try them both.

On the other hand, if you don't plan to add less-important-hardware-sprites dynamically on top of the converted image, then even with 8x16 sprites I think you should be able to arrange sprites according to priority, to essentially give you variable-height sprites. Another reason for ditching the grid and reformulating the sprite layer as a coverage problem, where each sprite can be off-grid.

2) Second limitation is probably the fact that the splitting is currently done in two separate passes.

The first moves background colors to the overlay whilst trying to minimise total amount of pixels moved (a sensible heuristic that can fail). And the second pass then has to work with the overlay produced by the first. And the downside of this is that the first pass can produce a result that the first might not be able to solve.

A single-pass solution is really needed to avoid this condition - but again may make an already slow conversion even slower because it would need to search a much bigger problem space. Or alternatively it might be possible to iterate over additional "valid" solutions from the first pass.

An earlier Python version where I used PuLP rather than CMPL / CBC was actually single-pass. But as that worked on the 16x16 grid (for the BG color restrictions) it wouldn't deal with this image anyway without some slight modifications to use 8x8 for the sprite grid whilst still enforcing 16x16 background color restrictions. It was even slower - taking hours for some complex images. So I ultimately ditched it to iterate faster on "most convertible images".

Interesting that I-CHR fails on it as well though... this image is probably good as a stress test for future improvements.

And yeah, OverlayPal is a bit limited in how it doesn't currently produce any of the .chr / nametable / OAM data. But I did consciously choose to limit the scope to trying to produce a .png that would be guaranteed to be convertible if OverlayPal succeeds at its job. Because once you step into the specifics of NES CHR / nametable / OAM it becomes more of "build system territory" in my eyes.

Conversion to .chr / nametable / OAM memory is a problem that is a lot more well-defined and faster. And more about data crunching, potential compression and of course how to handle bank-switched CHR.

I might possibly add such features to OverlayPal at some point for a more complete package, but it's not really on the top of the TODO-list - especially given the algorithm still needs refining / complementing to work with all images.

By the way, quite a few years back I also made a tool that was more focused on conversion of smaller sprites while optimizing tile counts / sprites per scanline / etc in a semi-configurable way.
http://retrocoder.epizy.com/tilificator_tutorial/

Tilificator probably overlaps a bit more with I-CHR's use-case in how tries to optimise for tile count. But it wasn't really made to handle big images / BG with overlays, whereas I-CHR does that as far as I understand. Tilificator also doesn't do any of the palette mapping decisions that I created OverlayPal for.

Like OverlayPal, Tilificator didn't find much of an audience at all. Although it at least got some use in "Streemerz"... ironically for the title screen conversion which it was honestly a bit ill-suited for

Looking back at Tilificator in hindsight, I gotta admit it did very well in some cases... but it also very much exposed the limitations of using greedy algorithms for these kind of problems. It's essentially a brute-force solution enumerating a lot of combinations for each sprite cel, and processes the sprite cels sequentially... which means a "bad start" will end up giving suboptimal results, because it's using greedy algorithm that doesn't backtrack.

I'm tempted to re-visit Tilificator some time and try CMPL on it for a truly global optimization that doesn't get stuck in local minima... if only to see how bad that would really get performance-wise. It could be that even a very large problem formulated as an integer LP may still perform better than all the complex&slow Python code I ended up writing when adding heuristic on top of heuristic. Not to mention it'd be more readable and maintainable than the Tilificator Python code's complex heuristics.

Gotta admit I am personally pretty hooked on the integer LP formulation for formulating these kind of problems. In this day and age I think the computing power is sufficient to find the true optimal solutions for many of the optimisation problems that keep re-occurring in the NES developer's conversion toolflow - not just graphics. But we might need just a few more years of Moore's law to really get there.

Then again, I'm not sure anymore that squeezing bytes / sprites-per-scanline counts out of content is much of a practical problem holding NES programmers back... it is looking more and more like it mostly belongs in the fun-programming-challenges category. And perhaps only shines if it does come bundled into an all-purpose tool.

Perhaps your new version of I-CHR will be that all-purpose tool to gain some traction. I would like to try out how it compares on other overlay conversions. A feature request of mine would probably be to produce a .png like OverlayPal does... just in case somebody already has their own flow for converting images to .chr / nametable / OAM

[Bananmos]

P.S.
To anyone else trying OverlayPal out... be aware the current version has a really silly bug of not working if you place it under a directory with spaces, due to how it naively passes this on to the CMPL .exe

A n00b mistake that I realised too late, just because I personally avoid spaces in folders and filenames like the plague.

[Bananmos]

In my own work I've done semi-automated solutions for this a few times.

What I tend to find most useful is a tool that does the automated part in a simple/predictable way, and then has a way to look at the result and manually give hints to it. "Start your row of sprites here. Come from the left instead of the right. Use a substitute tile here that I know will look the same. Use this specific palette in slot 2." etc.

Thanks for the feedback. Yes, this sort of debugging is something I wanted to have a lot of in OverlayPal... although unfortunately the flipside of using CMPL and the integer LP formulation is that the solving is very "opaque", in the sense that I'm offloading the searching of a very large problem space.

But there's definitely room for improvements. Come to think of it, one basic thing I need to add back from the earlier Python version is being able to show the number of colors / grid cell for the pre-converted image, as OverlayPal currently only shows this for the converted image, and only if the conversion is actually successful.

Although in some ways a "guide" for how to fix errors wouldn't make sense though, as being "close" to a solution does not automatically imply that tweaking that particular close-to-complete-solution is the best way to create a valid image. There might well be a different solution in the search space that is even better, or at least a better candidate for tweaking.

But there's definitely ways to suggest tweaks to the user... it's just that they don't naturally fall out of the search space, as CBC (which drives CMPL) does a ton of backtracking during its exhaustive search, so there's probably too many close-to-valid solutions to really communicate, unless one can objectively be defined as better than the other.

When I think about what is possible for optimization, there just seems to be too much search space to really cover all the issues (detecting symmetry, optimizing for unique tiles vs. lowest overlap, ambiguous tiles due to layering or shared palette colours, etc. etc.). Ideally I have an automation that works reasonably well out of the box, and then gives me ways to hand tweak it for optimization if/when I need it. Even more ideally it'd be an all-in-one tool with a GUI that shows me the results instantly and lets me do the hints visually, but creating such a thing has always seemed like much more overall work than just manually entering the hints in text or something.

Yeah, the nature of integer set problems is that they become intractable quickly. Hence why some simplifications need to be made. In this case, I've chosen to ignore the issue of tile count, as that's probably better handled as a separate optimisation pass, even if it might be at the cost of a less optimal solution.

The only other alternative I see if you still want to find the exact optimum without compromises is making everything into one single pass... and as people now predict Moore's law to end in less than 5 years, it's probably not a practical option

One thought re: grid of sprites, what I did in my current project was work in rows rather than a grid. I start the row at the edge where non-transparent pixels start and proceed across the line from there. If there's a gap in the middle of the row it keeps moving until it finds more non-empty pixels on that row. By doing it in rows they don't vertically overlap, and within the row by snapping each tile to the first non-empty pixel it automatically is using the minimum number of tiles, at least. (Similarly, rows don't need to be contiguous, just non-overlapping. It could skip some lines between rows if they don't have any non-empty pixels.)

Indeed, and the methods in tilificator do something like this. But using a greedy algorithm that will fail in many cases.

The core problem for OverlayPal though is that the decision problem of which colors to move to the overlay in each BG 16x16 grid cell already has a very large space and gets very rather slow to solve exactly. And adding any variant of a per-pixel coverage problem for up to 64 sprites for on top of that may really explode the search space.

OTOH, searching the search space efficiently for a valid solution is what CBC is made for... so it may not be as bad as I fear. Might just have to try it and see. Worst thing that can happen is I'll need to just keep it as a final method to attempt when every other simplification has failed.