Flood Fill Algorithm

Questions
1

I’m searching through a 1024 x 512 image made up of either (1) air pixels, or (2) land pixels. I’ve been having trouble with implementing a proper flood_fill() algorithm–it’s just not fast enough. Also, it may be the case that you can only call a recursive function so many times before getting a stack overflow exception…

Does anybody know of a good way of going about this?

Edit: I’ve built a rather interesting solution! Working very fast and effectively. I will post in a day or two how I did this for future readers.

2 Likes
2

So it turns out that an iterative solution for flood fill is much faster than a recursive solution. The idea here is pretty simple:
(1) fill the current pixel
(2) check if its neighbors are valid fill candidates
(3) if they are, add each to the queue
(4) repeat until queue is empty

-- Fills an area on the canvas using flood fill
-- colored_noise: noise grid containing colors instead of height values
-- x: pixel x position to begin flooding
-- y: pixel y position to begin flooding
-- target_color: color to erase
-- fill_color: color to fill
local function flood_fill(colored_noise, x, y, target_color, fill_color)
	if not flood_fill_queue_test(colored_noise, x, y, target_color, fill_color) then return end
	local fill_count = 0
	local queue = {}
	table.insert(queue, { x, y })
	while not is_empty(queue) do
		x, y = queue[1][1], queue[1][2]
		local index = y * CANVAS_WIDTH + x + 1
		colored_noise[index] = fill_color
		fill_count = fill_count + 1
		table.remove(queue, 1)
		if flood_fill_queue_test(colored_noise, x + 1, y, target_color, fill_color) then table.insert(queue, { x + 1, y }) end
		if flood_fill_queue_test(colored_noise, x - 1, y, target_color, fill_color) then table.insert(queue, { x - 1, y }) end
		if flood_fill_queue_test(colored_noise, x, y + 1, target_color, fill_color) then table.insert(queue, { x, y + 1 }) end
		if flood_fill_queue_test(colored_noise, x, y - 1, target_color, fill_color) then table.insert(queue, { x, y - 1 }) end
	end
	return fill_count
end
5 Likes