Flood fill?

Beginners Welcome!
1

I need a flood fill for a game I’m working on, but the ‘usual’ method crashes, I assume a stack overflow…

void floodFill(int x,int y){

    if(x%10==0){
        // so I can watch the fill...
        mygame.display.update();
    }

    // recursive flood fill
    if(x<0 || x>mygame.display.width || y<0 || y>mygame.display.height) return;
    int col = mygame.display.getPixel(x,y);
    if(col==0){ // bg colour
        mygame.display.drawPixel(x,y);

        floodFill(x+1,y);
        floodFill(x-1,y);
        floodFill(x,y+1);
        floodFill(x,y-1);
    }
    return;
}

Does anyone have a fill routine I can ‘borrow’ that works on Pokitto?

2

I think that crashes because nothing prevents a pixel from being filled more than once, resulting in an infinite loop.

1 Like
3

You can put CheckStack() call anywhere in your recursive function to verify that the stack is the problem. It is very fast to check.

4

Yes it does, the function returns if a pixel is not 0.

5

Ah, so the fill color is never 0?
Also, your upper bounds are off by 1.

6

Try this:

void floodFill(unsigned x, unsigned y, uint8_t fillColour)
{
	if((x % 10) == 0)
	{
		// so I can watch the fill...
		Pokitto::Display::update();
	}

	if((x >= Pokitto::Display::width) || (y >= Pokitto::Display::height))
		return;
		
	unsigned colour = Pokitto::Display::getPixel(x,y);
	if(colour != fillColour)
	{
		Pokitto::Display::drawPixel(x, y, fillColour);
		
		if(x < Pokitto::Display::width)
			floodFill(x + 1, y);
			
		if(x > 0)
			floodFill(x - 1, y);
			
		if(y < Pokitto::Display::height)
			floodFill(x, y + 1);
			
		if(y > 0)
			floodFill(x, y - 1);
	}
}

If that doesn’t work then the problem is almost certainly that the return stack can’t handle it and you’ll have to take a corecursive approach and maintain your own stack.

To be honest, I’m not really suprised it’s falling over.
If you tried to fill from point 0,0 the stack could potentially reach 220 frames on top of whatever was there before it.

Recursion is really only suitable when you won’t need much depth or when the process uses a tail-call which can be optimised away.

7

Your bounds are also off… it’ll try to fill x=width, which drawPixel ignores. The next iteration will try again and again, in an infinite loop.

1 Like
8

I didn’t bother to check the bounds,
I just assumed @spinal’s logic was right.
Nothing a couple of = won’t fix.

9

The logic was good enough to start testing. It’s most definitively a stack, the function calls itself at least a few hundred times, it is a well known issue with this type of flood fill routine.

10

Then you’d be best off going corecursive and maintaining your own stack:

struct Point
{
	unsigned x;
	unsigned y;
};

void floodFill(unsigned x, unsigned y, uint8_t fillColour)
{
	std::stack<Point> stack = std::stack<Point>();

	if((x % 10) == 0)
	{
		// so I can watch the fill...
		Pokitto::Display::update();
	}

	// If you're using C++11, replace all uses of stack.push(Point(x, y) with stack.emplace(x, y);
	stack.push(Point(x, y));
	
	while(!stack.empty())
	{
		Point point = stack.top();
	
		if((point.x >= Pokitto::Display::width) || (point.y >= Pokitto::Display::height))
			return;
			
		unsigned colour = Pokitto::Display::getPixel(point.x, point.y);
		if(colour != fillColour)
		{
			Pokitto::Display::drawPixel(point.x, point.y, fillColour);
			
			if(point.x < Pokitto::Display::width)
				stack.push(Point(point.x + 1, point.y));
				
			if(point.x > 0)
				stack.push(Point(point.x - 1, point.y));
				
			if(point.y < Pokitto::Display::height)
				stack.push(Point(point.x, point.y + 1));
				
			if(point.y > 0)
				stack.push(Point(point.x, point.y - 1));
		}

		// Almost forgot this bit
		stack.pop();
	}	
}

In case the stack functions aren’t obvious, here’s the stdlib reference

Unrelated: it’s just occurred to me that the PokittoLib is using C11 headers to get its fixed-width integer types.

11

…\Mine\main.cpp|76|error: ‘stack’ is not a member of ‘std’|

12

Did you test with >= for width and height?
The non-recursive method takes things off the stack and puts them in the heap, but there’s not that much heap either, so it might not solve the problem.

13

I didn’t, but my test has a border around the screen for safety while I’m testing.

14

Did you #include <stack>?

1 Like
15

Ninja’d by 2 minutes.

@spinal,
For the record, if you ever see anything with the prefix std::,
it’s almost certainly from the standard library and you need an include for it.

Standard library includes don’t have a .h after them and are generally included with angle brackets.
If in doubt, check the docs.

2 Likes
16

Not at first, but then I get –

c:\program files (x86)\embitz\1.11\share\em_armgcc\arm-none-eabi\include\c++\5.4.1\bits\stl_algobase.h|243|error: macro “min” passed 3 arguments, but takes just 2|

and about 20 other errors.

17

This sounds like a conflict with the AVR lib. Try adding #define DISABLEAVRMIN in the beginning of the file.

18

That didn’t do anything.

19

Really? Odd, min is not supposed to be a macro.
Defining DISABLEAVRMIN before including the PokittoLib is supposed to prevent it from making that macro.

20

…\Mine\main.cpp|97|error: no matching function for call to ‘Point::Point(unsigned int&, unsigned int&)’|