 |
|
||
| Date: | 1993-09-07 | ||
| From: | Paul | ||
| Subject: | Alex Status |
I now have a compilable but not linkable C++ continent generator. As it appears that just getting the thing to link may take some time, I'm abandoning Alexander for the next day or so in order to get Archipelago out. :-{. However, here's a small Alex puzzle for you:
Remember our old friend the SparkList? I need to know how big that can get. Here's a quick SparkList refresher:
SparkList starts out with some fixed number of entries - say 20. These are random points on the world map, and these initial entries are all LAND.
We pick one of these at random, remove it from the SparkList, and replace it with *up to* 8 more sparks - its 8 nearest neighbors, if they haven't yet been assigned (these new sparks may become LAND or SEA, depending on a simple algorithm irrelevant to this discussion), and if they aren't "out of bounds".
This process iterates until the SparkList is empty, signalling that all points on the map have been assigned.
So how big does the SparkList get? It turns out that when I wrote the initial code, years ago, I just sized it to maxRows * maxCols: 100 * 80 = 8000. This was stupid then; it's stupid and maybe "impossible" now. Why? Assume we smooth borders at 7x7 resolution. Assume also that 10% of the world is border. This is a wild guess, but it will have to do till someone does some calculations. Then the new SparkList size will have to be 8000/10 * 49 = ~40,000. Yow! We can't afford to be so sloppy any more.
I spent 5 minutes this afternoon thinking about the problem, and came up with a size estimate of ~1/15 the above. Needless to say, this is a vast improvement, if it's correct.
What do you think? Put your "Chief Algorithmist" cap on, and tell me how large I need to size the SparkList.
Mr. Duk