[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[pygame] Flood Fill



I am new to python and pygame. I wrote this but it needs to be faster.
Any one know how to speed it up?

It fills background color at start point to pattern. It is a little
fast but could be better I am sure.

Thanks Lots!

Douglas

PS I would be happy to add this to pygame. It would be nice to have a
spline too! :-)

# The following is a rewrite of the seed fill algorithm by Paul Heckbert.
# The original was published in "Graphics Gems", Academic Press, 1990.
#
# I have rewitten it here in python using pygame Douglas E Knapp 2005
# Fill background with patter. If you want a solid color make a 1*1
surface of your color.
# May not work if patern is bigger that surface but then again it might.
# If you make it better or faster please let me know at magick.crow(at)gmail.
# If your better is slower without more function I don't want to hear about it.
# Also faster means you can tell without looking at the thousanths
hand of your watch.
# the sk var was put in because the original had a goto in it.

def set_at((x,y), surfaceA, patternA):
	gx=x%patternA.shape[0]#width
	gy=y%patternA.shape[1]#height
	new_color=patternA[gx][gy]
	surfaceA[x][y]=new_color

def get_at((x,y), patternA):
	gx=x%patternA.shape[0]#width
	gy=y%patternA.shape[1]#height
	return patternA[gx][gy]

def push(rect,stack,(y,x,x2,dy)):# push for seed_fill
	if y+dy>=rect.bottom or y+dy<rect.top : return #don't fall of the
bottom or top of the surface.
	else : stack.append((y, x, x2, dy))
	
def seed_fillA(surface, x, y, pattern):# sk is for skip. It was a goto
    surface.lock()
    pattern.lock()
    (minx,miny,maxx,maxy)=(x,y,x,y)
    surfaceA=pygame.surfarray.pixels2d(surface)
    patternA=pygame.surfarray.pixels2d(pattern)
    if patternA==None : return
    stack=[]
    rect=Rect((0,0),surfaceA.shape)
    old_color = surfaceA[x][y]
    new_color = get_at((x, y), patternA)#make sure that surface color
is not the same as the pattern color
    if old_color == new_color : return #can't fill with same color
    if not rect.collidepoint(x, y) : return #can't fill off the surface
    push(rect,stack,(y, x, x, 1)) # needed in some cases
    push(rect,stack,(y+1, x, x, -1)) # seed segment (popped 1st)
    sk=0
    while len(stack)>0 :
	(y,x1,x2,dy)=stack.pop()
	y+=dy
	x=x1
	while x >= rect.left and surfaceA[x][y] == old_color : #bigger than
the left edge and point is old color
		#new_color=(randint(0,255),randint(0,255),randint(0,255))
		set_at((x,y), surfaceA, patternA)
		if minx>x : minx=x #find max and min x and y for Rect
		if miny>y : miny=y
		if maxx<x : maxx=x
		if maxy<y : maxy=y
		x-=1
	if( x >= x1 ) : sk=1
	if sk==0 : left = x+1
	if sk==0 and left < x1 : push(rect,stack,(y, left, x1-1, -dy)) # leak on left?
	if sk==0 : x = x1+1
	while True :
		if sk==0 :
			while x<rect.right and surfaceA[x][y] == old_color : #draw dot to
right if right needs color
				#new_color=(randint(0,255),randint(0,255),randint(0,255))
				set_at((x,y), surfaceA, patternA)
				if minx>x : minx=x
				if miny>y : miny=y
				if maxx<x : maxx=x
				if maxy<y : maxy=y
				#surface.set_at((x, y), new_color)
				x+=1
			push(rect,stack,(y, left, x-1,  dy))#look on the other side of
point, added to stack
			if x > x2+1 : push(rect,stack,(y,x2+1, x-1,  -dy)) # leak on right?
		x+=1; sk=0
		while  x <= x2 and surfaceA[x][y] != old_color : #draw right if ??
			x+=1
		left = x
		if x>x2 : break
    surface.unlock()
    pattern.unlock()
    return Rect(minx,miny,maxx-minx+1,maxy-miny+1)