Region FloodFill

Hi all,

Sorry if this might be a dumb question, but what I’m wanting to do is fill in a region with a certain colour. Is this possible, and if so how?

I have a map - say USA states, or Europe etc, and the map is basically just a white background and black borders for the states/countries. I’ve saved a single X/Y location within each area (this is where I will put some “icons” but before I place the icons I would like to fill in the “state/country” in a colour for “ownership” of said area.

Now going back to my VB 3 days I know there was some sort of “Flood Fill” command that would do this, but with monogame, I’m not sure what is the best way to do this.

Here is an example of a map I mean:

http://www.worldatlasbook.com/europe/europe-blank-map.html

As they are quite a few “regions” on the map, it might be better to do all the colouring in a new image, then send the new image to the spritebatch.

Can anyone point me to some example code that can do this?

Many thanks

MonoGame wraps the API for OpenGL and DirectX. Rendering with OpenGL and DirectX requires use of primitives (triangles or lines) which are made up of vertices. SpriteBatch is a convenient higher level API for batching dynamic (changes every frame) textured rectangles which are really two triangles.

To fill an area you need to compute the appropriate decomposition of that area into triangles and submit it for rendering. However, this is probably too complicated for people who are new to graphics programming since it requires a certain level of knowledge of the rendering pipeline. The quickest and simplest solution is to use SpriteBatch to render a “white” texture which represents what you want to be filled and using a Color parameter when calling SpriteBatch.Draw(...) to tint the texture.

Hi

Thanks for the response

Just looked up what I used way back in the old days - Link below. I’m after something like that. Do you have any example of how to do this?

The API you want with pens / brushes to render poly-lines and shapes doesn’t exist in MonoGame because it doesn’t exist in OpenGL / DirectX 9. Direct2D has the API you want but there are no bindings in MonoGame to Direct2D because that API can’t be used on every platform. A similar API to Direct2D could be built using a shader and triangle tessellation algorithm but it’s probably not worth the development time if you can use SpriteBatch to solve the original problem in a different way.

The old method of doing pixel operations would be done on a byte buffer representing the screen, and then that byte buffer set on a texture to be drawn to the screen.

The alternative is to convert the outlines of the regions to a polyline and then triangulate the polygon. This creates a set of triangles that fill the shape and can be rendered using the GPU.

Hmm, I have an idea that’s not too hard to implement. You can use spriteBatch as @LithiumToast suggested. I don’t think a polyline is a great idea because the borders are not straight even a little bit.

If you use the colored map and map each regions color to the desired color for that region that should do the trick. The colors on the map aren’t unique, but we can get around that. My idea is to render parts of the colored map to a render target while mapping 1 specific color in a part to another color and clipping other colors. If you render parts that do not have more than 1 region with the same color in them, you can give a different color to each region. Since we’ll draw the parts with a spritebatch, one part should be a collection of rectangles (you’ll need more than one in case one region can’t fit in one rectangle without having parts of another region with the same color in it).

I think it’s easiest to define a region with its part and source color since you hardcode some information about the regions anyway (like you do now with the coordinate for the icons or a name or ID, since I’m assuming you’'ll want to refer to a region in a way). You’ll also need a pixel shader that maps a specific color to another one and clips everything with a different color. With the regions defined and the shader implemented you can draw the map with the regions in a certain color as follows:

  1. Load the colored map and the shader
  2. Create a render target to draw the map with your colors
  3. Draw the full map to the RT with a spritebatch with the shader and source color for the shader set to black to draw the region edges
  4. Draw each region to the RT i.e. draw the rectangles of its part with the source color set to the color of the region and the destination color you want. Use source and destination rectangle of spritebatch for the part rectangles.
  5. That’s it :slight_smile: if you want to change the color of a region you’ll only have to redraw that region like you did in step 4!

I hope that made some sense. If it didn’t but this sparked your interest, I’ll make a drawing to explain in more detail tomorrow (I can’t right now because I’m on mobile, this was already a pain to write :stuck_out_tongue: ).

Thanks all for the replies. Much appreciated.

@Jjagg - Mobile - Arrh how I hate them, so thank you for typing all that on one of those things. Given the responses this is going to be harder than I first thought. The overall idea I have is sort of a “history timeline” for the player on a turn based game. So the regions will be different colours and not just one fixed colour. e.g. say Player one is England and is in red, and turn one he attacks France, France colour will then be red, Spain then attacks France, that then changes the colour to Yellow, England retakes France from Spain it goes Red again.

So when the player “views history”, it basically will show the time clock Turn 1, 2, 3, 4 etc, and colour France accordingly, over the X number of turns the player can see how the countries were loss/won over time.

I’m fairly new to all the graphical side of things and what can be done - Yes I can draw a basic Textrure2D images at position X,Y but nothing really much more than that.

Here is another idea I’ve just thought of:

Say my overall map is 1500 x 800 with all the regions drawn, and then I use a graphical application (e.g. paint.net) to cut out a rectangle of each region (not including the black lines) so the image is just a WHITE shape of the country and the rest is transparent (example below) could I then draw this image in a colour at a certain location on a render target - similar to creating a 1x1 white pixel image and drawing it in another colour?

If so then I could cut out all the regions and save them as textures and then just draw them onto the 1500x800 image…

Example Image of France (ignore the shading):

Example of UK (but the “sea” will be transparent and the land will be pure white:

Thanks again all.

That is a lot easier than what I proposed :stuck_out_tongue: Sounds like a good idea!

Thanks @Jjagg , you just replied as I was about to post this:

I’ve knocked up something and it seems to work - worked out how to change the colour of the white image too, this is a little example of what I’ve come up with:

  1. Resolution is the virtual screen manager class I have, this sets up the design area and the view size.
public GameRegionTest()
{
	IsMouseVisible = true;
	_graphics = new GraphicsDeviceManager(this);
	Content.RootDirectory = "Content";
	//Change Virtual Resolution
	Resolution.Initialize(_graphics);
	Resolution.SetVirtualResolution(1920, 1080);
	Resolution.SetResolution(960, 540, false);

}

  1. In the draw() I then call a sub method “DrawRegions()” which then draws the regions to a renderTarget2D, returning a texture2D

  2. Draw the returned texture 2D to the screen.

4, I also draw out each of the regions to the screen. - I’m guessing this is the WORSE way to do it and #2 is the better way.

protected override void Draw(GameTime gameTime)
{
	Resolution.BeginDraw();

	_spriteBatch.Begin(SpriteSortMode.Immediate, BlendState.AlphaBlend, SamplerState.PointClamp, null, null, null, null);

	// DRAW All the regions on a render target, then draw the full image to the screen
	Texture2D regions = DrawRegions(_graphics.GraphicsDevice);
	_spriteBatch.Draw(regions, new Vector2(0,0), Color.White);

	// Draw each region individually.
	_spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 0, _regionUK.Height), Color.Red);
	_spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 1, _regionUK.Height), Color.Yellow);
	_spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 2, _regionUK.Height), Color.Blue);
	_spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 3, _regionUK.Height), Color.Green);
	_spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 4, _regionUK.Height), Color.Brown);

	_spriteBatch.End();

	base.Draw(gameTime);
}

