Kasumi wrote: ↑
Tue Apr 06, 2021 9:21 pm
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.
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