I’m using a fill algorithm in my pixel art project which gives an error “stackoverflow” only if I scale up the project. For example if i do a fill for a 64 64 image it doesn’t give me any error but if I go ahead to 170 170 it gives a stackoverflow error. I’m sure that the algorithm is not going in an infinite loop since it works for 64*64. So what is the limit before which codea gives a stackoverflow error? I’m using the algorithm from this page http://en.wikipedia.org/wiki/Flood_fill , the one at the bottom of the page under the heading Large scale behaviour (four way flood fill).
Can you post the code?i am fairly sure there is something wrong in it.
@Jmv38 Here’s the part related to the fill.
Pixelate is a function which sets the colour of the pixel. And (a,b) are the coordinates. And self.Image is the image. And self.r… Is the colour of the pixel chosen and self.rc…is colour of the adjacent pixel.
function Grid:Flood(a, b)
self:Pixelate(a, b)
if a + 1 <= self.Image.width and b <= self.Image.height and a + 1 >= 1 and b >= 1 then
self.rc, self.gc, self.bc, self.ac = self.Image:get(a + 1, b)
if self.rc == self.r and self.gc == self.g and self.bc == self.b and self.ac == self.a then
self:Pixelate(a + 1, b)
self:Flood(a + 1, b)
end
end
if a - 1 <= self.Image.width and b <= self.Image.height and a - 1 >= 1 and b >= 1 then
self.rc, self.gc, self.bc, self.ac = self.Image:get(a - 1, b)
if self.rc == self.r and self.gc == self.g and self.bc == self.b and self.ac == self.a then
self:Pixelate(a - 1, b)
self:Flood(a - 1, b)
end
end
if a <= self.Image.width and b + 1 <= self.Image.height and a >= 1 and b + 1 >= 1 then
self.rc, self.gc, self.bc, self.ac = self.Image:get(a, b + 1)
if self.rc == self.r and self.gc == self.g and self.bc == self.b and self.ac == self.a then
self:Pixelate(a, b + 1)
self:Flood(a, b + 1)
end
end
if a <= self.Image.width and b - 1 <= self.Image.height and a >= 1 and b - 1 >= 1 then
self.rc, self.gc, self.bc, self.ac = self.Image:get(a, b - 1)
if self.rc == self.r and self.gc == self.g and self.bc == self.b and self.ac == self.a then
self:Pixelate(a, b - 1)
self:Flood(a, b - 1)
end
end
end
Flood() is calling Flood() calling Flood() etc… You clearly have a huge recursive loop. The ipad has limited memory, so no doubt you get a stackoverflow! You should rewrite Flood without the recursive loop. Like multiple passes until nothing changes anymore.
Thanks @Jmv38 finally got it working after some tweaking. But why is it that the above code worked for 64 by 64 and not for 170 by 170. There must be some reason?
@Saurabh - there may be a better way to do it, by using a table to store the cells you want to visit, instead of calling your function recursively. It looks something like this…
--first find the cell you want to start from, say cell (x,y)
tbl={vec2(x,y)}
--keep looping until we're done
while #tbl>0 do
--use the first table item, which has a location of tbl[1].x, tbl[1].y
local x,y=tbl[1].x, tbl[1].y
--look at the neighbour cells, and add them to the table if they need processing
--eg suppose cell x-1,y+1 needs processing, then you say
table.insert(tbl,vec2(x-1,y+1))
--finally we remove the cell we just processed
table.remove(tbl,1)
end
So what we are doing is adding new cells at the end of the table, and examining cells at the beginning of the table. This is called a queue in computer science because we add to the end, and process the beginning, like a real queue.
The advantage is that this cannot overflow. And it’s easier to program than recursion. I hate recursion.
@Saurabh the reason why it works for 64x64 and not 128x128 is probably that: for each pixel you call the 4 neighbours (or so) which call the 4 neighbours, which etc… until you reach the border. So you create a huge number of contextual calls, but this number is not infinite, because you stop on the border. In the 64x64 you didnt reach the memory limit, and in 128x128 you did…
Wow coincidental I did the same thing. I added the ones I wanted to flood in a table and in the draw function I did a flood check for them and removed it from the table out there itself. But this has a disadvantage if there are too many values in the table like for large images. It drops the frame rate temporarily.
If you really need a good framerate, for catching user touch for instance, but have a big computation to do, you can put the computation in a coroutine and start the computation at every draw() but stop it after 10ms, then requme it at next draw() etc… The computation will be a little bit longer, but the frame rate will still feel like 60 Hz.
Thanks @Ignatz, @Jmv38 now only have to learn how to do the co routine stuff from Ignatz’ tutorials, i believe he has done something about them. Thanks!
Here is a working example
--# Main
-- test coroutine
-- Use this function to perform your initial setup
function setup()
print("trying to use coroutines")
x1=0
fps = FPS()
fps:progressBarInit("long fonction")
end
longFonc2 = coroutine.wrap(function()
local xmax=100000
local t0,dt = 0,0.003
local restart = true
local killMe = false
local x = xmax
local justFinished = false
while not killMe do
if restart then
x=0
-- print("t0")
restart = false
end
t0 = os.clock()+ dt
if x<xmax then
for i=1,xmax do
x = x + 1
if os.clock()>t0 then
fps:progressBarUpdate(x/xmax)
coroutine.yield(x,false)
t0 = os.clock()+ dt
end
end
justFinished = true
end
if justFinished then
fps:progressBarUpdate(x/xmax)
justFinished = false
end
restart,_,t0 = coroutine.yield(x,true)
end
end)
caller = coroutine.wrap(function()
while true do
while a or not v do
u,v = longFonc2(a,b,c)
a,b,c = coroutine.yield(u,v)
end
a,b,c = coroutine.yield(u,v)
end
end)
-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(40, 40, 50)
-- This sets the line thickness
strokeWidth(5)
-- Do your drawing here
local a,b
if math.floor(ElapsedTime/5)~=math.floor((ElapsedTime-DeltaTime)/5) then
a,b = caller(true,false,ElapsedTime)
print(ElapsedTime,a,b)
else a,b = caller() end
fps:draw()
-- write the x on the screen
fill(208, 208, 208, 255)
fontSize(100)
font("AmericanTypewriter-Bold")
rectMode(CENTER)
text(tostring(a),WIDTH/2,HEIGHT/2)
end
--# FPS
FPS = class()
-- this manages FPS and a progress bar
function FPS:init()
-- average fps
self.val = 60
self.t0 = ElapsedTime
-- min fps
self.min = 60
self.t1 = ElapsedTime
-- progress bar
self.frac = 0
self:progressBarInit()
end
function FPS:draw()
local vShift = 0
if self.progressBarActive then vShift = 30 end
-- update FPS value with some smoothing
local old = self.val
local frac = self.frac
-- local t1 = os.clock()
local t1 = ElapsedTime
local delta = t1 - self.t0
self.t0 = t1
local new = 1/delta or old
if new<self.min then self.min=new; self.t1=ElapsedTime+1 end
if self.t1<ElapsedTime then self.min=60 end
if new>65 then new=65 end
local ratio = new/old
if 0.5<ratio and ratio<2 then new = old*(1-frac)+ new*frac end
self.val = new
-- write the FPS on the screen
fill(208, 208, 208, 255)
fontSize(20)
font("AmericanTypewriter-Bold")
rectMode(CENTER)
text(math.floor(new).." fps (> "..math.floor(self.min)..")",70,HEIGHT-15-vShift)
-- draw progress bar
self:progressBarDraw()
end
function FPS:progressBarInit(txt)
self.frac = 0
self.txt = txt or "running"
self.img = self:progressBarCalcInfoImg(self.txt,WIDTH*0.19,30,"top")
self.progressBarActive = false
end
function FPS:progressBarUpdate(frac)
self.frac = frac
if frac>0 and frac<1 then self.progressBarActive = true
else self.progressBarActive = false end
end
-- image to show job progress
function FPS:progressBarCalcInfoImg(txt,w,h,rot)
local w0,h0
pushStyle() pushMatrix()
if rot=="left" or rot=="right"
then w0,h0 = h,w
else w0,h0 = w,h
end
local img0 = image(w0,h0)
setContext(img0)
font("AmericanTypewriter-Bold")
rectMode(CENTER)
textMode(CENTER)
strokeWidth(1)
background(255, 255, 255, 255)
fill(0, 0, 0, 255)
stroke(0, 0, 0, 255)
fontSize(20)
text(txt,w0/2,h0/2)
setContext()
local img = image(w,h)
setContext(img)
background(0, 0, 0, 255)
spriteMode(CENTER)
translate(w/2,h/2)
if rot=="left" then rotate(-90) end
if rot=="right" then rotate(90) end
sprite(img0,0,0)
setContext()
popStyle() popMatrix()
return img
end
function FPS:progressBarDraw()
if self.progressBarActive then
local img = self.img
pushStyle()
spriteMode(CORNER)
tint(128, 128, 128, 255)
sprite(img, 0, HEIGHT - img.height)
tint()
tint(255, 255, 255, 255)
clip(0,HEIGHT - img.height,self.frac*img.width,img.height)
sprite(img, 0, HEIGHT - img.height)
clip()
popStyle()
end
end
I was just working on coroutine. Why does this not work? It doesn’t go beyond 1
function setup()
cos = coroutine.create(Job)
end
function Job()
for i = 1,10000 do
print(i)
coroutine.yeild(Job)
end
end
function draw()
coroutine.resume(cos)
end
though this one doesn’t need coroutine but yet…
:)) :)) :)>-
coroutine.yield(Job).
Dam it wasn’t that. Weird. As far as I remember it doesn’t work with coroutine.yield() also. I’ll check in the morning again and tell.
Yes it was. I ran your code and got 1. Then i corrected the syntax and got 1,2,3 etc…
Reading your code again i have a doubt. But since it worked directly i didnt try further. I’ll check tomorrow too
@saurabh no, finally it works fine. What i didnt like was the coroutine.yield(Job).
You shoul really write coroutine.yield() only, the pevious line returns the adress to call the class Job at each yield, which is not what you wanted, and you dont use it anyway because you dont read the output of the yield in this example.
I didn’t understand you @Jmv38 why shouldn’t I use coroutine out here. Or were you trying to say something else? And how did coroutine.yeild work?? It should have given an error…
@Saurabh read my text again. I didnt say you should not use coroutine. I just said you shouldnt pass the ‘Job’ parameter to the yield().
Oh okay thanks misunderstood it.