private Texture2D DrawRegions(GraphicsDevice graphicsDevice)
{
	var renderTarget2D = new RenderTarget2D(graphicsDevice, Resolution.VirtualViewport.Width, Resolution.VirtualViewport.Height);
	var spriteBatch = new SpriteBatch(graphicsDevice);

	graphicsDevice.SetRenderTarget(renderTarget2D);

	spriteBatch.Begin();
	spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 0, 0), Color.Red);
	spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 1, 0), Color.Yellow);
	spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 2, 0), Color.Blue);
	spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 3, 0), Color.Green);
	spriteBatch.Draw(_regionUK, new Vector2(_regionUK.Width * 4, 0), Color.Brown);
	spriteBatch.End();

	graphicsDevice.SetRenderTarget(null);

	return (Texture2D)renderTarget2D;
}

Yes, at the moment, I’m drawing the same region and in different colours, but I’m sure if I have a list of the region “objects” with a X,Y location to draw them I can build up a “world map” using this method to the render target object then return the final texture to be drawn to the screen.

Does this sound the best way to do what I want to achieve?

Thanks again

That will work and fit with how modern GPUs work.

Oops I think I did something wrong.

In the DrawRegions method I added a loop to draw 128 red regions every 12 pixels apart and my PC started to hang / slow reponse, even when I closed the game down it took ages to end (so long I rebooted the PC) after it took about 5 minutes to load the task manager I managed to see the memory was at 100%. Not sure what I’ve done wrong it appears that that there is clearly something I’m not doing right.

