News for hackers. Stuff that matters.
Re:Technical overview of Kandria, a game and game engine dev... by Shinmera on Monday July 11, 2022 @04:58PM (#32061734)
I'm sure Aseprite could be further optimised to press down the constant factor, but it is performing a rect packing algorithm among other things, which is an NP-hard problem.
Re:Technical overview of Kandria, a game and game engine dev... by rednab on Tuesday July 12, 2022 @07:32AM (#32068352)
The bin packing problem is NP-hard, but rectangle packing is "merely" NP.

However, most people just use a recursive biggest-fit-first ¹), a simple heuristic that is surprisingly hard to beat for most workloads.

I couldn't figure out what Aseprite is doing from their website or documentation, but if it's not that then it might be worth it writing your own sprite packer.

¹) https://codeincomplete.com/articles/bin-packing/

Re:Technical overview of Kandria, a game and game engine dev... by Shinmera on Tuesday July 12, 2022 @08:51AM (#32069115)
Yeah I don't know what they use either, but so far repacking that atlas has not been frequent enough that writing my own packer would save time.