Fractal Landscapes

In the introduction to my previous project, I explained the idea: Using Python to program old skool demo style real-time vector graphics. The finished project can be found here. This post is about a different part of the same demo - random Fractal Landscapes. 

Again, Python code can be found in GitHub.

Fractals They Are

Apparently, Benoit Mandelbrot has defined fractals as "a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole". These landscapes use a simple mid-point replacement algorithm to generate random fractal landscapes, which can be indefinitely zoomed into. 

The original Amiga demo (1992) used a fixed 65 x 65 point grid (i.e. 4,225 random grid values for 8,192 triangle surfaces between them), but this Python version can switch between (2^n + 1) x (2^n + 1) point grids, n being between 3 and 10 (i.e. 81 to 1,050,625 grid points and 128 to 2,097,152 surfaces). On the Amiga machine language and Blitter it took about two seconds to draw a new landscape; on my PC it takes about the same time to draw a 2^8+1 version - 16 times as many surfaces. Although the screen resolution on my PC is also a lot higher (about 25 times the number of pixels drawn), this mainly shows how slow (my) Python implementation is. 

Fractal Routine

Generating a landscape is simple, especially as its grid size is always 2^n+1. First, the corners are set. Then a simple loop goes through the mid-points so that they are set as the average of the end-points plus a random change. The size of the random change is halved after each round, as the distance of the end-points is also half of what it was the previous round. Unfortunately, I could not figure out a nicer way of achieving this without looping through single points.

    def generateGrid(self):
        
        # full grid generation. Start from corners.
        rSize = self.randSize
        startSize = self.landSize
        # set corner values. Tilt: Use higher altitudes for back of grid.
        self.grid[0, 0] = (random.random() - 0.5 + self.tilt * 2) * rSize
        self.grid[0, self.gridSize] = (random.random() - 0.5 + self.tilt * 2) * rSize
        self.grid[self.gridSize, 0] = (random.random() - 0.5 - self.tilt) * rSize
        self.grid[self.gridSize, self.gridSize] = (random.random() - 0.5 - self.tilt) * rSize
            
        # go through grid by adding a mid point first on axis 0 (X), then on axis 1 (Z), as average of end points + a random shift
        # each round the rSize will be halved as the distance between end points (step) is halved as well
        for s in range(startSize, 0, -1):
            halfStep = 2 ** (s - 1)
            step = 2 * halfStep
            # generate mid point in x for each z
            for z in range(0, self.gridSize + 1, step):
                for x in range(step, self.gridSize + 1, step):
                    self.grid[x - halfStep, z] = (self.grid[x - step, z] + self.grid[x, z]) / 2 + (random.random() - 0.5) * rSize
            # generate mid point in z for each x (including the nex x just created, so using halfStep)
            for x in range(0, self.gridSize + 1, halfStep):
                for z in range(step, self.gridSize + 1, step):
                    self.grid[x, z - halfStep] = (self.grid[x, z - step] + self.grid[x, z]) / 2 + (random.random() - 0.5) * rSize
            rSize = rSize / 2

Mountains and the sea

The coloring reflects the original demo: high altitudes are ice, then one has brown soil, and close to sea levels, green vegetation. The sea is a nice blue, and while it is generated in exactly the same way as land, it is drawn flat and the (negative) height only defines its color. For land, the color is given by how steep the triangle shape is, giving a shaded look.

To the Drawing Board

Drawing the fractals on screen is simple - start from the back, and for each grid square, draw two triangles. As the viewer is above sea level, the sea level coordinate of each new row is at a lower level than that of the previous row, and for perspective, the horizontal distance between the grid points grows the closer to the viewer we get.

Zooming in

As the definition above implies, one can take a part of a fractal, look at it closer, and it will have the same general properties as the original. These landscapes can be zoomed into indefinitely. There is a mouse-controlled zoomer, which can be used for selecting any quarter of the land area, and then zoom into it. Of course, zooming into a mountain will soon lead to that mountain growing so high that it goes entirely out of sight; so zooming in on some island in the sea is a better idea.

Zooming is quite simple. Take the zoomed area grid, and spread it to the whole grid, filling in every one in four grid points, and at the same time doubling the height. Then, use the last phase of random mid-point replacement algorithm to fill in the empty grid points.

The video clip shows zooming in action.

User Controls

There are some additional user controls in the Python version. They are listed in the information area above the landscape - cursor keys for controlling the grid size and general steepness, f to toggle full screen on/off. As in the original, left mouse button creates a new landscape, while right mouse button zooms the mouse-selected area.

Parallel Thoughts

Having a large number of grid points to calculate or triangles to draw sounds like a good candidate for using all processor cores. Alas, this is not the case here. For grid points there could be some complications as the number of points calculated in each step varies and the points depend on the previous step. Perhaps drawing the triangles would be easier, but I could not get even simple examples of Pool or Process to really work. Some say there are issues with the environment I use (namely, Spyder (4.0.1)). Perhaps sometime later...