# Flood Fill Algorithm

**URL:** <https://forum.defold.com/t/flood-fill-algorithm/63864>\
**Category:** Questions\
**Created:** [November 9, 2019, 7:00am UTC](https://forum.defold.com/t/flood-fill-algorithm/63864 "2019-11-09T07:00:40Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Anthroyd](https://forum-defold.b-cdn.net/user_avatar/forum.defold.com/anthroyd/32/19574_2.png) [@Anthroyd](https://forum.defold.com/u/Anthroyd)\
**Post date:** [November 9, 2019, 7:00am UTC](https://forum.defold.com/t/flood-fill-algorithm/63864/1 "2019-11-09T07:00:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Anthroyd](https://forum-defold.b-cdn.net/user_avatar/forum.defold.com/anthroyd/32/19574_2.png) [@Anthroyd](https://forum.defold.com/u/Anthroyd)\
**Post date:** [November 9, 2019, 10:07pm UTC](https://forum.defold.com/t/flood-fill-algorithm/63864/2 "2019-11-09T22:07:34Z")

</div>

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

```