Here is a very quickly written (and probably dirty) C solution to locate self-containing, non-overlapping sprites. I used a PNG reader to get the data in RGBA format and checked only alpha.
It works like this:
- find any non-zero alpha pixel, from top to bottom;
- starting at this pixel, form a (min,max) rectangle and keep expanding it until none of the sides contain an alpha pixel;
- you end up with a one-pixel wide blank border around the actual sprite, so
minx,y
has to be increased by 1 and maxx,y
decreased -- but that happens in the coordinates-to-size calculation.
- finally, this rectangle gets wiped out so next loops won't see this one anymore.
Sprite rectangles may not overlap! (They don't, in this image, but better make sure it happens nowhere else.)
The output list could be sorted on x,y coordinates for clarity; I'm going to leave that, and translating this to Java, to you. This program assumes there may be 64 or less images in a single sheet (struct bounds_t[64]
); make sure it's as large as necessary.
C-code (obvious PNG library structures and headers left out):
struct bounds_t {
int x,y,wide,high;
};
int alphaAt (struct pngdata_t *sheet, int x, int y)
{
if (x >= 0 && x < sheet->wide && y >= 0 && y < sheet->high)
return sheet->data[4*sheet->wide*y + 4*x + 3];
return 0;
}
void floodFindBounds (struct pngdata_t *sheet, int startx, int starty, struct bounds_t *dest)
{
int x,y;
int hit;
int minx = startx,miny = starty,maxx = startx,maxy = starty;
while (maxx < sheet->wide && alphaAt (sheet, maxx+1,miny))
maxx++;
while (maxy < sheet->high && alphaAt (sheet, minx,maxy+1))
maxy++;
do
{
hit = 0;
for (x=minx; x<=maxx; x++)
{
if (alphaAt (sheet, x,miny))
hit |= 1;
}
for (y=miny; y<=maxy; y++)
{
if (alphaAt (sheet, minx,y))
hit |= 2;
}
for (x=minx; x<=maxx; x++)
{
if (alphaAt (sheet, x,maxy))
hit |= 4;
}
for (y=miny; y<=maxy; y++)
{
if (alphaAt (sheet, maxx,y))
hit |= 8;
}
if (hit & 1) miny--;
if (hit & 2) minx--;
if (hit & 4) maxy++;
if (hit & 8) maxx++;
} while (hit);
minx++;
miny++;
dest->x = minx;
dest->y = miny;
dest->wide = maxx-minx;
dest->high = maxy-miny;
}
void wipeout (struct pngdata_t *sheet, struct bounds_t *wipe)
{
int x,y;
for (y=wipe->y; y<=wipe->y+wipe->high; y++)
for (x=wipe->x; x<=wipe->x+wipe->wide; x++)
sheet->data[4*sheet->wide*y + 4*x + 3] = 0;
}
int main (void)
{
struct pngdata_t *sheet;
struct bounds_t fullList[64];
int x,y;
int n_in_list = 0;
sheet = read_png ("monster.png");
if (!sheet)
{
printf ("unable to read sprite sheet\n");
return 0;
}
printf ("ready to process\n");
printf ("size: %d x %d\n", sheet->wide, sheet->high);
printf ("pixel #0 = %d,%d,%d,%d\n", sheet->data[0],sheet->data[1],sheet->data[2],sheet->data[3]);
for (y=0; y<sheet->high; y++)
{
for (x=0; x<sheet->wide; x++)
{
if (alphaAt (sheet,x,y) != 0)
{
floodFindBounds (sheet, x,y, &fullList[n_in_list]);
wipeout (sheet, &fullList[n_in_list]);
n_in_list++;
}
}
}
printf ("found %d sprites:\n", n_in_list);
for (x=0; x<n_in_list; x++)
printf (" %d,%d,%d,%d\n", fullList[x].x,fullList[x].y,fullList[x].wide,fullList[x].high);
return 0;
}