 |
|
||
| Date: | 1997-03-17 | ||
| From: | Paul | ||
| Subject: | RE: Queue-based Alexander Algorithm |
The GIF came through fine, and reinforced my belief that this algorithm is just not doing the job. Actually, after sending you the raw file I found one bug in the world generation algorithm, but it doesn't seem to be contributing to the stringiness problem.
My hunch was that the problem was mostly due to the fact that I process cells in a fixed order. A little background, in case you're rusty on the details. For each spark, I look at each of the eight nearest neighbors to see if they've been assigned, and if not, I assign them and add them to the (stack, queue, or array) structure of cells to check later. With the queue-based algorithm - well, actually, with all of the algorithms - I place them in the data structure in a fixed order. If "5" represents the center cell, then using the following numbering
123
456
789
the cells are always added in the following order: 12346789. With the queue, then, they always get pulled off in the same order, and I'd expect to see a diagonal stringiness.
My attempted fix yesterday was to randomize the order the neighboring cells go onto the queue. Surprisingly, I didn't detect much of a difference in the generated worlds. It's quite possible there's some other bug in my code which is exacerbating this problem, or maybe the queue data structure is just fundamentally wrong for this algorithm. For completeness, and since you say it's so easy to crank out the GIF files, I enclose a sample world using this modified algorithm. Note that I no longer bother to print out "W" for water (or was it "S" for sea?). You'll only see "L" for land. Later (i.e., tonight or tomorrow) I may also add something like "C" for city.
The good news, such as it is, is that the algorithm is plenty quick. A world of this size (50 x 70) takes maybe a second to generate. A 300 x 300 world takes 5 seconds, and 500 x 500 is about 10 seconds. Of course this is on a 200 MHz Pentium Pro processor, but it's running through the debugger with all optimizations turned off. Later I'll check on non-debugger fully optimized speeds, just for grins.
The tape arrived Saturday. Thanks for the cute deck of cards. I tried a couple hands of solitaire, and concluded the manufacturer needs to hire a new game designer. The poker variations sound just like something my old high-school poker crowd would dream up after a few hours and a bunch of beers, and I'll make a point of bringing the deck to the next game.
Paul