#### Archived

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

# Trying to write a filling routine - stack overflows

This topic is 5814 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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..

"take a look around" - limp bizkit

##### 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
Exood4 Studios

##### 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?

NEW (13th August): A new screenshot is up, plus diaries for week #3

John 3:16

##### 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

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 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...

NEW (13th August): A new screenshot is up, plus diaries for week #3

John 3:16

##### 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
Exood4 Studios

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

##### Share on other sites
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 on other sites
Thanks AP, would not have thought of using a queue/stack like that. Will try something like that I think.

NEW (13th August): A new screenshot is up, plus diaries for week #3

John 3:16

1. 1
Rutin
26
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 10
• 10
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
631752
• Total Posts
3002090
×