Pygame Flood Fill“相比之下超出了最大递归深度”

Question

我目前正在开发一个绘图程序，并尝试实现这个洪水填充程序。

我尝试将其改编为 Pygame，但由于某种原因，它似乎只能部分工作；如果我保留 x 行（x+1，x-1），程序将崩溃。如果我删除 1 x 线，那么一切都会正常。我不确定是什么原因造成的。任何确定问题的帮助将不胜感激，并且比完全重写更好。

full_canvas = flood_fill(full_canvas,mouse_history[-1][0],mouse_history[-1][1],brush_colour,old_colour,mouse_history[-1])

def flood_fill(image,x,y,new_colour,old_colour,start_pixel):
    pixel = image.get_at((x,y))
    pixel_colour = (pixel[0],pixel[1],pixel[2])
    if x < 0 or x > image.get_width() or y < 0 or y > image.get_height() or pixel_colour == new_colour or pixel_colour != old_colour or pixel[3] < 1:
        return
    image.set_at((x,y),new_colour)
    flood_fill(image,x+1,y,new_colour,old_colour,start_pixel)
    flood_fill(image,x-1,y,new_colour,old_colour,start_pixel)
    flood_fill(image,x,y+1,new_colour,old_colour,start_pixel)
    flood_fill(image,x,y-1,new_colour,old_colour,start_pixel)

return image

Answer 1

当我几乎完成重写你的递归方法时，我注意到你正在检查

x > image.get_width() or y > image.get_height()

。我不熟悉 Pygame，但通过快速在线搜索我可以看出该图像似乎是 0 索引的。这意味着您实际上想要检查

x >= image.get_width() or y >= image.get_height()

。宽度 100 可能意味着 0...99 可用，而 100 已经超出范围。您可以尝试仅更改这一点，看看是否有帮助。此外，应该在使用

image.get_at((x,y))

之前进行检查。

因此，您的前几行可能应该如下所示：

if x < 0 or x >= image.get_width() or y < 0 or y >= image.get_height():
    return
pixel = image.get_at((x,y))
pixel_colour = (pixel[0],pixel[1],pixel[2])
if pixel_colour == new_colour or pixel_colour != old_colour or pixel[3] < 1:
    return
image.set_at((x,y),new_colour)
...

如果这没有帮助，您可以尝试以下实现。我将您的递归更改为深度优先方法。待处理的 (x,y) 点在列表中进行管理，已访问的点在集合中进行跟踪（以允许快速比较）。

顺便说一下，pygame 文档中有一个关于 image.get_at() 和

image.set_at()

的警告：

一次获取和设置一个像素通常太慢，无法在游戏或实时情况下使用。最好使用一次对多个像素进行操作的方法，例如 blit、fill 和 draw 方法 - 或者使用 pygame.surfarray/pygame.PixelArray。

如果代码太慢，请考虑使用 pygame.PixelArray 而不是 get_at/set_at。我快速浏览了一下，似乎很合适。

def flood_fill(image, x, y, new_colour, old_colour):
    visited = set()
    pending = [(x, y)]

    while pending:
        x, y = pending.pop()

        if x < 0 or x >= image.get_width() or y < 0 or y >= image.get_height():  # out of bounds
            continue

        pixel = image.get_at((x, y))
        pixel_colour = (pixel[0], pixel[1], pixel[2])

        if pixel_colour == new_colour or pixel_colour != old_colour or pixel[3] < 1:
            continue

        image.set_at((x, y), new_colour)

        for point in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if point not in visited:
                pending.append(point)
                visited.add(point)