Date:	1997-02-20
		From:	Paul
		Subject:	RE: Alexander

You'll recall that in prior versions of the algorithm, we start with an array of sparklist locations and remove elements randomly as the world is generated, replacing them in the array with any of their nearest neighbors that get assigned during that pass. The problem with this scheme is that we need to pre-allocate a large array of worst-case size.

So one of us (me?) proposed switching to a stack. The idea is that you always pull the top element off the stack, then push on any of the six nearest neighbors that get assigned that pass. If the stack can grow dynamically, this nicely avoids wasted space. But it occurred to me this morning that it probably doesn't work. Chances are the first spark will grow for a while, then at least most of the rest of the world will fill up with sea before the stack empties enough to get to even the second spark. If you start with ten sparks, I bet six or eight will wind up totally surrounded by land or water before they get a crack at growing. This is not a good thing.

What's the solution? I'm betting that a queue will solve the problem.

Imagine we start with ten sparks. The first one will be pulled off the queue, and its eight nearest neighbors will be assigned and pushed onto the end of the queue. Then the second spark will get its turn to grow, and its children will be pushed onto the end of the queue. Then the third spark, and so on, until all ten sparks have had a crack at growing. At this point, you're back to servicing whatever the first spark left behind, and so on again, until the world is entirely mapped out.

My biggest concern is that this may generate too-uniform growth; maybe the random selection of the array-based algorithm is important to the final look of the world. To help combat that, I plan to randomly vary initial spark sizes from 1 cell to some requested upper limit. But I guess we just won't know how well this algorithm will work until we generate a bunch of worlds.

On this last subject - if I send you a file of 1's and 0's to represent land and water, how difficult is it for you to turn this into a blue and green world map - a pict or gif or whatever? I'm no sure if there will be an easy way for me to do the display myself from C++, so telling if my program is doing the right thing may be problematical.

Paul