generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: How do I stop my recursive functions from causing a stack overflow?

Previous Thread :: Next Thread 
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
13 Nov 2011 07:40 PM
I am forced to use a recursive function to check continutity in my randomly generated dungeon, but it likes to stack overflow when I make the dungeon too big...

~Monica
Report Abuse
aboy5643a is not online. aboy5643a
Joined: 20 Nov 2010
Total Posts: 2785
13 Nov 2011 07:46 PM
You use a controlled loop?? One that stops after a certain point.
Report Abuse
pwnedu46 is not online. pwnedu46
Joined: 23 May 2009
Total Posts: 7534
13 Nov 2011 07:51 PM
Use a tail call because they use no stack space.

function tailCallRecursion()
-- code
return tailCallRecursion()
end
Report Abuse
ENET is not online. ENET
Joined: 01 Jan 2010
Total Posts: 4820
13 Nov 2011 08:04 PM
Increment a value every time and if it hits 255 or so then stop cause thats the max stack size...
Report Abuse
aboy5643a is not online. aboy5643a
Joined: 20 Nov 2010
Total Posts: 2785
13 Nov 2011 08:08 PM
Y so 8 bit??
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
13 Nov 2011 08:10 PM
Prolly so they only have to tack a single byte into the memory to have the depth of each function call?

~Monica
Report Abuse
NecroBumpist is not online. NecroBumpist
Joined: 12 Sep 2010
Total Posts: 4198
13 Nov 2011 08:13 PM
Or you could just use a tail-call like previously suggested, which won't cause a stack overflow.
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
13 Nov 2011 08:14 PM
Hmm

~Monica
Report Abuse
eyeontheprizeREBOOT is not online. eyeontheprizeREBOOT
Joined: 30 Jan 2011
Total Posts: 1555
13 Nov 2011 08:43 PM
Use tail calls. No new stack frames are created.
Report Abuse
Varp is not online. Varp
Joined: 18 Nov 2009
Total Posts: 5333
13 Nov 2011 08:57 PM
You can unroll the recursive function into an iterative function. If you posted the function or one analogous to it, I could be more help than that.
Report Abuse
stravant is not online. stravant
Forum Moderator
Joined: 22 Oct 2007
Total Posts: 2893
13 Nov 2011 09:23 PM
Like Varp said, unroll it.

Lua has a pretty large stack available.. if you're managing to get a stack overflow then you probably shouldn't be using recursion to solve whatever your problem is, or at the very least, you should be using some hybrid solution.
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 06:43 AM
Are you sure youre not just making the function go back to spots it has already checked?
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
14 Nov 2011 08:21 AM
@Radio
I check to make sure I haven't checked that spot before.
local function RecurGrab(x,y)
local te = getCell(x,y)
if(te == nil or te == 0 or te == 3 or te == 1)then setCell2(x,y,0); return; end
setCell2(x,y,te);
for x1=-1,1,2 do
if(getCell2(x+x1,y) == nil)then
if(math.random(1,128) == 2)then wait(); end
RecurGrab(x+x1,y);
end
end
for y1=-1,1,2 do
if(getCell2(x,y+y1) == nil)then
if(math.random(1,128) == 2)then wait(); end
RecurGrab(x,y+y1);
end
end
end

~Monica
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 08:38 AM
Its not working because it looks too complex.


Fix it pl0x.
Report Abuse
stravant is not online. stravant
Forum Moderator
Joined: 22 Oct 2007
Total Posts: 2893
14 Nov 2011 08:43 AM
Why does that need to be recursive..?

Can't you just do:
for x = 1, width do
for y = 1, height do
...
end
end
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
14 Nov 2011 08:53 AM
Because I'm checking for continuity in the dungeon, and the only way I know to do that, is to start at one point, then check adjacent squares until I hit walls.

~Monica
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 08:53 AM
local te = getCell(x,y)
if(te == nil or te == 0 or te == 3 or te == 1)then setCell2(x,y,0); return; end
setCell2(x,y,te);

if the cell doesnt go thru that if statement it will never change and cause infinitie loopz
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
14 Nov 2011 08:55 AM
@Radio
Nah, cause 0, 3, or 1 are the walls, so there's no need to check adjacent squares on a wall. And the nil check is to keep it within the confines of the map.

~Monica
Report Abuse
TheMyrco is not online. TheMyrco
Joined: 13 Aug 2011
Total Posts: 15105
14 Nov 2011 09:07 AM
    local callTimes = 0
    
    function blah()
        callTimes = callTimes + 1
        if callTimes < 20000 then
            blah()
        elseif callTimes ​>= 20000 then
            return
        else
            return
        end
    end
    
    blah()
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 09:11 AM
nvm im not sure how that works...

I was assuming that the line is to stop it from recursing more than once on the same cell, but apparently you got some other checks in there and i have no idea what the getcell functions do >_>
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
14 Nov 2011 09:20 AM
getCell returns the type of cell for that x,y position. setCell sets it.
I'm switching the map from the first table to the second table, but only transfering continuious parts.

~Monica
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 09:38 AM
so when you have been at a cell, where do you mark it as "visited"?
Report Abuse
oxcool1 is not online. oxcool1
Joined: 05 Nov 2009
Total Posts: 15444
14 Nov 2011 09:42 AM
[ Content Deleted ]
Report Abuse
mustyoshi is not online. mustyoshi
Top 50 Poster
Joined: 27 Dec 2007
Total Posts: 41651
14 Nov 2011 11:55 AM
I call setCell2() and that sets the second map as having a value at that cell, then when I call getCell2 if it's not nil, I know I already checked that cell.

~Monica
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
14 Nov 2011 12:03 PM
local function RecurGrab(x,y)
if getCell2(x,y) == nil then
if math.random(1,128) == 2 then wait() end
local te = getCell(x,y)
if te == nil or te == 0 or te == 3 or te == 1 then setCell2(x,y,0) return end
setCell2(x,y,te)
RecurGrab(x+1,y)
RecurGrab(x-1,y)
RecurGrab(x,y+1)
RecurGrab(x,y-1)
end
end


Nao its prettier.

Idk if it works anymore.

Or if it actually works now.
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image