mustyoshi
|
  |
 |
| 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
|
  |
| 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
|
  |
| 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
|
  |
| 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
|
  |
| Joined: 20 Nov 2010 |
| Total Posts: 2785 |
|
| |
|
mustyoshi
|
  |
 |
| 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 |
|
|
|
| 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
|
  |
 |
| Joined: 27 Dec 2007 |
| Total Posts: 41651 |
|
| |
|
|
| 13 Nov 2011 08:43 PM |
| Use tail calls. No new stack frames are created. |
|
|
| Report Abuse |
|
|
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
|
  |
 |
| 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 |
|
|
|
| 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
|
  |
 |
| 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 |
|
|
|
| 14 Nov 2011 08:38 AM |
Its not working because it looks too complex.
Fix it pl0x. |
|
|
| Report Abuse |
|
|
stravant
|
  |
 |
| 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
|
  |
 |
| 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 |
|
|
|
| 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
|
  |
 |
| 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
|
  |
| 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 |
|
|
|
| 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
|
  |
 |
| 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 |
|
|
|
| 14 Nov 2011 09:38 AM |
| so when you have been at a cell, where do you mark it as "visited"? |
|
|
| Report Abuse |
|
|
oxcool1
|
  |
| Joined: 05 Nov 2009 |
| Total Posts: 15444 |
|
| |
|
mustyoshi
|
  |
 |
| 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 |
|
|
|
| 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 |
|
|