Archived

This topic is now archived and is closed to further replies.

d000hg

Trying to write a filling routine - stack overflows

Recommended Posts

I read this ages back as a fill routine:
Fill(Map *LD,WORD x,WORD y,BYTE test,BYTE set)
{
	if(test==set)return;
	LD->SetGround(x,y,set);
	if(LD->GetGround(x-1,y-1)==test)Fill(LD,x-1,y-1,test,set);
	if(LD->GetGround(x  ,y-1)==test)Fill(LD,x  ,y-1,test,set);
	if(LD->GetGround(x+1,y-1)==test)Fill(LD,x+1,y-1,test,set);
	if(LD->GetGround(x+1,y  )==test)Fill(LD,x+1,y  ,test,set);
	if(LD->GetGround(x+1,y+1)==test)Fill(LD,x+1,y+1,test,set);
	if(LD->GetGround(x  ,y+1)==test)Fill(LD,x  ,y+1,test,set);
	if(LD->GetGround(x-1,y+1)==test)Fill(LD,x-1,y+1,test,set);
	if(LD->GetGround(x-1,y  )==test)Fill(LD,x-1,y  ,test,set);
}
 
test is the value the ground must be in order to be filled, set is what we change it to. This works perfectly but on a 255x255 map I get a stack overflow. I don''t see what''s wrong, but paint programs can deal with images 1000s of pixels to a side so what can I do? Shame, I was pleased it was so easy to implement as well
Read about my game, project #1 NEW (13th August): A new screenshot is up, plus diaries for week #3
John 3:16

Share this post


Link to post
Share on other sites
its a recursive call to a function. every call allocates some data, somewhen you don''t have memory left on the stack..

you have to find a way wich is not recursive but simply a loop..

there was a discussion about this on flipcode..

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Well, in a such case recursivity is not the good way to write a fill algorithm. Prefer an iterative solution ...
The stack can''t support so much calls with the recursivity method!

__________________________



Bruno Wieckowski
Lead Programmer
Exood4 Studios

Share this post


Link to post
Share on other sites
I read this in a graphics textbook; it seems such a good way to do it. And a 255x255 map, only 65K points - doesn''t seem unreasonably high for recursion. Can I change stack size or anything, or is that generally a sign of doing things the wrong way?



Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3


John 3:16

Share this post


Link to post
Share on other sites
quote:
Original post by d000hg
I read this ages back as a fill routine:

Fill(Map *LD,WORD x,WORD y,BYTE test,BYTE set)
{
if(test==set)return;
LD->SetGround(x,y,set);
if(LD->GetGround(x-1,y-1)==test)Fill(LD,x-1,y-1,test,set);
if(LD->GetGround(x ,y-1)==test)Fill(LD,x ,y-1,test,set);
if(LD->GetGround(x+1,y-1)==test)Fill(LD,x+1,y-1,test,set);
if(LD->GetGround(x+1,y )==test)Fill(LD,x+1,y ,test,set);
if(LD->GetGround(x+1,y+1)==test)Fill(LD,x+1,y+1,test,set);
if(LD->GetGround(x ,y+1)==test)Fill(LD,x ,y+1,test,set);
if(LD->GetGround(x-1,y+1)==test)Fill(LD,x-1,y+1,test,set);
if(LD->GetGround(x-1,y )==test)Fill(LD,x-1,y ,test,set);
}


test is the value the ground must be in order to be filled, set is what we change it to. This works perfectly but on a 255x255 map I get a stack overflow. I don''t see what''s wrong, but paint programs can deal with images 1000s of pixels to a side so what can I do? Shame, I was pleased it was so easy to implement as well



Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3


John 3:16




Attend CS class->Be forced to write dummy programs that does everything in a recursive manner->Get all errors->Learn->Hate recursion->Never use them IRL.

Try to trace a recrusive mehtod on your stack...you''ll want to sell you computer and become amish.

_______________________________________________
I don''t need pointers. I know where i''m going.

Share this post


Link to post
Share on other sites
I don''t like recursion but it is an incredibly useful tool in certain situations. This seems like the perfect place to use it, is my method maybe calling extra copies when un-needed? Someone must have a fill algo from a map editor or something...



Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3


John 3:16

Share this post


Link to post
Share on other sites
I don't think graphic tools use recursion to fill areas ... Indeed recursion is an "easy" way to solve a problem (easy to write it) but is really slow compared to the iterative solution.

You can in the worst case, change the stack value ... but there is no need to do it.

I would advice you to use a technic like filling polygons in 3D rendering to screen. Try to get informations on "boundaries filling" and scanlines techniques...

__________________________



Bruno Wieckowski
Lead Programmer
Exood4 Studios



[edited by - brunow on August 17, 2002 10:11:51 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
One of your problems is that your fill algorithm doesn''t fill from the inside out. So, theoretically you''ve got 65000+ function calls deep when you have a 256 x 256 grid.

Here is a quick and dirty fill algorithm that you might use. It is certainly not optimal, but it is much better than 65000 recursive calls --


  
class Point
{
public:
Point(int new_x, int new_y) : x(new_x), y(new_y) {}
int x;
int y;
};

Fill(Map* grid, Point startLocation, char originalColor, char newColor)
{
queue<Point> hotSpots;
Point current;
if (grid->GetGround(startLocation.x, startLocation.y) == originalColor)
{
grid->SetGround(current.x, current.y, newColor);
hotSpots.push(startLocation);
while (!hotSpots.empty())
{
current = hotSpots.top();
hotSpots.pop();
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if (grid->GetGround(current.x + i, current.y + j) == originalColor)
{
hotSpots.push(Point(current.x + i, current.y + j));
grid->SetGround(current.x + i, current.y + j, newColor);
}
}
}
}
}
}

Share this post


Link to post
Share on other sites
Thanks AP, would not have thought of using a queue/stack like that. Will try something like that I think.



Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3


John 3:16

Share this post


Link to post
Share on other sites