Hi everyone,
I'm working on a little world map generator. I've got things working fairly well, but like many terrain generators it tends to create maps with lots of inland seas, cut off from the ocean. I want to fill these in so my maps are more like the real world (where genuine inland seas are very rare).
To do this I've adapted ianm's excellent
floodfill functions. I changed them so that instead of filling an area, they count its size. The map itself is a 2D array.
The program basically looks over the array until it finds an area of sea that is larger than a certain minimum size. It calls that the ocean and marks it on another array. (In fact it does this on two arrays, because I had difficulty getting the area checking functions to wrap from east to west, so I came up with a terrible hack whereby the area checker does its work once then shifts the whole map 50% to the right and does it again, but that's not important right now.) Then it simply goes over the map array and any sea areas that aren't marked on the ocean array are replaced by land.
Here's my problem: the functions work fine and very quickly, but they have a nasty habit of crashing the app (about one time in three for me). I'm not certain why but I think it's because they work recursively, and sometimes - perhaps when dealing with especially crinkly coastlines - they overflow the stack. So I want to rewrite these functions to work iteratively instead, with a custom queue.
Unfortunately doing this seems to be beyond my powers. My rewritten functions look flawless to me, but the program just hangs in an endless loop.
Can anyone help? I attach a stripped down version of the program here. Rather than generating a map it loads one in. You can press space to see the recursive inland-sea-filling functions do their thing. (As it stands they just fill in the inland seas with flat plains just above sea level, which look a bit rubbish, but I'll do something a bit fancier once I've got the basic method to work more reliably.) The comments in the code show where these functions are, and I have included my attempts at iterative functions, remmed out. Rem out the recursive functions and unrem the iterative ones and run the program again and you'll see it fail to work.
What am I doing wrong? Can anyone help?
Also in case anyone can work this out just by looking, here are the (working correctly) recursive functions, based on ianm's floodfill:
function areacheck(map ref as integer[][],checked ref as integer [][],width,height,x,y,mode)
for i=height to 0 step -1
__FilledSpansCount[i]=0
next i
if x >= 0 and x <= width
if y >= 0 and y <= height
checked[x,y]=1
origcol=map[x,y]
if mode=-1 then origcol=-1
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
endfunction total
` origcol=-1 means it's looking for sea.
function checkloop(map ref as integer [][],checked ref as integer [][],width,height,x,y,origcol,total)
for lt=x-1 to 0 step -1
if origcol=-1
if map[lt,y]>sealevel
checked[lt,y]=1
exit
endif
else
if map[lt,y] <> origcol then exit
endif
next lt
lt=lt+1
for rt=x+1 to width
if origcol=-1
if map[rt,y]>sealevel
checked[rt,y]=1
exit
endif
else
if map[rt,y] <> origcol then exit
endif
next rt
` count this line
for i=lt to rt
if i=>0 and i<=width
total=total+1
checked[i,y]=1
endif
next i
` and remember it
__AddFillSpan(y,lt-1,rt+1)
` Count upwards
if y > 0
y=y-1
x=lt
while x < rt
SpanSize=__CheckFillSpan(x,y)
if SpanSize = 0
if origcol=-1
if map[x,y]<=sealevel
total=checkloop(map,checked,width,height,x,y,origcol,total)
if x=0
if map[width,y]<=sealevel and checked[width,y]<>1 ` If this sea wraps round to the other side
total=checkloop(map,checked,width,height,width,y,origcol,total)
endif
endif
endif
else
if map[x,y] = origcol
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
x=x+1
else
x=x+SpanSize
endif
endwhile
y=y+1
endif
` Count downwards
if y < height
y=y+1
x=lt
while x < rt
SpanSize=__CheckFillSpan(x,y)
if SpanSize = 0
if origcol=-1
if map[x,y]<=sealevel
total=checkloop(map,checked,width,height,x,y,origcol,total)
if x=0
if map[width,y]<=sealevel and checked[width,y]<>1 ` If this sea wraps round to the other side
total=checkloop(map,checked,width,height,width,y,origcol,total)
endif
endif
endif
else
if map[x,y] = origcol
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
x=x+1
else
x=x+SpanSize
endif
endwhile
endif
endfunction total
And my failed attempt to translate this into an iterative version:
global qsize=10000
global dim q[qsize,1]
function areacheck(map ref as integer[][],checked ref as integer [][],width,height,x,y,mode)
for i=0 to qsize ` First clear the queue array.
for j=0 to 1
q[i,j]=-1
next j
next i
if x>=0 and x<=width ` Put the first node in the first place in the queue.
if y>=0 and y<= height
q[0,0]=x
q[0,1]=y
endif
endif
for i=height to 0 step -1
__FilledSpansCount[i]=0
next i
keepgoing=1
repeat ` Now we're going to keep on doing this until we run out of nodes to check.
if q[0,0]=-1 ` If the next in the queue is empty
keepgoing=0
endif
x=q[0,0] ` Take x and y coordinates from the next item in the queue.
y=q[0,1]
shuntqueue() ` Get rid of that item in the queue and move all the waiting items up one.
if x >= 0 and x <= width
if y >= 0 and y <= height
checked[x,y]=1
origcol=map[x,y]
if mode=-1 then origcol=-1
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
until keepgoing=0
endfunction total
` This function removes the current item in the queue and moves all the later items up one.
function shuntqueue()
for i=0 to qsize-1
if q[i,0]=-1 ` If we've reached the end of waiting items
exitfunction
endif
q[i,0]=q[i+1,0]
q[i,1]=q[i+1,1]
next i
endfunction
` This function adds a new node to be checked at the end of the queue.
function addtoqueue(x,y)
found=-1
for i=0 to qsize
if q[i,0]=x and q[i,1]=y ` If this node is already in the queue
exitfunction
endif
if q[i,0]=-1
found=i
endif
if found<>-1 then exit
next i
if found=-1 ` If the queue is full!
exitfunction
endif
q[found,0]=x
q[found,1]=y
endfunction
` origcol=-1 means it's looking for sea.
function checkloop(map ref as integer [][],checked ref as integer [][],width,height,x,y,origcol,total)
for lt=x-1 to 0 step -1
if origcol=-1
if map[lt,y]>sealevel
checked[lt,y]=1
exit
endif
else
if map[lt,y] <> origcol then exit
endif
next lt
lt=lt+1
for rt=x+1 to width
if origcol=-1
if map[rt,y]>sealevel
checked[rt,y]=1
exit
endif
else
if map[rt,y] <> origcol then exit
endif
next rt
` count this line
for i=lt to rt
if i=>0 and i<=width
total=total+1
checked[i,y]=1
endif
next i
` and remember it
__AddFillSpan(y,lt-1,rt+1)
` Count upwards
if y > 0
y=y-1
x=lt
while x < rt
SpanSize=__CheckFillSpan(x,y)
if SpanSize = 0
if origcol=-1
if map[x,y]<=sealevel
`total=checkloop(map,checked,width,height,x,y,origcol,total)
addtoqueue(x,y)
if x=0
if map[width,y]<=sealevel and checked[width,y]<>1 ` If this sea wraps round to the other side
`total=checkloop(map,checked,width,height,width,y,origcol,total)
addtoqueue(width,y)
endif
endif
endif
else
if map[x,y] = origcol
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
x=x+1
else
x=x+SpanSize
endif
endwhile
y=y+1
endif
` Count downwards
if y < height
y=y+1
x=lt
while x < rt
SpanSize=__CheckFillSpan(x,y)
if SpanSize = 0
if origcol=-1
if map[x,y]<=sealevel
`total=checkloop(map,checked,width,height,x,y,origcol,total)
addtoqueue(x,y)
if x=0
if map[width,y]<=sealevel and checked[width,y]<>1 ` If this sea wraps round to the other side
`total=checkloop(map,checked,width,height,width,y,origcol,total)
addtoqueue(width,y)
endif
endif
endif
else
if map[x,y] = origcol
total=checkloop(map,checked,width,height,x,y,origcol,total)
endif
endif
x=x+1
else
x=x+SpanSize
endif
endwhile
endif
endfunction total
