Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Trying to turn recursive functions iterative... help!

Author
Message
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 26th Oct 2017 21:22 Edited at: 26th Oct 2017 21:25
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:



And my failed attempt to translate this into an iterative version:

Attachments

Login to view attachments
Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 27th Oct 2017 03:36

if you use a parallel array to store the scanned status, then you don't really need recursion or a stack, although it's a bit more memory over head (depends upon the area).

Dark Basic Source Codes - Snippets scroll down to Shape Drawing & Effects and the link is titled 2D Fast Array based Flood Filler (updated Nov 2003).. It was originally written for DB classic, but I guess it might have updated to work with DBpro at some future point.


PlayBASIC To HTML5/WEB - Convert PlayBASIC To Machine Code
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 27th Oct 2017 14:38
Thank you! I did see that routine before while researching this, but its download only contains DBC files (.DBA), which I'm guessing you can't read without having DBC, which I don't, unfortunately... I thought DBC was freely available these days but can't seem to find anywhere to get it from!

Ideally I'd like to work out what went wrong with my attempt at iteration, if only for my own growth from a bad programmer to a slightly less bad one, but I'll ask on the DBC forums if anyone can post that flood filler routine in an accessible form.
Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 27th Oct 2017 14:46
,DBA files are just plain text.



PlayBASIC To HTML5/WEB - Convert PlayBASIC To Machine Code
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 27th Oct 2017 19:58
Well I'm an idiot. Thank you - I'll get studying them.
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 9th Nov 2017 13:58
Thank you again for your help on this. Your DBC code was a bit beyond me to translate - so many differences compared to AppGameKit now - but the basic idea of using a 2D array to store the locations of nodes to be checked, thereby avoiding both recursion and the need for a queue or stack, is basically genius so I created my own routine based on that idea. It works really well and is totally stable.

The only problem of course is that it’s slower, because the routine has to keep searching through the array to find the next node to check, rather than going straight to it as a recursive function does. I’ve used a few tricks to speed that process along here and there but overall the routine is on the slow side. But that’s a price worth paying for stability.

Login to post a reply

Server time is: 2024-03-29 15:46:07
Your offset time is: 2024-03-29 15:46:07