Any one have any idea ? doing the above at 60 fps seems to be bad. This is the for loop I added in just before the spriteBatch.End() call:

for (int r = 0; r < 128; r++)
{
	spriteBatch.Draw(_regionUK, new Vector2(r * 12, _regionUK.Height*2), new Color(r, 0, 0));
}

Do I need to dispose something or is it simply too much to do @ 60 fps

EDIT:

Think I’ve solved the issue - Using() - I’ve added a using on the “DrawRegions” call

using (Texture2D regions = DrawRegions(_graphics.GraphicsDevice))
			{...}

and then within the draw regions method i’ve added a using to the spritebatch:

using (var spriteBatch = new SpriteBatch(graphicsDevice))
			{...}

Seems to be running much better now, even after increasing the loop to 256.

It is best to allocate the render target and sprite batch once during init and re-use them. Allocating and disposing every frame is not efficient and can cause allocation issues over time.

@KonajuGames Thanks for that, I’ve created a class wide spritebatch and rendertarget variable, but in my DrawRegions method it doesn’t draw the regions if I use the class wide spritebatch:

Below is my DrawRegions method, the Commented out bit of code where it uses the local spritebatch variable works, and the new bit below doesn’t draw anything - I think it’s because the local sprite batch is being passed the graphics device with the new “SetRenderTarget” on it.

private void DrawRegions(GraphicsDevice graphicsDevice, RenderTarget2D renderTarget2D)
{
	graphicsDevice.SetRenderTarget(renderTarget2D);
	graphicsDevice.Clear(Color.Transparent);

	DrawWater(graphicsDevice, renderTarget2D);

	Texture2D regionUK = Resources.Images["Region_UK"];
	//using (var spriteBatch = new SpriteBatch(graphicsDevice))
	//{
	//	spriteBatch.Begin();
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 0, 0), Color.Red);
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 1, 0), Color.Yellow);
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 2, 0), Color.Blue);
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 3, 0), Color.Green);
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 4, 0), Color.Brown);
	//	spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 5, 0), Color.DarkMagenta);

	//	for (int r = 0; r < 512; r++)
	//	{
	//		spriteBatch.Draw(regionUK, new Vector2(r * 3, regionUK.Height * 2), new Color(r / 2, 0, 0));
	//	}

	//	spriteBatch.End();
	//}


	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 0, 0), Color.Red);
	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 1, 0), Color.Yellow);
	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 2, 0), Color.Blue);
	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 3, 0), Color.Green);
	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 4, 0), Color.Brown);
	_spriteBatch.Draw(regionUK, new Vector2(regionUK.Width * 5, 0), Color.DarkMagenta);

	for (int r = 0; r < 512; r++)
	{
		_spriteBatch.Draw(regionUK, new Vector2(r * 3, regionUK.Height * 2), new Color(r / 2, 0, 0));
	}
	graphicsDevice.SetRenderTarget(null);
}

EDIT - Nevermind, I’ve now solved this by adding a
_spriteBatch.Begin(…) and .End() in the method

I’m not following why he cannot do a flood fill on the Texture2D itself. MonoGame will draw any texture and you can manipulate textures however you like. They’re just data.

Here’s an extension method I whipped up for FloodFill():

public static class Texture2DExtensions {

