azsdaja/floodspill-csharp

A flood fill algorithm implementation for C#

FloodSpill — a free multi-purpose flood-fill algorithm for C#

What can you do with it?

• run a flood-fill in two-dimensional space,
• pass your own conditions for visiting positions and for stopping the flood,
• pass your own callbacks that will be executed for visited positions,
• use LIFO, FIFO or priority queue for deciding in what order positions should be visited,
• decide if you allow diagonal neighbourhood of positions or not,
• use scanline fill to double up execution speed.

It is:

• fast and memory efficient,
• easy to use,
• elastic,
• compatible with .NET Standard 1.6+ and .NET Framework 3.5+.

It can for example be used in games (roguelikes, RTS, RPG) to calculate so called influence maps, scent maps, Dijkstra maps et cætera.

---

Usage example

var wallMatrix = new bool[6, 5]; // setting up some obstacles for flood
wallMatrix[2, 0] = wallMatrix[2, 1] = wallMatrix[2, 2] 
	= wallMatrix[3, 0] = wallMatrix[3, 1] = wallMatrix[3, 2] = true;

Predicate<int, int> positionQualifier = (x, y) => wallMatrix[x, y] == false;

var floodParameters = new FloodParameters(startX: 0, startY: 0)
{
	Qualifier = positionQualifier
};
var markMatrix = new int[6, 5];

new FloodSpiller().SpillFlood(floodParameters, markMatrix);

Code above fills markMatrix with numbers indicating in how many steps the starting position is reachable:

---

More advanced example

private int[,] _positionMarkMatrix;

public void BucketFillImage(int floodStartX, int floodStartY, Color replacedColor, Color targetColor)
{
	var floodSpiller = new FloodSpiller();
	var floodParameters = new FloodParameters(floodStartX, floodStartY)
	{
		BoundsRestriction = new FloodBounds(_imageSizeX, _imageSizeY),
		NeighbourhoodType = NeighbourhoodType.Four,
		Qualifier = (x, y) => GetColor(x, y) == replacedColor,
		NeighbourProcessor = (x, y, mark) => SetColor(x, y, targetColor),
		ProcessStartAsFirstNeighbour = true
	};

	floodSpiller.SpillFlood(floodParameters, _positionMarkMatrix);
}

For more instructions and code examples see Getting started section in wiki.

---

Performance report measured with BenchmarkDotNet

(with checking for wall presence by accessing a bool[,] matrix; measured on a good 2016 laptop with Intel i7-6700HQ)

Area size	Walls blocking flood	Mode	Mean execution time	Allocated memory
20x20	No walls (open area)	Normal	33 µs	< 1kB
20x20	No walls (open area)	Scanline	15 µs	< 1kB
20x20	Sparse pillars (11% of area)	Normal	33 µs	< 1kB
20x20	Sparse pillars (11% of area)	Scanline	23 µs	< 1kB
20x20	Circular walls (50% of area)	Normal	20 µs	< 1kB
20x20	Circular walls (50% of area)	Scanline	10 µs	< 1kB
200x200	No walls (open area)	Normal	3,458 µs	16 kB
200x200	No walls (open area)	Scanline	1,158 µs	< 1kB
200x200	Sparse pillars (11% of area)	Normal	3,072 µs	16 kB
200x200	Sparse pillars (11% of area)	Scanline	2,430 µs	8 kB
200x200	Circular walls (50% of area)	Normal	2,031 µs	8 kB
200x200	Circular walls (50% of area)	Scanline	879 µs	< 1kB
2000x2000	No walls (open area)	Normal	371,000 µs	131 kB
2000x2000	No walls (open area)	Scanline	117,000 µs	< 1kB
2000x2000	Sparse pillars (11% of area)	Normal	328,000 µs	131 kB
2000x2000	Sparse pillars (11% of area)	Scanline	262,670 µs	66 kB
2000x2000	Circular walls (50% of area)	Normal	216,312 µs	66 kB
2000x2000	Circular walls (50% of area)	Scanline	88,618 µs	8 kB

floodspill-csharp's Issues

To-do list for next version

High priority:

• consider using a jagged array for mark matrix
• consider adding an optional parameter for skipping resetting the mark matrix before the run (useful when doing things like region detection)
• move start x and y parameters out of FloodParameters to save memory when running the algorithm multiple times with only x and y being different
• consider allowing to construct the parameters in a fluent manner

Low priority:

• check if using native, JIT-optimized System.Drawing.Point class wouldn't improve the performance,
• handle multi-threading,

---

Post your wishes with arguments for them.

FloodSpill algorithm that returns regions for further calculation

Hi there,

Great Work on the algorithm.

Can you please guide how can i achieve following case with your amazing library?

I have a 2D Array of Colors (100x100),

imagine this this 2d array represent following pixel art image.
https://cdn4.vectorstock.com/i/1000x1000/75/98/pixel-art-golden-coin-dollar-retro-video-game-vector-15947598.jpg

Instead of actually changing colors by flood fill, what i want is that algorithm visit all the cells, and return list of all the colorable connected regions's cells

for example if you look at image. it has 5 white color regions (4 on corners, and 1 inside). So algorithm will return 5 arrays where each array will contain point (x,y) location of each cell that makes a single region.

This way i can process each region differently.

please advise and Thank you very much for creating an efficient library.

Work on a Flattened 2D Array

Hi there,

Usually in image related formats return pixel data in a flattened 2D Array. So how can we use Flood Spill in that situation?
https://docs.unity3d.com/ScriptReference/Texture2D.GetPixels.html

Thanks