Fractal landscape

Time for an algorithmic interlude.

I’ve been playing with some code to generate a fractal landscape, and it had a flaw in it that was one of the more insidiously subtle bugs I’ve come across.

The classic way to do a fractal landscape is the diamond-square algorithm, but (for reasons I’m not revealing for now… ooooh, drama) I decided to do something different. The high-level algorithm is this:

  • Start with a small grid (say, 10×10) of uniformly random values. (The value will be the height of the landscape at that point.)
  • Repeat until big enough:
    • Expand the grid horizontally by one square as follows:
      • For each row, insert a new, empty square at a random location. Shift the squares after it to the right.
      • Set each new square’s value to the average of the four neighbouring squares, plus or minus a small random jitter. The landscape should be a torus (i.e. the right side wraps around to the left, and the top to the bottom, so that it can be tiled), so include squares on the opposite edge in the average if necessary. Disregard any neighbours that were newly created in the previous step.
    • Do the same thing vertically.

There’s some extra tweaking and smoothing and whatnot, but that’s the basic idea.

Now… what’s the flaw? There’s a prize* for the first person to find it.

* Prize not guaranteed to have material value or physical existence. Prizes will only be awarded for the particular flaw I have in mind, not any other flaw, whether I’d noticed it beforehand or not.

No comments

No comments yet. Be the first.

Leave a reply