	public static void FloodFill(this Texture2D tex, Point p, Color c) {
		if (tex == null) throw new ArgumentNullException(nameof(tex));
		int w = tex.Width;
		int h = tex.Height;
		int x = p.X;
		int y = p.Y;
		if (p.X < 0 || p.X >= w) throw new IndexOutOfRangeException($"p.X = {x} for texture of width {w}");
		if (p.Y < 0 || p.Y >= h) throw new IndexOutOfRangeException($"p.Y = {y} for texture of width {h}");
		var data = new Color[w * h];
		tex.GetData(data);
		var targetColor = data[y * w + x];
		// OMGRECURSIVEFLOODFILLRUNFORYOURLIVES!
		_FloodFill(x, y, w, h, targetColor, c, data);
		tex.SetData(data);
	}

	static void _FloodFill(int x, int y, int w, int h, Color targetColor, Color replaceColor, Color[] data) {
		data[y * w + x] = replaceColor;
		// up
		if (y > 0 && data[(y - 1) * w + x] == targetColor) _FloodFill(x, y - 1, w, h, targetColor, replaceColor, data);
		// down
		if (y < h-1 && data[(y + 1) * w + x] == targetColor) _FloodFill(x, y + 1, w, h, targetColor, replaceColor, data);
		// left
		if (x > 0 && data[y * w + (x - 1)] == targetColor) _FloodFill(x - 1, y, w, h, targetColor, replaceColor, data);
		// right
		if (x < w-1 && data[y * w + (x + 1)] == targetColor) _FloodFill(x + 1, y, w, h, targetColor, replaceColor, data);
	}

}

Usage:

someTexture.FloodFill(somePoint, someColor);
  1. It’s very inefficient and could overflow your stack. If you go with this approach you will want to use one of the more efficient algos described at https://en.wikipedia.org/wiki/Flood_fill
  2. You might also choose to make the data buffer static, only reallocating it when it needs to be bigger.
  3. This works on your image, but not well because jpeg has compression artifacts from being lossy. Your best bet is to get a png with no artifacts. Your second best bet is to tweak the FloodFill to have a threshold calculation instead of an exact color comparison with the equality operator.

Thoughts?

P.S. The syntax highlighting for this forum screws up indentation of this source code, at least in the Preview area during composition.

@Chuck_Esterbrook Many thanks for this and the code, I’m happy that it can actually be done, though not sure how fast this will be, but will certainly have a play around with what I have in mind for it. I’ve only recently learned you can get the colour of each pixel, so actually understand your code and what it’s doing. :slightly_smiling: Images - I generally use PNG format for images due to the loss % of jpegs, only really useful for photos. At the moment I’m currently playing around with each region being a separate white image and then drawing them in position to look like a map, and with the draw function using Color.Whatever to draw the region in a colour, seems to be working well so far.

Thanks

Sure you can do it, but I wouldn’t because

  1. Efficiency (I know, premature optimization and all that…)
  2. Flood fill won’t do for this map because of islands and parts of a country seperated from the bulk of the region
  3. Drawing each country seperately with a spritebatch is really easy and only requires a little work beforehand and hardly any implementation

