Fast Flood Fill in Pygame?

Question

I am creating a simple game in Pygame for my kids. It involves intersecting random complex curves. Some of the intersections can be coloured in different colours. I have implemented a flood fill algorithm which works well for handling areas created by intersecting complex curves, but is very slow.

Couple of questions:

Is there a built-in flood fill algorithm I should be using (I could not find one) that can handle the above use case?
If not, then outside of algorithm improvements, how could I dramatically speed up a flood fill to make it near instantaneous to the human eye? (I am thinking about going low level but not sure how to go about this)

Flood Fill code:

# replaces all points of same starting colour, 
# with a new colour, up to a border with 
# different starting colour
def do_flood_fill(surface, x, y, newColor):
    theStack = [(x, y)]
    oldColor = surface.get_at((x,y))    # Get starting colour
    while len(theStack) > 0:
        x, y = theStack.pop()
        if surface.get_at((x,y)) != oldColor:
            continue
        surface.set_at((x,y),newColor)
        # pygame.display.update()   # Show fill - very slow
        theStack.append( (x + 1, y) )  # right
        theStack.append( (x - 1, y) )  # left
        theStack.append( (x, y + 1) )  # down
        theStack.append( (x, y - 1) )  # up

Post some code, so we can see what you have and what you can improve. — Bálint
– Bálint, Commented Mar 18, 2016 at 13:37

Community · Accepted Answer · 2020-06-16 10:15:23Z

Read the docs, they can be very helpful. For both get_at and set_at, there's this comment:

Getting and setting pixels one at a time is generally too slow to be used in a game or realtime situation. It is better to use methods which operate on many pixels at a time like with the blit, fill and draw methods - or by using surfarray/PixelArray.

This function will temporarily lock and unlock the Surface as needed.

The reason why get_at/set_at are slow is partly hinted at here:

They temporarily lock/unlock the Surface every call
They require conversion from the underlying pixel format to the standard pygame Color class

Both of which aren't bad, but become very slow when you're doing a flood fill, which could involve hundreds or thousands of pixels.

One of the recommended approaches is to use PixelArray. It can be constructed from a Surface, then you update it as if it's a 2D array, preferably using integer pixel values instead of Colors to minimise conversions (hint: convert newColor using map_rgb()). Here's some example code:

pxarray = pygame.PixelArray(surface)
pxarray[x, y] = 0xFF00FF

del pxarray

https://stackoverflow.com/a/12959670/2038264

Fortunately for flood fill, you don't need to know the exact Color you're filling into, only if the next pixel has the same value, so you can avoid conversions in the inner loop.

Finally, delete the PixelArray. This is because it implicitly locks/unlocks the Surface during its lifetime. This is covered in the docs but can be easy to miss; read them carefully:

During its lifetime, the PixelArray locks the surface, thus you explicitly have to delete it once its not used anymore and the surface should perform operations in the same scope. A simple : slice index for the column can be omitted.

Just for completeness, make sure to catch IndexError which occurs when you try to access pixels outside the Surface, which is easy to do in a flood fill algorithm.

In general, when you need to update a bunch of pixels in one go, it's best to lock the whole surface once, perform pixel operations in the underlying format, then unlock at the very end. This applies to pygame surfaces as well as SDL surfaces, GDI images and DirectX textures, as it relates to how graphics hardware works.

648trindade · Accepted Answer · 2016-03-28 04:28:38Z

You can try first finding the points next to the border, storing them in a list and then using the list on filled_polygon function.

Make sure to not reappend points already seen to the theStack. Poping from stack and ignoring the repeated ones costs some valuable processing.

Based on my recent knowledge in SDL, manipulate points on a Texture/Surface tends to be slow because wrapping functions in pygame probably (not sure, not looked at the source. If you can, look and correct this answer) need to lock the Surface, manipulate the pixel and then unlock the Surface at each time you use the set_at/get_at wrapping functions.

Stack Exchange Network

Fast Flood Fill in Pygame?

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Fast Flood Fill in Pygame?

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions