 |
Attention | Topic was automatically imported from the old Question2Answer platform. |
 |
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()
imageTexture.create_from_image(image)
self.texture = imageTexture
func flood_fill(x: int, y: int, fillColor: Color, image : Image):
var rect = image.get_used_rect()
var visited = BitMap.new()
visited.create(image.get_size())
var toFill = []
toFill.append(Vector2(x, y))
image.lock()
var expectedColor : Color = image.get_pixel(x,y)
while not toFill.empty():
var current = toFill.pop_front()
if not rect.has_point(current):
continue
visited.set_bit(current, true)
if not image.get_pixel(current.x, current.y) == expectedColor:
continue
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)
image.unlock()
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