@Jjagg The “history map” I’m looking at trying to do is something I did ages ago with VB3 and using a picture box and the built in floodfill, hence the initial question - the map I have is only about 900x700 in size and contains about 150 or so regions. I do have a pixel X,Y location within each region to start as filling point, so it doesn’t matter if they are islands or not on the map, each region has a clear thick black border. I’ve quickly tried the recursive flood fill this morning provided by @Chuck_Esterbrook but ran into call stack issues with it so might have to look at doing it slightly differently (maybe a data buffer array or something - yes I basically dropped the code in the Draw() method to see what would happen.

no.3 Drawing each region separately - It does seem straightforward to do I agree, but a lot of work before hand, to cut out each region into separate images and then to note down the top left x,y position within the overall “world”/texture so I can place them onto the screen in the required colour at the correct position.

Again, just like to thank everyone for being so helpful on this, much appreciated

I was going to say that too: That cutting out the countries ahead of time in a pixel perfect fashion seems like a lot of upfront work. Also, I don’t think efficiency will ultimately be a problem because there are options like computing during a load screen, caching in memory, caching on disk, etc.

While playing around with this, I also ran into the stack limit. Here is a mildly improved version that bails at an arbitrary stack depth:

	public static class Texture2DExtensions {

		// to-do: if this is to be used in real situations, then either the textures have to be very small
		// or the algo has to be replaced with something far more efficient.
		// see https://en.wikipedia.org/wiki/Flood_fill

		public static void FloodFill(this Texture2D tex, Point p, Color c) {
			// http://community.monogame.net/t/region-floodfill/7896/13
			if (tex == null) throw new ArgumentNullException(nameof(tex));
			int w = tex.Width;
			int h = tex.Height;
			int x = p.X;
			int y = p.Y;
			if (x < 0 || x >= w) throw new IndexOutOfRangeException($"p.X = {x} for texture of width {w}");
			if (y < 0 || y >= h) throw new IndexOutOfRangeException($"p.Y = {y} for texture of width {h}");
			var data = new Color[h * w];
			tex.GetData(data);
			var targetColor = data[y * w + x];
			// OMGRECURSIVEFLOODFILLRUNFORYOURLIVES!
			_FloodFill(x, y, w, h, targetColor, c, data, 0);
			tex.SetData(data);
		}

		const int MaxDepth = 6400;

		static void _FloodFill(int x, int y, int w, int h, Color targetColor, Color replaceColor, Color[] data, int depth) {
			data[y * w + x] = replaceColor;
			depth++;
			if (depth > MaxDepth) return;
			// up
			if (y > 0 && data[(y - 1) * w + x] == targetColor) _FloodFill(x, y - 1, w, h, targetColor, replaceColor, data, depth);
			// down
			if (y < h - 1 && data[(y + 1) * w + x] == targetColor) _FloodFill(x, y + 1, w, h, targetColor, replaceColor, data, depth);
			// left
			if (x > 0 && data[y * w + (x - 1)] == targetColor) _FloodFill(x - 1, y, w, h, targetColor, replaceColor, data, depth);
			// right
			if (x < w - 1 && data[y * w + (x + 1)] == targetColor) _FloodFill(x + 1, y, w, h, targetColor, replaceColor, data, depth);
		}

	}

While that’s more friendly, it doesn’t change the fact that you’ll have to implement one of the other flood fill algos at the wikipedia page to make this usable.

@Chuck_Esterbrook Thanks for the new version - I’ve been playing around with it today and think I got it working. What I did is at the start of the scene created TWO Color[w*h] arrays (initial & current), and passed both of these to the recursive flood fill, in there I checked that the initial is target color and that the current is NOT yet the new colour, if so, call self again and then change the current array (initial never gets changed - always the black & white image), this seems to have stopped the stack overflow so I think it got into some sort of mess before. When I get back in the office tomorrow I can post up the code, picture paints a 1000 words and all that. So far, for what I need, I think even this recursive filling is good enough - seems to work fine on my rubbish work PC, so a gaming rig won’t have an issue. :slightly_smiling:

You’re welcome. I couldn’t let it lie though. Here is one more version that won’t ever blow the stack and also provides the option to pass in the target color:

public static class Texture2DExtensions {

	/// <summary>
	/// Flood fills an area with the given color.
	/// Uses the color under the point as the target color
	/// (just like a paint program) unless you pass an
	/// explicit targetColor.
	/// Not thread safe due to static collection reuse.
	/// May throw ArgumentNullException and IndexOutOfRangeException.
	/// Reference https://en.wikipedia.org/wiki/Flood_fill
	/// </summary>
	public static void FloodFill(this Texture2D tex, Point p, Color replacementColor, Color? targetColor = null) {
		// http://community.monogame.net/t/region-floodfill/7896
		if (tex == null) throw new ArgumentNullException(nameof(tex));
		int w = tex.Width;
		int h = tex.Height;
		if (p.X < 0 || p.X >= w) throw new IndexOutOfRangeException($"p.X = {p.X} for texture of width {w}");
		if (p.Y < 0 || p.Y >= h) throw new IndexOutOfRangeException($"p.Y = {p.Y} for texture of width {h}");
		var data = new Color[h * w];
		tex.GetData(data);
		if (targetColor == null) targetColor = data[p.Y * w + p.X];
		FloodFillByQueue(data, p, w, h, replacementColor, targetColor.Value);
		tex.SetData(data);
	}

	static Queue<Point> queue = new Queue<Point>(2048);

	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);
	}

}