Home
- Run
Install-Package FloodSpillcommand in Package Manager Console, - or find FloodSpill package in Tools —> NuGet Package Manager —> Manage NuGet Packages for Solution... window in Visual Studio.
Flood-fill is an algorithm which goes through two-dimensional space by joining more and more of its fragments which are adjacent to fragments already visited. The fragments we join to flood must satisfy some conditions; they can be processed in any way.
Above you see a flood starting from bottom-left corner, marking visited positions with numbers and not spilling to the forbidden area in the middle.
Here is rough pseudocode of current FloodSpill implementation:
set mark values of all positions to int.MaxValue (indicating they are unmarked)
mark starting position with 0
add starting position to queue
while queue contains positions:
visited_position = take position from queue
perform user-defined processing on visited_position
if visited_position satisfies stop condition:
STOP
for each unmarked neighbour matching given bounds and conditions:
mark neighbour with a number bigger by 1 than visited_position's mark
perform user-defined processing on neighbour
add neigbhour to queue
if any neighbour satisfied stop condition:
STOPYou can find the examples and play around with them in Examples.cs file in FloodSpill.Tests project.
- No walls, FIFO (default) queue:
var markMatrix = new int[10, 5];
var floodParameters = new FloodParameters(startX: 1, startY: 1);
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
3333345678
2222345678
1112345678
1012345678
1112345678
*/- No walls, LIFO queue:
var markMatrix = new int[10, 5];
var floodParameters = new FloodParameters(new LifoPositionQueue(), 1, 1);
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
5433345678
5222345678
11123edd99
1012fedcaa
111gggdcbb
*/- No walls, priority queue:
var markMatrix = new int[10, 10];
Position center = new Position(5, 5);
Func<Position, Position, int> distanceToCenterComparer = // favours positions closer to center
(first, second) => Position.Distance(center, first).CompareTo(Position.Distance(center, second));
var priorityQueue = new PriorityPositionQueue(distanceToCenterComparer);
var floodParameters = new FloodParameters(priorityQueue, 1, 1);
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
8888888888
7777777778
7666666678
7655555678
7654445678
7633345678
7222345678
1112355678
1012666678
1117777778
*/- Scanline flood, no walls, FIFO (default) queue:
var markMatrix = new int[8, 10];
var floodParameters = new FloodParameters(4, 2);
new FloodScanlineSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
54321234
54321234
54321234
54321234
54321234
54321234
54321234
54320234
54321234
43211123
*/- Disallow diagonal neighbourhood:
var markMatrix = new int[10, 5];
var floodParameters = new FloodParameters(1, 1)
{
NeighbourhoodType = NeighbourhoodType.Four
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
43456789ab
323456789a
2123456789
1012345678
2123456789
*/- Bounds:
var markMatrix = new int[10, 5];
var floodParameters = new FloodParameters(7, 7)
{
BoundsRestriction = new FloodBounds(minX: 5, minY: 5, sizeX: 5, sizeY: 3)
// markMatrix will be accessed with offset, so that we don't get IndexOutOfRangeExceptions
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/*results in:
##########
##########
21012#####
21112#####
22222#####
*/- Negative bounds:
var markMatrix = new int[10, 5];
var floodParameters = new FloodParameters(-99, -99)
{
BoundsRestriction = new FloodBounds(minX: -100, minY: -100, sizeX: 10, sizeY: 5)
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/*results in:
3333345678
2222345678
1112345678
1012345678
1112345678- Some walls:
var markMatrix = new int[10, 5];
Predicate<int, int> positionQualifier = (x, y) => x%2==0 || y == 0;
var floodParameters = new FloodParameters(0, 0)
{
Qualifier = positionQualifier
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
4#5#7#9#b#
3#4#6#8#a#
2#3#5#7#9#
1#2#4#6#8#
0123456789
*/- Using callbacks for processing neighbours and visiting positions:
var markMatrix = new int[3,2];
Action<int, int, int> neighbourProcessor =
(x, y, mark) => Console.WriteLine($"Processing {x}, {y} as a neighbour with {mark} mark.");
Action<int, int> positionVisitor =
(x, y) => Console.WriteLine($"Visiting {x}, {y}");
var floodParameters = new FloodParameters(0, 0)
{
NeighbourProcessor = neighbourProcessor,
SpreadingPositionVisitor = positionVisitor
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
/* results in:
Visiting 0, 0
Processing 0, 1 as a neighbour with 1 mark.
Processing 1, 0 as a neighbour with 1 mark.
Processing 1, 1 as a neighbour with 1 mark.
Visiting 0, 1
Visiting 1, 0
Processing 2, 0 as a neighbour with 2 mark.
Processing 2, 1 as a neighbour with 2 mark.
Visiting 1, 1
Visiting 2, 0
Visiting 2, 1
*/- Scanline flood, using callbacks for processing neighbours and visiting positions:
var markMatrix = new int[3,5];
Action<int, int, int> neighbourProcessor =
(x, y, mark) => Console.WriteLine($"Processing {x}, {y} as a neighbour with {mark} mark.");
Action<int, int> positionVisitor =
(x, y) => Console.WriteLine($"Visiting {x}, {y}");
var floodParameters = new FloodParameters(1, 1)
{
NeighbourProcessor = neighbourProcessor,
SpreadingPositionVisitor = positionVisitor
// due to scanline nature, not all positions will be VISITED
};
new FloodScanlineSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
Visiting 1, 1
Processing 1, 0 as a neighbour with 1 mark.
Processing 0, 0 as a neighbour with 1 mark.
Processing 2, 0 as a neighbour with 1 mark.
Processing 1, 2 as a neighbour with 1 mark.
Processing 1, 3 as a neighbour with 1 mark.
Processing 1, 4 as a neighbour with 1 mark.
Visiting 0, 0
Processing 0, 1 as a neighbour with 2 mark.
Processing 0, 2 as a neighbour with 2 mark.
Processing 0, 3 as a neighbour with 2 mark.
Processing 0, 4 as a neighbour with 2 mark.
Visiting 2, 0
Processing 2, 1 as a neighbour with 2 mark.
Processing 2, 2 as a neighbour with 2 mark.
Processing 2, 3 as a neighbour with 2 mark.
Processing 2, 4 as a neighbour with 2 mark.
Mark matrix of size 3, 5.
212
212
212
202
111
*/- Neighbour stop condition:
var markMatrix = new int[10, 5];
Action<int, int, int> neighbourProcessor =
(x, y, mark) => Console.WriteLine($"Processing {x}, {y} as a neighbour with {mark} mark.");
Action<int, int> positionVisitor =
(x, y) => Console.WriteLine($"Visiting {x}, {y}");
Predicate<int, int> neighbourStopCondition = (x, y) =>
{
if (x > 1)
{
Console.WriteLine($"{x}, {y} causing stop!");
return true;
}
return false;
};
var floodParameters = new FloodParameters(0, 0)
{
NeighbourProcessor = neighbourProcessor,
SpreadingPositionVisitor = positionVisitor,
NeighbourStopCondition = neighbourStopCondition
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
Visiting 0, 0
Processing 0, 1 as a neighbour with 1 mark.
Processing 1, 0 as a neighbour with 1 mark.
Processing 1, 1 as a neighbour with 1 mark.
Visiting 0, 1
Processing 0, 2 as a neighbour with 2 mark.
Processing 1, 2 as a neighbour with 2 mark.
Visiting 1, 0
Processing 2, 0 as a neighbour with 2 mark.
2, 0 causing stop! <-- still the rest of (1, 0)'s
neighbours will be processed before actual stop
Processing 2, 1 as a neighbour with 2 mark.
2, 1 causing stop!
##########
##########
22########
112#######
012#######
*/- Spreading position stop condition:
var markMatrix = new int[10, 5];
Action<int, int, int> neighbourProcessor =
(x, y, mark) => Console.WriteLine($"Processing {x}, {y} as a neighbour with {mark} mark.");
Action<int, int> positionVisitor =
(x, y) => Console.WriteLine($"Visiting {x}, {y}");
Predicate<int, int> spreadingPositionStopCondition = (x, y) =>
{
if (x > 1)
{
Console.WriteLine($"{x}, {y} causing stop!");
return true;
}
return false;
};
var floodParameters = new FloodParameters(0, 0)
{
NeighbourProcessor = neighbourProcessor,
SpreadingPositionVisitor = positionVisitor,
SpreadingPositionStopCondition = spreadingPositionStopCondition
};
new FloodSpiller().SpillFlood(floodParameters, markMatrix);
string representation = MarkMatrixVisualiser.Visualise(markMatrix);
Console.WriteLine(representation);
/* results in:
Visiting 0, 0
Processing 0, 1 as a neighbour with 1 mark.
Processing 1, 0 as a neighbour with 1 mark.
Processing 1, 1 as a neighbour with 1 mark.
Visiting 0, 1
Processing 0, 2 as a neighbour with 2 mark.
Processing 1, 2 as a neighbour with 2 mark.
Visiting 1, 0
Processing 2, 0 as a neighbour with 2 mark.
Processing 2, 1 as a neighbour with 2 mark.
Visiting 1, 1
Processing 2, 2 as a neighbour with 2 mark.
Visiting 0, 2
Processing 0, 3 as a neighbour with 3 mark.
Processing 1, 3 as a neighbour with 3 mark.
Visiting 1, 2
Processing 2, 3 as a neighbour with 3 mark.
Visiting 2, 0
2, 0 causing stop!
##########
333#######
222#######
112#######
012#######
*/