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
Trying to write a filling routine - stack overflows
I read this ages back as a fill routine:
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
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
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
The stack can''t support so much calls with the recursivity method!
__________________________
Bruno Wieckowski
Lead Programmer
Exood4 Studios
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
Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3
John 3:16
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.
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
Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3
John 3:16
The simple fact is that you can''t recurse for every pixel! There''s just too many.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
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]
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]
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 --
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);}}}}}}
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
Read about my game, project #1
NEW (13th August): A new screenshot is up, plus diaries for week #3
John 3:16
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement