 |
|
||
| Date: | 1993-09-08 | ||
| From: | Paul | ||
| Subject: | Re: Alex Status |
I had totally forgotten that SparkList size had been a topic of conversation oh-so-many-years-ago. You should certainly add "Chief Archivist" to your list of titles. And it's interesting that your first example totally invalidated my initial guess at maximum size.
My plan *was* to generate the world in one pass, then smooth it in a second. However, I am still most receptive to cleverer suggestions. As such, your one-pass procedure certainly deserves consideration.
Let's see how this would work (this is my "refinement" of your suggestion): when I assign a new cell, I check its eight nearest neighbors. Throw out cells unassigned; of those remaining, also throw out all which from this micro view appear to not be border cells. If there are any cells left, somehow smooth this subset at a higer resolution. To allow a smooth transition to more distant cells, maybe leave the outside edges of this high-res neighborhood alone. Maybe a "picture" would help:
S L L 1 2 3
S L L <--4 5 6
S S U 7 8 9
Cell 5 has just been assigned as land. Ignore cell 9; it's currently unassigned. Ignore cell 3; from this perspective, it's not a border cell (how about cell 6? I *think* we want to keep him. I *think* my answer would be the same even if cell 9 was also land). This leaves us with
S L
S L L
S S
Expand the resolution on this mini-world; at worst, this would be 21 x 21 (or 42 x 42 if smoothing at lower resolution appears unsatisfactory). This is quite manageable. Further, we would want to seed this map something like this at higher resolution:
u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | u u u | u u u | u u u | u u u | u u u | u u u | u u u | u u u | --------------+---------------+---------------+ u u u | L L L | u u u u u u u | u u u | L L L | u u u u u u u | u u u | L L L | u u u u u u u | u u u | L L L | u u u | u u u | L L L | u u u | u u u | L L L | u u u | u u u | L L L | u u u | --------------+---------------+---------------+ u u u | | u u u | | u u u | | u u u | | u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | u u u u u u u | --------------+---------------+where "u" means unchanged from current setting, if any, "L" means force to land, and blank means unassigned (to be generated). But having taken the time to draw this, I have *no* idea of its goodness. If we stick to this "leave the outer three pixels alone" philosophy we can ignore the outer two pixels in the calculations. This gives us a probably very reasonable 17x17 partially-filled-in grid to smooth. But each cell - each LARGE cell - could be resmoothed eight times in this scheme. I dunno. It should be fun and instructive to try something like this, anyway.
You want a plain English version of the current algorithm? I thought I supplied that last time. Well, I'll try again:
Set every cell in the world map to UNASSIGNED
Empty the SparkList
Randomly assign some points as land
Mark them as LAND on the world map
Add their map coordinates to the SparkList
Repeat until the SparkList is empty:
Pick a random element from the SparkList
Check its eight adjacent neighbors on the world map in turn
(there will be fewer than eight neighbors if we're on a map edge)
If UNASSIGNED:
Mark the neighbor as LAND or SEA on the world map
Add the neighbor's map coordinates to the SparkList
Remove the old spark from the SparkList
That's it!
I "finished" Archipelago earlier this evening; it'll go out in tomorrow's mail.
My C++ world generator now links. It also crashes immediately, and hard. I'll be in Idaho Falls tomorrow and Thursday, so it will be Friday at best before I can even look at it. Unfortunately, the following two weeks look to be travel weeks as well, but fear not. I WILL make the time to continue to work on this!
Duk