Date:	1993-11-02
		From:	John
		Subject:	Smoothing Quandry

I gather you are out of town for two weeks, but are you incomunicado? If you receive this message via internet please reply so that I know you are receiving.

I have been grinding away on the smoothing algorithm and am beginning to see that a fair amount of experimentation will be required before we can work out all the details. I now have a full scale (50x70) map with a script that draws the shoreline area in gray and the initial set of land sparks (the inside of that shoreline area) in red. There are still a few dots out of place, but I can now provide our first solid estimates of the size of the sparklist.

My initial assumption has been that we would use the inner edge of the shoreline area as our starting set of land sparks. But this approach may not be workable. Here's why.

The initial size of the sparklist seems to be about 3.78 sparks per square unit. This is about 13000 sparks in my 50x70 map, or about 37800 sparks in the proposed 100x100 map. The total shoreline area is currently 6 times as large. If the sparklist rises and falls at the micro level in the same way it does at the macro level (which is not at all certain), I'm estimating that the sparklist would peak at about 6.6 sparks per square unit (66000 sparks in the 100x100 map).

At the macro level, the sparklist starts out at essentially zero and peaks at about .29 sparks per square unit. Thus the micro sparklist STARTS OUT at 13 times as large as the maximum macro sparklist and may rise to something like 23 times as large.

I see two problems here. The first is that the sparklist is large to the point of being unwieldy (although not as large as I had originally feared). The second is that the huge initial land-to-sea ratio may prevent sea pixels from forming in the shoreline area. At the macro level, with 20 initial land sparks, the land/sea ratio rises to about 50/50 within the first 500 sparks. Under my current smoothing approach, by the time the sparklist grows from 38000 to 50000, I would expect only about 2000 (or 4%) sea sparks. By the time the sea sparks start to achieve critical mass, all the shoreline area would already be landfill. That, at least, is my guess.

What can we do? We could change the chance of land sparks begetting sea sparks from 1 in 6 to 1 in 2, but that would probably not be enough. We could expand the shoreline pixel area and/or make it unsymetrical to give the sea sparks more "breathing room," but the shoreline area is already too big and needs to fluctuate equally in AND out.

Some better ideas. We could decrease the initial number of sparks by designating only every other pixel along the inside of the shoreline as a land spark (or only in the corners of shoreline coordinates or at a random point along each edge). Or we could balance the set of initial land sparks with some yet-to-be-determined number of sea sparks. OR some combination of the above.

But we can't scatter land sparks totally at random as we do on the macro level because the shoreline of each continent is disconnected from the rest of the shoreline space. The growth cannot spread from one continent to the next. And if the sea expansion ever completely overtakes land expansion for any significant stretch of coastline (or vice versa), the original jagged corners would be revealed.

Clearly, more research by the chief algorithmist is called for. But it would help if the chief programmer could clarify the limitations he will face during implementation. Is there a limit on how big the sparklist can get? Or on how big the shoreline area can get? These are not black and white questions, since clever programming can overcome any limit. But I imagine there are certain plateaus beyond which further size increases become exponentially more burdensome. For example, does it become difficult to handle more than 32767 sparks?

And ANYTHING you can tell me about your implementation could help. For example, how do you plan on representing the discontinuous shoreline space? Are you likely to deal with pixels using a single 1800x1400 coordinate system, or with a combination of macro coordinates (100x100) and micro coordinates (18x14)? How will the detailed map be stored? Can the algorithm that finds shoreline pixels mark some pixels more than once? If the pixels are stored in a big array this won't matter, but if they are stored as a list of coordinates it would.

Any conclusions you've drawn from your experience to date would be appreciated. Just as necessity is the mother of invention, so implementation contraints often lead to algorithmic inspirations.

Yours in haste,

Epicurious J.