Curses and recurses

ID:150881
 
Jul 11 2001, 11:58 am
There is a problem with my mapmaker code generating recursion errors on large maps or mid-sized maps with many open spaces. If I set world.loop_checks = 0 Dream Seeker produces an illegal operation when it reaches the max recursion level.

I have tried replacing the recursive proc with a non-recursive one, but in a worst case scenario, it would have to check neighboring turfs (((maxx/2)-1)*((maxy/2)-1))^2 times! This ate tons of processor time and took a very long time for larger maps but it did remove the errors.

My error message for those interested:

Maximum recursion level reached (perhaps there is an infinite loop)
To avoid this safety check, set world.loop_checks=0.
proc name: linkup (/checkmatrix/proc/linkup)
usr: Shadowdarke (/mob)
src: /checkmatrix (/checkmatrix)
call stack:
/checkmatrix (/checkmatrix): linkup(19, 13)
/checkmatrix (/checkmatrix): linkup(18, 13)
/checkmatrix (/checkmatrix): linkup(17, 13)
/checkmatrix (/checkmatrix): linkup(16, 13)
/checkmatrix (/checkmatrix): linkup(15, 13)
/checkmatrix (/checkmatrix): linkup(14, 13)
/checkmatrix (/checkmatrix): linkup(13, 13)
/checkmatrix (/checkmatrix): linkup(12, 13)
/checkmatrix (/checkmatrix): linkup(12, 14)
/checkmatrix (/checkmatrix): linkup(13, 14)
...
/checkmatrix (/checkmatrix): linkup(7, 4)
/checkmatrix (/checkmatrix): linkup(5, 4)
/checkmatrix (/checkmatrix): linkup(3, 4)
/checkmatrix (/checkmatrix): linkup(1, 4)
/checkmatrix (/checkmatrix): linkup(1, 2)
/checkmatrix (/checkmatrix): linkup(3, 2)
/checkmatrix (/checkmatrix): linkup(2, 1)
makelevel(1)
the open dugeon level (/obj/preset/open): Click("Map settings")


Here is the culprit generating my recursion errors.

linkup(X as num,Y as num)
// if(linked[X][Y]) return // already linked this location
/* tried to sleep every 100th recursion, but that didn't fix
the trouble and only slowed it down when it worked
if(recurse++ > 100)
sleep()
recurse = 0
*/
linked[X][Y] = 1
if((X > 1) && !istype(locate(X*2-1,Y*2,Z),mapwall) && !linked[X-1][Y])
linked[X-1][Y] = 1
linkup(X-1,Y)
if((X < maxX) && !istype(locate(X*2+1,Y*2,Z),mapwall) && !linked[X+1][Y])
linked[X+1][Y] = 1
linkup(X+1,Y)
if((Y > 1) && !istype(locate(X*2,Y*2-1,Z),mapwall) && !linked[X][Y-1])
linked[X][Y-1] = 1
linkup(X,Y-1)
if((Y < maxY) && !istype(locate(X*2,Y*2+1,Z),mapwall) && !linked[X][Y+1])
linked[X][Y+1]= 1
linkup(X,Y+1)


The connectivity test is started by calling linkup(1,1). Does anyone have any ideas to cut down on the recursion trouble?
Jul 11 2001, 12:44 pm
On 7/11/01 2:58 pm Shadowdarke wrote:
The connectivity test is started by calling linkup(1,1). Does anyone have any ideas to cut down on the recursion trouble?

Try spawn()ing your recursive calls to linkup()?
Jul 11 2001, 1:13 pm
In response to Air Mapster
On 7/11/01 3:44 pm Air Mapster wrote:
On 7/11/01 2:58 pm Shadowdarke wrote:
The connectivity test is started by calling linkup(1,1). Does anyone have any ideas to cut down on the recursion trouble?

Try spawn()ing your recursive calls to linkup()?

I've been trying to work that out, but I can't seem to find a good way to keep the map generation code on pause until the linkup code is done.
Jul 11 2001, 2:12 pm (Edited on Jul 14 2001, 1:06 pm)
On 7/11/01 2:58 pm Shadowdarke wrote:

Does anyone have any ideas to cut down on the recursion trouble?

Ah, the wonderful world of recursion! The problem you are encountering isn't specific to DM-- the same basic situation will occur in C, etc. It is happening because the OS has a very limited stack space and when the depth in a depth-first search gets too big this limit is reached. The easisest way to workaround this is to manage your own stack and avoid recursion altogether. Example:

