floodfill algorithm not working correctly in pygame

Question

I tried implementing the floodfill algorithm in pygame, it works but doesn't fills the entire shape recursively. I tried a lot but i am not able to debug the issue. Kindly help me find it out. Here's my source code.

import pygame

pygame.init()
SCREEN = WIDTH, HEIGHT = 288, 512
win = pygame.display.set_mode(SCREEN, pygame.NOFRAME)

clock = pygame.time.Clock()
FPS = 60

# COLORS **********************************************************************

WHITE = (255, 255, 255)
BLUE = (30, 144,255)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLACK = (0, 0, 0)

colors = [BLUE, RED, GREEN]

# TEXT ************************************************************************

font = pygame.font.SysFont('freesansbold', 26)
text = font.render('Flood Fill Algo test', True, WHITE)

clicked = False
polygon = []

def floodfill(x, y, old, new):
    pixel = win.get_at((x, y))
    if pixel != old:
        return
    elif pixel == new:
        return
    else:
        print(x, y)
        pygame.draw.circle(win, new, (x, y), 1)
        pygame.display.update()

        floodfill(x-1, y, old, new)
        floodfill(x+1, y, old, new)
        floodfill(x, y-1, old, new)
        floodfill(x, y+1, old, new)
        floodfill(x-1, y-1, old, new)
        floodfill(x-1, y+1, old, new)
        floodfill(x+1, y-1, old, new)
        floodfill(x+1, y+1, old, new)

class Rect:
    def __init__(self, x, y, c):
        self.x = x
        self.y = y
        self.c = c
        self.rect = pygame.Rect(x, y, 30, 30)

    def draw(self):
        pygame.draw.rect(win, self.c, self.rect)

r1 = Rect(WIDTH-40, 10, RED)
r2 = Rect(WIDTH-40, 45, GREEN)
r3 = Rect(WIDTH-40, 85, BLUE)

rects = [r1, r2, r3]
color = RED

running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE or event.key == pygame.K_q:
                running = False

        if event.type == pygame.MOUSEBUTTONDOWN:
            pos = event.pos
            btn = pygame.mouse.get_pressed()
            if btn[0]:
                clicked = True

            elif btn[2]:
                if pos[0] < WIDTH - 50:
                    floodfill(pos[0], pos[1], (0,0,0), color)

            if pos[0] > WIDTH - 50:
                for r in rects:
                    if r.rect.collidepoint(pos):
                        color = r.c

        if event.type == pygame.MOUSEBUTTONUP:
            clicked = False

        if event.type == pygame.MOUSEMOTION:
            if clicked:
                pos = event.pos
                btn = pygame.mouse.get_pressed()
                if btn[0]:
                    if pos[0] < WIDTH - 50:
                        pygame.draw.circle(win, WHITE, pos, 5)
                
    pygame.draw.rect(win, WHITE, (0, 0, WIDTH-50, HEIGHT), 3)
    pygame.draw.rect(win, WHITE, (WIDTH-50, 0, 50, HEIGHT), 2)

    win.blit(text, (60, 40))

    for rect in rects:
        rect.draw()

    clock.tick(FPS)
    pygame.display.update()

pygame.quit()

Here's the sample output of my code, As you can see the shape is filled but not completely. It stops after reaching the starting position from which the algorithm starts.

I tried debugging it by printing the different positions but with no luck. Also is there any better way to debug recursions in these type of problems.

Answer 1

A circle with radius 1 draws more than 1 pixel. Either set a single pixel instead of drawing a circle:

pygame.draw.circle(win, new, (x, y), 1)

win.set_at((x, y), new)

or step left and up by 2 pixels:

floodfill(x-2, y, old, new)
floodfill(x+1, y, old, new)
floodfill(x, y-2, old, new)
floodfill(x, y+1, old, new)

I recommend using a loop instead of recursion to avoid exceeding the recursion limit:

def floodfill(x, y, old, new):
    draw_list = [(x, y)]
    while draw_list:
        p = draw_list[-1]
        draw_list.pop()
        pixel = win.get_at(p)
        if pixel == old:
            win.set_at(p, new)
            new_p = [(p[0]+1, p[1]), (p[0]-1, p[1]), (p[0], p[1]+1), (p[0], p[1]-1)]
            draw_list += new_p`