Texture floodfill too slow

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By livingstone

I’m trying to practice some gdscript and decided to start with one of those coloringbooks games. I had a very good expererience with Godot so far, just had one issue:

I’m trying to fill the colors in the screen using a very simple floodfill algorithm:

extends TextureRect

var fillColor : Color

func set_color(color):
	fillColor = color

func fill(x: int, y: int):
	var image = self.texture.get_data()
	flood_fill(x, y, fillColor, image)
	var imageTexture = ImageTexture.new()
	self.texture = imageTexture

func flood_fill(x: int, y: int, fillColor: Color, image : Image):
var rect = image.get_used_rect()

var visited = BitMap.new()

var toFill = []
toFill.append(Vector2(x, y))

var expectedColor : Color = image.get_pixel(x,y)

while not toFill.empty():
	var current = toFill.pop_front()

	if not rect.has_point(current):
	visited.set_bit(current, true)
	if not image.get_pixel(current.x, current.y) == expectedColor:
	image.set_pixel(current.x, current.y, fillColor)	
	for direction in [Vector2(current.x-1, current.y), Vector2(current.x+1, current.y), Vector2(current.x, current.y-1), Vector2(current.x, current.y+1)]:
		if rect.has_point(direction) and not visited.get_bit(direction): toFill.append(direction)

It is very slow. I had to cut some corners in the algorighm (e.g: using a dictionary as a set is not available in gdscript) but, although very improvable, I don’t think there is something inherently terrible in the algorithm but perhaps that I’m abusing get_pixel (can’t prove it thow I have no idea how to profile gdscript).

How to make this faster?

Update: Changed it a bit following @Zylann advice

How big is the image you are using it on? And how long is your flood fill taking? I made a paint app myself with bucket fill, and it is slow, but still usable (takes less than a second in worst case).

Note: toFill.keys()[0] will create a copy of ALL keys in the dictionary and return them as an array, I believe this can have a performance impact if you do this for every pixel.
And judging by toFill[[currentX-1, currentY]], you are creating arrays for each keys, but you could use Vector2 instead. For storing “visited” pixels, I use a BitMap.

Zylann | 2019-12-01 19:50

It’s 877x542. Thanks for the tips, I was suspecting the key copy thing, but went for hopeful thinking instead. Likewise for the array creation, assumed (as I know nothing about the internals of gdscript) than it would be lighter than an object.

I’ll try both changes and let you know, thanks.

livingstone | 2019-12-01 20:42

With my own floodfill implementation I think 877x542 would take about a second to complete (just a blank canvas with some spiral drawing so the flood fills the whole image). How long is it taking for you?

Zylann | 2019-12-02 13:51

It is in that ballpark figure, something between 1 and 3 seconds, depending on the contents.

livingstone | 2019-12-02 15:09