Mar 29, 2009

Discovering Fractals: The Mandelbrot Set

I read a blog post a while back about content generation in video games, one section of which is terrain generation. One interesting way to generate realistic terrain is using fractals. One of the most well-known and relatively basic fractals is the Mandelbrot set. After reading through this article I decided to write a simple program that generates pictures based on this set.

Here's how the set works. You take a complex number c. You then take a sequence described by the following formula:
zi+1 = zi2 + c
Where z0 = 0. If this sequence is bounded (it does not escape to infinity), then c is in the set, otherwise it is not.

You can display this using a program by taking each pixel in your window and converting it to a complex number. You then test to see if the number is in the set by iterating over it a certain number of times to see what happens. Of course you won't be 100% precise, but with enough iterations you can get a pretty good approximation.

On top of this you can make it look even prettier by tweaking the colour depending on how quickly each point escapes to infinity. If it shoots off into infinity immediately, you make it darker. If it takes a while, then you make it lighter. I used the following formula:
colour = (0, 0, i / n * 255)
Where i is the iteration that the number escaped a certain threshold where the norm of the complex number is greater than this threshold (I used 2 and 3, didn't notice a huge difference between them) and n is the number of iterations (I used 500, 1000 and 2000, 1000 made the prettiest picture). This means that the colour of each pixel ranges between black and bright blue.

Here's what I got when I calculated it centred at c = 0.38 + 0.1i, with 64x zoom (where 1x zoom is in (1 + i to -1 - i)), 1000 iterations and a threshold of 2 - unfortunately when viewing the picture in the browser (at least for me on Ubuntu with Firefox) it doesn't look as nice as if you actually download the thing so I recommend you do that to appreciate it more:

That's pretty eh?

One thing that I find neat about this set is that it is self-similar. Each one of those little blue blobs is how the picture looks if you centre at 0 + 0i and have 1x zoom. You can then zoom into each one of those and see little bumps on the side that also look exactly the same as the whole. And each of those bumps has smaller bumps on it that also look the same. Pretty cool eh?

UPDATE: I wrote a follow-up about this here.


lili said...


Michael Mol said...

We've got a Dragon Curve task over on Rosetta Code. Would you care to seed something similar for the Mandlebrot set?

Rob Britton said...

@Michael: Done and done:

Turns out not only have people tweaked my C example (by adding a graphics library, I just did something that assumed put_pixel() would work), they've added versions in other languages too! These guys are fast.

One interesting thing to note is that in the C++ example, they use std::complex. The code that I use to generate the images is written in C++, and originally I also used std::complex. However, std::complex is far slower than just using a bunch of doubles. Depending on what percentage of visible pixels escape or not, the computation with std::complex takes about 5-10 seconds. With doubles it takes under a second and it is possible to watch an animated version of the set changing colour.

Michael Mol said...

@Rob Thanks!

Yeah, these guys are fast. Most of us watch the wiki's recent changes feed, and several folks jump almost immediately on any new task. Keep us in mind whenever you're experimenting with fractals. :-)