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?
