I'm currently writing a Sprite Sheet Unpacker such as Alferds Spritesheet Unpacker. Now, before this is sent to gamedev, this isn't necessarily about games. I would like to know how to detect a sprite within a spriitesheet, or more abstactly, a shape inside of an image.
Given this sprite sheet:
I want to detect and extract all individual sprites. I've followed the algorithm detailed in Alferd's Blog Post which goes like:
- Determine predominant color and dub it the BackgroundColor
- Iterate over each pixel and check ColorAtXY == BackgroundColor
- If false, we've found a sprite. Keep going right until we find a BackgroundColor again, backtrack one, go down and repeat until a BackgroundColor is reached. Create a box from location to ending location.
- Repeat this until all sprites are boxed up.
- Combined overlapping boxes (or within a very short distance)
- The resulting non-overlapping boxes should contain the sprite.
This implementation is fine, especially for small sprite sheets. However, I find the performance too poor for larger sprite sheets and I would like to know what algorithms or techniques can be leveraged to increase the finding of sprites.
A second implementation I considered, but have not tested yet, is to find the first pixel, then use a backtracking algorithm to find every connected pixel. This should find a contiguous sprite (breaks down if the sprite is something like an explosion where particles are no longer part of the main sprite). The cool thing is that I can immediately remove a detected sprite from the sprite sheet.
Any other suggestions?
Best Answer
After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.
The Method
The Code
The source is available on github, and here is the code w/o documentation or imports.
However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.