The Intellectual Wilderness There is nothing more useless than doing efficiently that which should not be done at all.

2020.09.9 12:51

Erlang: Barnsley’s Fern

Filed under: Computing — Tags: , , , , — zxq9 @ 12:51

A mathematician friend of mine asked me the other day whether we used many techniques from fractal theory in game development. I told her that I didn’t think so, at least not formally. She asked me if I had ever implemented “Barnsley’s Fern” (Wikipedia) and of course I never had. So she asked me to implement it and tell her what I thought.

Her plan seems to have been to get me to recognize that we do use techniques derived from fractal theory all over the place by implementing a famous fractal by hand myself. The plan worked: it was immediately obvious to me that Barnsley’s Fern makes use of a technique that is central to the way random map generators work in game development, but I had never realized this was actually from “fractal theory”, having stumbled on the technique myself because it was a useful shortcut to making game maps that were interesting and felt natural(ish).

Here is the interesting part of the code:

The interesting part about that is the fact that the plotting of points is actually a random function, not a concretely defined rotation of an existing pattern. The constants involved in the fern1-4 functions are found here:

My Barnsley’s Fern implementation is available on gitlab and can be run using either ZX or Vapor if you have ZX on your system. The most recent version as of this post, 0.1.2, uses OpenGL to render the image and seems to work much more reliably across platforms than the previous implementation using a WX graphics context (some versions of WX don’t like the way I drew the points). In Vapor you can select the version with the version drop box if you want to see the WX implementation:

Or you can run it directly from ZX using the command line with:
zx run barnsley_fern

Here is what the OpenGL version looks like at 100001 iterations:

The OpenGL interface allows you to rotate and move the image around a bit, though in v0.1.2 the center of rotation is a bit off center. Also, if you have more than a few hundred thousand points it becomes cumbersome to render repeatedly in animation because it is actually re-plotting each frame (I didn’t go to the trouble to plot the points to a buffer or texture and simply rotate that instead).

The previous version looks like this at the same number of iterations:

The coordinate systems are different for the two implementations, hence the difference in the direction of the curve.

Hanging around mathematicians lately has made me realize that there is a tremendous amount of higher math involved in a lot of what we do in programming, but that the mathematicians rarely talk to the computer science people, and computer science people are living on their own little planet with little connection to what actual developers are doing in industry (all of us little people just “trying to make it go”). Further, the semantic map of what words are used to mean what in which context is an absolute mess, so it takes some patience and explanation to understand what the other person is saying half the time if you are talking outside your tribe.

Keep the patience! Explain exhaustively! Listen carefully! It is so much more interesting when you have a chance to confer with people outside your tribe!

Powered by WordPress