How to optimize Flood Fill algorithm for a 2D sprite editor?

HashirNawaz

I am making a 2d sprite editor in Godot something like aseprite and I have used flood fill algorithm for the paint bucket tool, the only problem is that it is way too slow and I want it optimized. In the code, I have a brush size something like 20 pixels on both x and y and If I want to fill all 20x20 squares on the canvas, the flood fill algo takes too long.

dcuny

There's a detailed description of possible optimizations here:

https://en.wikipedia.org/wiki/Flood_fill

But... I don't understand how the code is working. You're taking brush-length strides across the canvas, but instead of checking to see if the entire rectangular area under the brush is the old_color, you're only testing one single pixel in the upper left corner before filling it in the most expensive way possible, instead of with fill_rect.

But I suspect you want to make sure the entire area is set to the old_color before filling it:

# check to make sure the block can be filled
for row in range(brush_size.y):
    var yy = y + row
    if yy >= bounds.y:
        # past the bottom, exit loop
        break
    for column in range(brush_size.x):
        var xx = x + row
        if xx >= bounds.x:
            # past the right edge, exit loop
            break
        if image.get_pixel(xx,yy) != old_color:
           # found a color that's not the old_color, so can't fill area
            return
# didn't return from above tests, so
# all colors in the bounds match the old color
image.fill_rect ( Rect2i(x, y), new_color )

Then again, I might just be mis-reading your code.