gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Flood fill algorithm

#4677 - sgeos - Sun Apr 06, 2003 9:24 pm

Do you suppose the stack would survive a recursive flood fill algorithm on a 32 by 32 map under the worst conditions? 64 by 64? I could always use an iterative approach:

unsigned short fill_map[0x1000];
unsigned long current_fill = 0;

I've actually never done a flood fill before. I don't need to keep track of 64 * 64 points in an iterative solution. Time to work on this. At any rate, any thoughts on the recursive method?

-Brendan

#4686 - ArnoldLayne - Mon Apr 07, 2003 2:18 am

The simple but bad way of doing it recursively is to fill the starting pixel, then up down left and right. It tends to blow the stack and it's slow.

A much better way is to work on a scan line at a time (also called "spans"). From the starting pixel, draw a horizontal line to the left and right until you hit a different color. After the whole line is drawn, scan from left to right above it and recurse. Then scan from left to right below and recurse.

Code:

we want to fill over O and stop when we hit color Y
X is the fill color

YYYYY
YOYOY
YOOOY
YOOOY
YYYYY


YYYYY
YOYOY
YOXOY         start pixel
YOOOY
YYYYY

YYYYY
YOYOY
YXXXY         horizontal
YOOOY
YYYYY

YYYYY
YXYXY     above ( 2 calls)
YXXXY         
YOOOY
YYYYY

YYYYY
YXYXY     
YXXXY         
YXXXY   below (1 call)
YYYYY





Does that make sense? Sorry about my sucky diagrams.

The easiest way is to recurse for each pixel as you scan above and below. This will result in a lot of calls that return right away. I'd implement it that way first. The variation is to scan longest spans and pass those offsets recursively. Foley and Van Dam describe both and have a diagram but no pseudocode. If I were coding this for GBA to be fast in bitmap modes I'd probably try to check and write 2 pixels at a time, then 1 pixel at the end if necessary.

-Kevin



sgeos wrote:
Do you suppose the stack would survive a recursive flood fill algorithm on a 32 by 32 map under the worst conditions? 64 by 64? I could always use an iterative approach:

unsigned short fill_map[0x1000];
unsigned long current_fill = 0;

I've actually never done a flood fill before. I don't need to keep track of 64 * 64 points in an iterative solution. Time to work on this. At any rate, any thoughts on the recursive method?

-Brendan

#4687 - tepples - Mon Apr 07, 2003 2:40 am

If you want to see a implementation of span-based flood filling, look at tetanus.c in the source code for TOD, which uses flood filling to determine contiguous masses of blocks.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#4694 - sgeos - Mon Apr 07, 2003 4:36 am

[quote="tepples"]If you want to see a implementation of span-based flood filling, look at tetanus.c in the source code for [url=http://www.pineight.com/gba/#tod]TOD[/url], which uses flood filling to determine contiguous masses of blocks.[/quote]

What function or set of functions am I looking for? I looked briefly, but when I saw "p.c.b[y][x]" I decided that I should probably just ask. You have a thing for printed circuit boards I take it? =P Hehehe...

-Brendan

#4697 - tepples - Mon Apr 07, 2003 5:42 am

sgeos wrote:
tepples wrote:
to see a implementation of span-based flood filling, look at tetanus.c

What function or set of functions am I looking for?

TeFloodFill() and FloodFillLoop()

Quote:
I looked briefly, but when I saw "p.c.b[y][x]" I decided that I should probably just ask. You have a thing for printed circuit boards I take it?

The answer can be found in tod.h:
Code:
typedef struct Field
{
  unsigned char b[21][10];
} Field;

typedef struct Player
{
  Field b, c;  /* block map and connection map */
/* SNIP SNIP SNIP */
} Player;

extern Player p;

So "p.c.b[][]" is the player's connection map's array of blocks. Nothing to do with a printed circuit board, although given a scanned PCB, a similar algorithm could possibly be used to find traces that lead from one part to another.

The falling algorithm I use in TOD (developed under the "Carbon" codename) is based on copying the block map to the connection map and then flood-filling contiguous areas.

Just consider p.c.b an array 21 high by 10 wide.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.