Wii stack size, and flood fill algorithm

Hi,

I've got 2 questions here.
I think I need to implement a 4-way floodfill using a queue as storage, does anyone know how I would go about it (tad cheeky :P)

basically need something to look like this.. where w is and edge, and x is the center.

 5 4 4 4 4 4 4 w 5 5
 5 4 3 3 3 3 3 w 4 5
 5 4 w 2 2 2 2 3 4 5
 5 5 w 1 1 1 2 3 4 5
 6 6 w w x 1 2 3 4 5
 7 7 7 w 1 1 2 w 4 5
 8 8 8 w w 2 2 w 5 5
 9 9 9 9 w 3 3 w 5 6
10 9 8 8 w 4 4 4 5 6
10 9 8 7 w 5 5 5 5 6
10 9 8 7 6 6 6 6 6 6

Also,I dont want to get a stack overflow does anyone know what size stack the wii has?

Dunno stack size but you can always implement a recursive algorithm in an iterative fashion. I did one back in '96 for my icon editor, it was a max 64x64 grid and an array of 800 integers was enough to flood the entire grid. I would have posted the source code if it was an easy to understood one...

About the queue, it depends...

Here is the questions

1. Will you be doing this often?
2. What size of display area are we talking about?

If 1: yes, 2: large area expressed in a queue

Either you should find a clever algorithm that operates directly on the queue which will be hard. Or you should switch to the matrix representation which is easy to traverse and will be fast. Or keep a separate datatype for this job like a hashtable so that you can access a pixel fast using given x and y coordinates. Your hashtable key could be y*width + x....

It's not that hard to allocate memory without using the stack.

Is there any reason not to use a field/matrix representation?

To be honest, I have no idea, why the data should represented as a queue.
Would would be the benefit?



Stacksize:
The stack should grow from one end of the free memory. So it depends on your memory usage, your malloc() implementation.
So it would be 64M - size of your dol - size of global variables.

Does the Wii's hardware MMU even notice memory access violations, or store any metdata?
Memory is accessed directly, without a page table.



Edited 1 time(s). Last edit at 07/07/2009 01:16AM by daniel_c_w.

Ok,

I've got a 300x300 grid that I want a many-to-one shortest path algorithm.
An ascending flood fill will do that, and "curve" round walls.

I tried doing a recursive one but the display went all screwy (green screen, then diff coloured lines all over the place) then it just stopped responding. I am assuming this was due to a stack overflow ( as I dont know what else it could be), unless i just slowed it right down.

Basically I wanted to have the algorithm run for 6 players and run every game cycle (prob slow it right down) so maybe use threading or have algorithm run every X cycles...


The grid was going to hold the wall data too, so that any "fighters" (separate class with x,y position) will move to an area of lower gradient potential (wall definded as very high number).

I heard that using a queue (non-recursive) uses less space in memory so might be better for this, as opposed to using a stack...

my algorithm is:

void flood_fill(int team, int x, int y, int value)
{
  if(grad_grid[team][x][y] == 0)
  {
    grad_grid[team][x][y] = value +1;
      
    flood_fill(team, x+1, y,value);
    flood_fill(team, x-1, y,value);
    flood_fill(team, x, y+1,value);
    flood_fill(team, x, y-1,value);
  }
}

Your algorithm looks wrong to me:

-There is no stop-condition,
-you will eventually do it out of bounds,
-you do not raise the value
(every field will either have a 0 or the value)
-it only checks straight connection, not diagonals, but that may be your intention,
-it touches all regions more than once
(for example: your first inner function call is a "go down", but it will call a "go up" as its second inner function call)



Edited 2 time(s). Last edit at 07/07/2009 01:31PM by daniel_c_w.

my mistake... this is the algorithm

void bucket_fill(int x, int y, int value)
{
    if (grid[x, y] == 0 || (grid[x, y] - value)>0)
        {
            grid[x, y] = value;
            if (x < map_size-1)
                bucket_fill(x + 1, y, value+1);
            if(x>0)
                bucket_fill(x - 1, y, value+1);
            if (y < map_size-1)
                bucket_fill(x, y+1, value+1);
            if(y>0)
                bucket_fill(x, y-1, value+1);
        }            
}

It is triggered by calling

bucket_fill(x,y, 0);

The stop condition is when all cells have the "correct number" as eventually if (grid[x, y] == 0 || (grid[x, y] - value)>0) will return false on every cell.
The only reason I havent checked the diagonal is because this would raise the amount of recursions (?) and get stack overflow quicker.