turf
var/tmp/visited

proc/extendTurfs(turf/cent)
var/list/adjList = list()
for(var/x=cent.x-1;x<=cent.x+1;x+=2)
for(var/y=cent.y-1;y<=cent.y+1;y+=2)
var/turf/adj = locate(x,y,cent.z)
if(adj && !adj.visited)
adjList += adj
adj.visited = 1
return adjList

proc/fillTurfs(turf/cent)
var/list/centList = list(cent)
var/list/adjList = list()
var/turf/T

cent.visited = 1
while(centList.len)
for(T in centList)
// do your routine on T here
adjList.Cut() // clear it
for(T in centList)
adjList += extendTurfs(T)
centList.Cut() // clear it
centList += adjList

I didn't test this or even see if it compiled, but I think that basic system should solve your problem.

// edit -- oops! Fixed a bug found by ShadowDarke, just in // case anyone ever looks at this snippet in the future
Jul 11 2001, 2:19 pm
In response to Tom
On 7/11/01 5:12 pm Tom wrote:
On 7/11/01 2:58 pm Shadowdarke wrote:

Does anyone have any ideas to cut down on the recursion trouble?

Ah, the wonderful world of recursion! The problem you are encountering isn't specific to DM-- the same basic situation will occur in C, etc. It is happening because the OS has a very limited stack space and when the depth in a depth-first search gets too big this limit is reached. The easisest way to workaround this is to manage your own stack and avoid recursion altogether.
problem.


I had the same problem in DragonSnot...after 8 months of the game being available in various forms, Leftley was the first person to create such diabolical trenches that the recursive stack went over 200 and crashed out.

Fortunately, it's usually very easy to rewrite to avoid recursion.
Jul 11 2001, 2:21 pm
In response to Deadron
I had the same problem in DragonSnot...after 8 months of the game being available in various forms, Leftley was the first person to create such diabolical trenches that the recursive stack went over 200 and crashed out.

ph34r my m4d fr33 t1m3.

Jul 11 2001, 2:46 pm
In response to Leftley
On 7/11/01 5:21 pm Leftley wrote:
I had the same problem in DragonSnot...after 8 months of the game being available in various forms, Leftley was the first person to create such diabolical trenches that the recursive stack went over 200 and crashed out.

ph34r my m4d fr33 t1m3.
Hey, that looks like that secret code I saw in a class room once-upon-a-time...
Jul 13 2001, 4:12 pm
In response to Tom
On 7/11/01 5:12 pm Tom wrote:
I didn't test this or even see if it compiled, but I think that basic system should solve your problem.

Thanks, Tom. I finally got to work on some code today and this snippet worked out nicely. :)
Jul 13 2001, 4:37 pm
In response to Shadowdarke
On 7/13/01 7:12 pm Shadowdarke wrote:
On 7/11/01 5:12 pm Tom wrote:
I didn't test this or even see if it compiled, but I think that basic system should solve your problem.

Thanks, Tom. I finally got to work on some code today and this snippet worked out nicely. :)

I spoke too soon. :(
Now it thinks it's an infinate loop on larger maps.
I'm going to work with spawning it after I get some sleep...

Infinite loop suspected.
To avoid this safety check, set world.loop_checks=0
proc name: fillTurfs (/checkmatrix/proc/fillTurfs)
source file: mapmaker.dm,244
usr: Shadowdarke (/mob)
src: /checkmatrix (/checkmatrix)
call stack:
/checkmatrix (/checkmatrix): fillTurfs(the type3 (1,1,0) (/turf/floor/type3))
makelevel(1)
Shadowdarke (/mob): generate()
the generate map (/obj/generate_map): Click("Map settings")
Jul 13 2001, 5:24 pm
In response to Shadowdarke
On 7/13/01 7:37 pm Shadowdarke wrote:

Thanks, Tom. I finally got to work on some code today and this snippet worked out nicely. :)

I spoke too soon. :(
Now it thinks it's an infinate loop on larger maps.
I'm going to work with spawning it after I get some sleep...

If you turn off world.loop_checks does it work? It's probably just in that while() loop for a long time since you could conceivably be mapping through every turf in your game. Why don't you (temporarily) turn off loop_checks and put a counter in to see how many iterations are occurring.