Date:	1993-09-07
		From:	John
		Subject:	Refining the Algorithm

A VERY interesting little puzzle. I shall, as you suggest, put on my "Chief Algorithmist" cap and see if I can come up with a better alogorithm, or at least a clearer understanding of the one we have.

Meantime, I did a quick bit of research and found the following quotation from the Mr. Wizard card which launched the continent grower way back in volume 11:

"The second graph shows the size of the 'Spark List'. Under the current arrangement this value rises and then falls. After awhile many sparks on the list don't need to be examined, because all their neighbors have already been assigned. This is one of the reasons the algorithm slows down; with a little more thought I may be able to reduce the wasted computations."

With some difficulty I managed to unearth my copy of the Continent Grower stack and examined this spark usage graph. This version generated a map of 53 by 93 pixels for a total area of just under 5000 square pixels. The sparkcount slowly rose to a maximum value of 1456 (about 30%) and then swiftly dropped back down to zero. I seem to recall that all the maps I generated showed the same basic pattern.

Suppose, then, that we allocate only 3000 pixels for your 80 by 100 world - that is 37.5% which, I admit, doesn't give us much of a safety margin but with the law of large numbers on our side might actually be quite safe. Now then, you calculated that with 10% of the world as beachfront property (and your guess is as good as mine) and with a resolution of 7 by 7, the sparks required for smoothing would be 8000/10*49, or about 40000. If my guesswork is correct, you should be able to lower that to 15000.

Still too high? Here's a question for you, then. Do you need to allocate all the smoothing sparks at once? Or could you first smooth the western hemisphere, and then clear things out and smooth the eastern hemisphere? For that matter could you divide the world into a hundred degrees of longitude and smooth 1% of the world at a time, thereby achieving a 100-fold reduction?

Or would that spoil your nifty all-in-one recursive procedure? Was your plan to generate the macro world in one pass, scan for coastline, and then smooth in a second pass? Maybe if the algorithm could do the micro-assignments AS it was doing the macro-assignments this problem would go away.

The off-the-top-of-my-head scheme works like this. Every time you assign a macro-pixel as land or sea, check to see if this new pixel is adjacent to a previously-assigned pixel of the opposite type. If so, we now have a tiny piece of coastline. Set up a 7 by 7 microworld straddling the two macro-sparks. Fill in the details AND MOVE ON.

That's it. The result would be a ONE PASS procedure. And since it only handles one 7 by 7 microworld at a time, you don't need to allocate huge volumes of RAM for the sparklist.

The problem with this approach is that tackling the shoreline one bit at a time may produce lots of chunky little edges. I think this could be avoided by considering what parts of the nearby micro-shoreline had already been assigned when setting up each 7 by 7 microworld. What do you think?

But I've blathered along too much as it is. As I said, I will keep thinking about this. It would be helpful, though, if you could provide me with a plain English version of the current algorithm as you define it. That would get me up to speed and give us a common point of reference.

I will await further word with mounting anticipation. And I'll expect to see your pelago packet by the end of the week.

Yours in haste,

Epicurious J.