I wrote a flood fill algorithm in Java to get the bounds of each sprite in a spritesheet. The problem is that it works fine with some sprites but with the rest of them it doesn't. For example:

https://i.gyazo.com/cdbdb0ce40a46445ca8e7b62176ab442.png

I put a red square surrounding some of the errors.

This is the flood fill method:

private static Rectangle floodFill(int[] pixels, int x0, int y0, int width, int height) {

        Rectangle frame = new Rectangle(x0,y0,1,1);

        Deque<Point> queue = new LinkedList<>();

        queue.addLast(new Point(x0,y0));

        while(!queue.isEmpty()) {

            Point p = queue.poll();

            final int x = p.x;
            final int y = p.y;

            if(x < 0 || x >= width || y < 0 || y >= height) {
                continue;
            }

            // Is not part of a sprite, or has been visited before
            if(pixels[x+y*width] == 0) {
                continue;
            }

            pixels[x+y*width] = 0; // Mark as visited

            // Update bounds

            if(x < frame.x) {
                frame.x = x;
            } else if(x > frame.x + frame.width) {
                frame.width++;
            }

            if(y < frame.y) {
                frame.y = y;
            } else if(y > frame.y + frame.height) {
                frame.height++;
            }

            queue.add(new Point(x-1,y));
            queue.add(new Point(x-1,y-1)); 
            queue.add(new Point(x-1,y+1)); 
            queue.add(new Point(x+1,y));
            queue.add(new Point(x+1,y-1));
            queue.add(new Point(x+1,y+1));
            queue.add(new Point(x,y-1));
            queue.add(new Point(x,y+1));

        }

        return frame;
    }

The flood fill method is called from here:

private static List<Rectangle> split(BufferedImage image) {

        List<Rectangle> sprites = new ArrayList<>();

        int[] pixels = ((DataBufferInt)image.getRaster().getDataBuffer()).getData().clone();

        final int width = image.getWidth();
        final int height = image.getHeight();

        for(int y = 0;y < height;y++) {
            for(int x = 0;x < width;x++) {

                if(pixels[x+y*width] != 0) {

                    Rectangle r = floodFill(pixels,x,y,width,height);

                    sprites.add(r);

                }


            }
        }

        return sprites;

    }

What it does is visit each pixel, and if it is not equal to zero (background color), then it is a sprite, and the flood fill method gets it bounds.

I have searched for a solution and I've tried many times with different implementations but I couldn't found a solution.

Can someone help me? I think I am missing something but I can't see it.

Thanks!

if(x < frame.x) {
	frame.x = x;
} else if(x > frame.x + frame.width) {
	frame.width++;
}

If frame's x coordinate decreases by 1 (or more) doesn't that mean frame's width increases by 1 (or more)? Currently you change only one or the other. Same thing with height.

@Zaoshi Kaba Thank you! I cannot believe I spent so much time with such a dummy mistake!  I corrected my code and wrote frame.width++ and frame.height++ inside the if statements.

However, the result isn't perfect yet. My program still interpreting 2 separate sprites as only one, so frustrating: 

Strange... I'll work on it.

Thank you again!!

If you haven't solved it yet, here's a couple things you could try:

- Check in an image editor to make sure there's a complete row of background pixels between the two sprites that are being combined, and that there aren't any connecting pixels that are just slightly off (e.g. due to resampling).

- Do a single flood fill starting at a position that falls in one of the two sprites that are being combined, and use the debugger or debug logging to try to identify why the flood fill is crossing the gap. Due to the number of pixels involved, stepping through the whole thing or reading through detailed log information might be impractical, but there should be ways to work around that (for example, set things up so that the debugger breaks only when the flood fill gets near the gap between the two sprites).

I (apparently) found a solution!! 

 @Zakwayda Thank you for the advice. I checked the image in an editor and yes, the problem is that between the 2 sprites there are pixels that are not fully transparent.

For anyone who has the same problem, you have to check the alpha value of the pixel, not the color, like I did. In this case, the color is in the following format: argb, where:

a = alpha, r = red, g = green and b = blue.

All these values are represented with 8 bits, so bits 24-31 are alpha, 16-23 are red, 8-15 are green, 0-7 are blue. So, to retrieve the alpha value of a color you can simply do color >>> 24, that is, shifting 24 bits to the right. (>>> does not keep the sign, and exists in Java, but not in other languages like C or C++. To do this in C++, for example, you have to work with unsigned types, like unsigned int).

What I had to do is check if a pixel is transparent enough to be considered as part of the background or not. Simply change the first if condition to this:

if((pixels[x+y*width] >>> 24) > threshold)

And the second one like this:

if((pixels[x+y*width] >>> 24) <= threshold) {
    continue;
}

Where threshold is the minimum value of alpha a pixel must have to be considered as non-background. You can set the threshold to the value you want, but according to my tests a value of 0x33 works fine with many images.

Thank you very much for your answers.