Region FloodFill

Harag · July 15, 2016, 8:49am

@Chuck_Esterbrook Thanks for the new version, I tried it this morning, but it seems to run a lot slower - taking a couple of seconds to complete 186 country colour changes. In the mean time I think I’ve now come up with a solution to the whole problems.

Texture2D historyMap = TextureManager.GetSpriteTextureData(SpriteTexture.Asset.HistoryMap).Texture2D;
_historyMapData = historyMap.GetPixels();

When I load in the blank map (it’s transparent for sea, and white for the countries/region), I get get the pixel colours and store them in a class wide Color[] variable
In my Update() method (I update all the regions when a key is pressed - at the moment, just random colours - Key press is to simulate a turn by turn change. I’ve put the flood fill into a “util” class and pass the Color[] data to it after getting the target colour of the point(x,y);

if (_updateMap)
{
var randomColor = new Color(BaseGame.RND.Next(32, 255), BaseGame.RND.Next(32, 255), BaseGame.RND.Next(32, 255));
Texture2D historyMap = TextureManager.GetSpriteTextureData(SpriteTexture.Asset.HistoryMap).Texture2D;
foreach (Region region in _historyMapRegions)
{
region.Color = GetRandomColor();
Color targetColor = _historyMapData[region.X + region.Y * historyMap.Width];
Util.FloodFill(region.X, region.Y, historyMap.Width, historyMap.Height, targetColor, region.Color, _historyMapData);
}
_updateMap = false;
}
I then draw the end result to the screen, by setting the Colour[] data to the texture and then simply draw it as normal.

Texture2D historyMap = TextureManager.GetSpriteTextureData(SpriteTexture.Asset.HistoryMap).Texture2D;
historyMap.SetData(_historyMapData);
int leftBorder = (renderTarget2D.Width - historyMap.Width) / 2;
int topBorder = (renderTarget2D.Height - historyMap.Height) / 2;
spriteBatch.Draw(historyMap, new Vector2(leftBorder, topBorder), Color.White);
Here is my final version of the Flood Fill - Yes it’s recursive, but I’ve figured out why it was getting a stack overflow error - the first IF statement seems to stops this issue. By hold down the key and running the update() method constantly the drawing reminds me of the old commodore 64 loading screens I’m very happy with the final result.

public static void FloodFill(int x, int y, int w, int h, Color targetColor, Color newColor, Color[] currentData)
{
if (currentData[y * w + x] != targetColor)
return;
currentData[y * w + x] = newColor;
if (y > 0 && currentData[(y - 1) * w + x] != newColor)
FloodFill(x, y - 1, w, h, targetColor, newColor, currentData);
if (y < h - 1 && currentData[(y + 1) * w + x] != newColor)
FloodFill(x, y + 1, w, h, targetColor, newColor, currentData);
if (x > 0 && currentData[y * w + (x - 1)] != newColor)
FloodFill(x - 1, y, w, h, targetColor, newColor, currentData);
if (x < w - 1 && currentData[y * w + (x + 1)] != newColor)
FloodFill(x + 1, y, w, h, targetColor, newColor, currentData);
}

Again, many thanks for all your help on this.

(apologies for the formatting, can’t work out how it works with multiple sections)

EDIT: Recursive - Still get the stack error but only when I tried to pain the background - don’t seem to get it for the countries I have on the map, so it’s very much a size issue. I’ve implemented your “maxDepth” you did in an earlier post to stop it from crashing.

Chuck_Esterbrook · July 15, 2016, 9:32am

The recursive algo is elegant and understandable, but it’s a ticking time bomb imo. MaxDepth reduces the chances, but even that’s just a guess. The max safe depth will vary per platform and could even change with an update to .NET or Mono.

But I’m glad you’re getting results and having fun. There is a faster version of the flood fill where horizontal lines are filled in rather than just pixels. Per wikipedia “In most cases this scanline algorithm is at least an order of magnitude faster than the per-pixel one.” https://en.wikipedia.org/wiki/Flood_fill#Scanline_fill

Harag · July 15, 2016, 9:37am

@Chuck_Esterbrook Apologies for another post, I’m just updating here in case anyone else is interested. Yet more changes, I tried the queue filling again and this time it seemed quite quick, not sure what I did wrong before. anyway I’ve not managed to get the whole of the “sea” (as well as country borders as they are also the same transparent colour) filled in using queue, and it’s quick enough for what I need. Changed it to use an extension: here is the full code I have so far:

if (_updateMap)
{
	var randomColor = new Color(BaseGame.RND.Next(32, 255), BaseGame.RND.Next(32, 255), BaseGame.RND.Next(32, 255));
	Texture2D historyMap = TextureManager.GetSpriteTextureData(SpriteTexture.Asset.HistoryMap).Texture2D;
	foreach (Region region in _historyMapRegions)
	{
		region.Color = GetRandomColor();
		_historyMapData.FloodFill(new Point(region.X, region.Y), historyMap.Width, historyMap.Height, region.Color);
	}
	_updateMap = false;
}


public static void FloodFill(this Color[] data, Point hotspot, int width, int height, Color replacementColor, Color? targetColor = null)
{
	int x = hotspot.X;
	int y = hotspot.Y;
	if (x < 0 || x >= width)
		throw new IndexOutOfRangeException($"x = {x} for texture of width {width}");
	if (y < 0 || y >= height)
		throw new IndexOutOfRangeException($"y = {y} for texture of width {height}");
	if (targetColor == null)
		targetColor = data[y * width + x];

	Util.FloodFillByQueue(data, hotspot, width, height, replacementColor, targetColor.Value);
}


public static void FloodFillByQueue(Color[] data, Point p, int w, int h, Color replacementColor, Color targetColor)
{
	queue.Clear();
	queue.Enqueue(p);
	do
	{
		p = queue.Dequeue();
		if (data[p.Y * w + p.X] != targetColor)
			continue;

		data[p.Y * w + p.X] = replacementColor;
		// up
		if (p.Y > 0 && data[(p.Y - 1) * w + p.X] == targetColor)
			queue.Enqueue(new Point(p.X, p.Y - 1));
		// down
		if (p.Y < h - 1 && data[(p.Y + 1) * w + p.X] == targetColor)
			queue.Enqueue(new Point(p.X, p.Y + 1));
		// left
		if (p.X > 0 && data[p.Y * w + (p.X - 1)] == targetColor)
			queue.Enqueue(new Point(p.X - 1, p.Y));
		// right
		if (p.X < w - 1 && data[p.Y * w + (p.X + 1)] == targetColor)
			queue.Enqueue(new Point(p.X + 1, p.Y));
	} while (queue.Count > 0);
}

@Chuck_Esterbrook Just got your post as I was typing this… Yes the maxDepth is a ticking time bomb as you say, hence another look at the queue way, which is what I’ve gone for now. I’ll take a look at the scanline_fill, to see if I can work it out, but what I have at the moment is fast enough.

Harag · July 15, 2016, 9:50am

@Chuck_Esterbrook Worked out why the queue was slow initially - it wasn’t the actual queue it was the extension method that contained the following:

var data = new Color[width * height];
texture.GetData(data);  // <<<--THIS IS WHAT IS MAKING IT TO GO SLOW

if (targetColor == null)
	targetColor = data[y * width + x];

Util.FloodFillByQueue(data, hotspot, width, height, replacementColor, targetColor.Value);
texture.SetData(data);

Because it’s creating the data Color array and populating it with GetData() - this is what is taking the time (about a second or so) so it’s noticeably slower on this PC between each update, so by creating this array and PRE populating it in the LoadContent() method and changing the extension method to work on the array rather than the texture, it’s much smoother.

Chuck_Esterbrook · July 15, 2016, 4:22pm

I see. You’re saying that since you are doing multiple flood fills, it’s better to get the data once and do them all.

Harag · July 15, 2016, 5:13pm

Exactly @Chuck_Esterbrook I have 186 “countries/regions” on the map I have and each “turn” several could/will be coloured in, it’s a history map I’m building - so if you’re on turn 20, then the map will display what the countries for turn 1, then 2, then 3 etc - showing how the war changed over the 20 turns. so by having the map data in memory on first load, I can just fill the data and then set the data to the texture after each update.

Chuck_Esterbrook · July 16, 2016, 1:39am

Couple more things:

In my testing, the app would sometimes throw OutOfMemoryException after a long time. I needed to guard against the colors being the same:

if (replacementColor == targetColor.Value) return;

Also, I tried a Stack<Point> in place of the Queue<Point> just out of curiosity and picked up about 7.85% in speed.

Harag · July 17, 2016, 8:44am

Interesting about using Stack over Queue, I’ll have to try this and time my flood fill too to see if it makes a difference.

Since you’ve all been so helpful I thought I would share the result of my filling, here are a couple of pictures, the first one is the original black/whit0 (click image to open album).

[Album] Monogame - Region History map testing

Alkher · July 28, 2016, 7:30am

A queue, logically, removes the picked element (Filo) and moves the others, so the more you have the slower it is.
(I don’t know the internal code of Queue in .NET, if it only keeps an index or wahtever)
Whereas a stack should not have to move the bunch of items it contains. (Fifo) so it’s faster in certain cases.

Harag · July 28, 2016, 7:38am

Actually thinking about it, this makes complete sense now - thanks @Alkher.

Jjagg · July 28, 2016, 10:26am

If you make a circular queue things don’t need to be moved, though you need to now the maximum number of items.