As a holiday treat, in this installment of Mr. Wizard we get to see a movie. It's a very short movie, no actors, not much of a plot, but it does feature scenery that assembles itself!
As all of you should know by now, Paul and I are working on our very own strategic war game. The first step in this process is to find a way to create randomly generated planets, complete with continents, islands, lakes, rivers, fiords, peninsulas, etc. We want to create maps that are interesting to play on, easy to make, and "natural looking". This turns out to be rather an interesting challenge, and since I foolishy promised Paul I'd have some kind of algorithm in place by Christmas, Mr. Wizard found himself trying to grow continents on Christmas Eve. The ContinentGrower stack is a animation that displays one of his many experiments.
There are all sorts of radicaly different ways to make a continent. One approach is to randomly spatter ovals of different sizes all over the map and then tidy up the edges so that they look more "coast-like". In trying this approach I discovered that vertical globs (made of ovals which are taller than they are wide) look much more natural than horizontal globs. On our planet we have lots of globs like Florida and India that stick down, but not many globs that stick out. Why is that, do you think?
Another approach would be to start with some kind of proto-continent and then split it up along random fault lines and let the pieces drift for awhile. This idea struck me as easy to visualize but difficult to implement, so I let it go.
My favorite approach so far, the one depicted in our movie, is extremely simple. I start with 20 individual dots of land (I call them sparks) scattered at random. I put those 20 locations on the "spark list" and I then begin pulling items off the list at random and applying the following simple rule:
If the spark I've chosen is a land spark, I look at the eight cells adjacent to the spark's location. I mark each unassigned cell as either a land or a sea spark and add it to the spark list. To decide between land or sea I simply role the dice, with about an 80% chance of choosing land. But if the spark I've chosen is a sea spark, then ALL unassigned neighboring positions become sea sparks.
At first there is nothing but land. Every now and then a bit of water appears. But since water, in effect, grows faster than land, eventually each glob of land becomes surrounded by ocean and the ocean spreads until it fills 70% or so of the planet. The continents and islands produced are fairly interesting, albeit a bit too "raggedy". They have swamps, lakes, rivers, and convoluted coastlines. The algorithm still needs refinement, but I think it is quite promising.
And now it's show time! Simply press the ContinentGrower button, and you will see the initial scattering of land sparks. Push the "Show Movie" button to see what happens when the simple rule is applied over and over (you can pause at any point by holding down on the mouse). You can also step from frame to frame by using the arrow buttons; tap once to advance, hold down to continue the animation.
HOW IT WORKS
There are various ways to achieve animation in HyperCard; this is perhaps the simplest. There are fifty cards in the stack and the "Show Movie" button simply flips through them. A new frame was created after every 100 sparks were plotted, so the rate of growth is constant.
Several graphs are shown at the bottom of the screen. The first shows the number of seconds elapsed since the growth process began. As the map neared completion the program slowed down; it took about three hours to finish. HyperCard is clever, but it's not very fast at this sort of thing; I expect AT LEAST a 100-fold speed improvement when Paul rewrites this algorithm in 'C' (another programming language).
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.
The third graph shows what percentage of assigned locations on the current frame is occupied by sea. This value seems to approach about 70% even when some of the initial variables are changed, but I haven't done enough experiments yet to nail down the relationship between the starting pattern and the final result.
If you'd like to see the program that generated this brave new world, just push the Algorithm button on the first card. This is the actual button that did all the work, with a line added at the front so that all it does now is display a copy of its own script. You HyperTalk students should enjoy browsing this
*fairly* simple script.
If anyone expresses an interest, I will release a version of this stack that lets you grow your own. Please feel free to contribute any insights you may have on the best way to grow a continent!