It will check regions twice as need to verify value (but shouldnt matter as it'l call it the main if will return false and function will exit)

unless I am getting terribly confused.

I tried implementing in a windows app too, and got a "StackoverflowException"



Edited 1 time(s). Last edit at 07/07/2009 04:01PM by steaky1212.

My first understanding was (because of your other question in another thread) you are keeping the map in a queue...

So you are actually using a grid...

Somehow what you want to do differs a bit from a standard flood fill... a standard one should look like

int match=1; //the color/value you are replacing (filling)
int replacement = 2; //fill color/value

void bucket_fill(int x, int y)
{
if (grid[x, y] == match)
{
grid[x, y] = replacement;
if (x < map_size-1)
bucket_fill(x + 1, y);
if(x>0)
bucket_fill(x - 1, y);
if (y < map_size-1)
bucket_fill(x, y+1);
if(y>0)
bucket_fill(x, y-1);
}
}

for the standard algorithm, it's not wise to pass fill color and replacement color everytime since they won't change... you can keep them global and set them when required... though don't know your actual requirements...

Also if it performs slow or you want to make it perform slow so that flood can be seen than how you implement the algorithm matters too, there are some visual examples in wikipedia... if you use a queue as a medium storage then it seems it looks better...

[en.wikipedia.org]

To give you an idea of how it can be implemented without a recursive function still using supplementary storage as stack or queue (in my code it's a stack)

Code snippet from my rather old sprite editor... (I admit it's ugly..)

#define RANGE_CHECK(A,B) ( ( (A) < rowspr+SMALLY) && ( (A)>=SMALLY ) && ( (B)>=SMALLX ) && ( (B) < colspr+SMALLX) )
void floodf(void)
{
int stack[800]; // Stack for 400 Positions
// This big Stack is needed because of bad floodfill algorithm done by me..
// it eats a lot of space as it goes through multiple choices,
// it starts pulling of positions until it has no place to go.
// Most of the positions in the stack becomes unavailable since they are covered
// by previous steps and this is the weak side of the algorithm.
// But it is fast enough filling 64x64 area

// The algorithm is recursive but implemented with goto
// to avoid stack overflow


int *stackp;
char cdraw,cpool;
int si,sj,i,j;

if (getsimplegridarea (&dg,xplace,yplace,&i,&j) >NOT_IN_CELL)
{

cdraw=current_col;

i+=SMALLY;j+=SMALLX;

cpool=getpixel(j,i);

if (cpool!=cdraw)
{
	putpixel(j,i,cdraw);
	save_undo_sprite();
	setcolor(cdraw);
	stackp=stack;

recurse : ;

	// Going Up
	if ( (getpixel(j,i-1)==cpool)&&RANGE_CHECK(i-1,j))
		{
		*stackp++=i;
		*stackp++=j;
		     while ((getpixel(j,i-1)==cpool)&&RANGE_CHECK(i-1,j))
			{
			i--;
			putpixel(j,i,cdraw);
			}
		goto recurse;
		}

else
	// Right
	if ((getpixel(j+1,i)==cpool)&&RANGE_CHECK(i,j+1))
		{
		*stackp++=i;
		*stackp++=j;

		     while ((getpixel(j+1,i)==cpool)&&RANGE_CHECK(i,j+1))
			{
			j++;
			putpixel(j,i,cdraw);
			}
		goto recurse;
		}
else


	// Down

	if ((getpixel(j,i+1)==cpool)&&RANGE_CHECK(i+1,j))
		{
		*stackp++=i;
		*stackp++=j;

		     while ((getpixel(j,i+1)==cpool)&&RANGE_CHECK(i+1,j))
			{
			i++;
			putpixel(j,i,cdraw);
			}
		goto recurse;
		}
	// Left

else
	if ((getpixel(j-1,i)==cpool)&&RANGE_CHECK(i,j-1))
		{
		*stackp++=i;
		*stackp++=j;
		     while ((getpixel(j-1,i)==cpool)&&RANGE_CHECK(i,j-1))
			{
			j--;
			putpixel(j,i,cdraw);
                        }
                goto recurse;
                }

if (stackp!=stack)
        {
        si=*(stackp-2);         // Copy top of stack to variables si,sj...
        sj=*(stackp-1);
        if (si==i&&sj==j)
                {
                stackp--;      // Position Pulled out of stack..
		stackp--;
                goto recurse;
                }
        else                      // Move in the direction of position
                {
                if ((si-i)>0) i++;
                else
                if ((si-i)<0) i--;

                if ((sj-j)>0) j++;
                else
                if ((sj-j)<0) j--;
                goto recurse;
                }
        }

	update_to_grid();  // Make grid aware of flood

}  // End of color control

} // End of if


} // End of main block...

Edited 1 time(s). Last edit at 07/07/2009 08:46PM by I.R.on.

This might help a bit, it fill a horizontal line and then the lines above/below it, using not that much stack space, and it's pretty fast:

static void map_flood_line_area(struct map_data *m, int x, int y, int areanum) 
{ 
  int fillL, fillR, i; 
  int in_line = 1; 
  
  /* find left side, filling along the way */ 
  fillL = fillR = x; 
  while( in_line ) 
  { 
    m->area[fillL+y*m->xs] = areanum; 
 
    fillL--; 
    in_line = (fillL < 0) ? 0 : (m->area[fillL+y*m->xs] == AREA_FILLABLE);
  } 
  fillL++; 
  /* find right side, filling along the way */ 
  in_line = 1; 
  while( in_line ) 
  { 
    m->area[fillR+y*m->xs] = areanum; 
 
    fillR++; 
    in_line = (fillR >= m->xs) ? 0 : (m->area[fillR+y*m->xs] == AREA_FILLABLE);
  }
  fillR--;
  /* search top and bottom */
  for(i = fillL; i <= fillR; i++)
  {
    if( y > 0 && m->area[i + (y - 1) * m->xs] == AREA_FILLABLE)
        map_flood_line_area(m, i, y - 1, areanum);
    if( y < (m->ys-1) && m->area[i + (y + 1) * m->xs] == AREA_FILLABLE)
        map_flood_line_area(m, i, y + 1, areanum);
  }
}