Fractals have been something that I've found really intriguing since high school, though, I've never taken too much of a stab at trying to generate them.  For a few assignments back in my CS1 class we had to use Python and the Turtle package to draw some.  These were done mainly to teach the concepts of recursion, state, and using geometry in computer programs; pretty basic stuff.  I imagine that almost everyone has had to use Turtle at some point in their CS coursework, and incidentally, has drawn a fractal.

Last year I was taking a course in Global Illumination.  We had to do two projects over the semester.  Write a ray tracer (throughout the weeks) and explore a graphics related topic of your choosing.  For that second one, some students chose to look into ray marching or real time raytracing.  I wanted to look at fractals some more.

After talking with one of my friends, he told me to look up something called "L-Systems."  The full name is "Lindenmayer System," and it's the magic behind fractal generation.  In a nutshell, the idea behind it is to create a grammar (yeah, one of the CS theory ones) and give each letter (or variable) an action (e.g. "draw line forward 10 units," or "rotate 45 degrees clockwise,").  The simplest example I can think of is the Cantor Set on the L-System wiki page.

Even though I was already making a 3D graphics program for the class, I decided writing a Blender script would be the best.  Here are some of my reasons why:

1. All the tools, libraries, and rendering infrastructure is already there.  I only need to focus on the tree logic
2. My Ray Tracer has a .obj file loader, so all I need to do is export it from Blender as a Wavefront object
   • On top of it too, I was also able to export it as a .stl, load it into slic3r, and materialise it on my 3D printer.  Pretty cool!
3. Blender is widely used and some others might find my script useful

So working in Blender there isn't a 3D Turtle object you can rely on to do the drawing.  But instead, you have to work with Matrices.  The basic idea of what you need to do is this:

1. Chain a bunch of matrices (appending and popping to/from the end of a list works well).  Most of what you'll need will come from Matrix.Translation() and Matrix.Rotation().  These are equivalent of the Turtle movement commands forward() and left()/right()
   • Make sure you chose one axis as your "forward," direction.  For my script, I always made translations in the Z+ direction.
2. Compute the result of the matrix chain, by taking the leftmost (first) matrix, then multiply it by it's neighbor to the right.  Rinse and repeat until you have one matrix left
3. Create a new 3D mesh (e.g. via bpy.ops.mesh.primitive_cylinder_add())
4. Blender will consider the newly created mesh as the "currently active object."  So multiply that new mesh's world matrix by the computed matrix chain:
   • bpy.context.active_object.matrix_world *= computed_matrix_chain
5. And voila!  It should be in the location and orientation you want it.  From here you can go to a deeper level of the fractal or move back up.  Don't forgot to pop those matrices off the end of your chain!

If you're still a little bit confused, take a look at the git repo over here.  All of the necessary code is in l-system_tree.py.  It's pretty simple and you should be able to follow along.  My L-System grammar is quite uncomplicated:

• A → BCDE
• B → A
• C → A
• D → A
• E → A

"A," also means "draw a branch," whereas "B," "C," "D," and "E," mean rotate about an axis (each one is different).  Each variable also checks the current depth to make sure that it isn't going on forever, though only "A," really needs to check for that.

There are a few other configuration options that I threw in (e.g. TWIST) so I could make some different looking trees.  Below is an example of one of the trees that I made with VARIATION_MODE turned on; it gives the tree a much more natural looking feel.

I remember first seeing this book in an newsletter from the Pragmatic Bookshelf a year ago.  It caught my attention because it seemed like a publication that was on a very niche topic yet fun.  I didn't get a copy of it when it was released because I was busy at the time with schoolwork (and then forgot about it).  Though a month ago I was down in on a weekend trip to D.C. and I saw it in a bookstore I visited; I decided to buy a copy since I have a lot more free time right now.  Being interested in game development, computer graphics, and procedural generation, I found this book to be a delight to read.

The Code

All of the code for each chapter (except for a POV-Ray file) is in Ruby.  My best guess why the author (Jamis Buck) chose to use Ruby is that he is a former contributor for the core team on the Rails projects.  His GitHub page is also littered with Ruby projects, so I assume it's what he's most comfortable with.

If you have zero experience in Ruby, fear not, neither did I before reading this book.  Not knowing Ruby should not be an obstacle to understand what is going on.  As long as you have a lot of experience with many different languages it shouldn't be difficult.  Most of the source reads like Pseudocode.  Only a few times did I find myself checking the Ruby documentation (e.g. Array.sample, or Ruby Blocks) to understand something unknown.  If you are looking to get familiar with the syntax of Ruby (or only to get your feet wet), I think this is a good start, but keep in mind that author's goal is not to teach you Ruby.  Personally, I would have preferred the sample code to be in Python, but that's just me.

Of the tech books I've read, I've gone through many that have given me incomplete code examples (i.e. snippets) or code that breaks on running it.  It's one of the most frustrating things out there!  Buck and the rest of the team that worked on this project did a very good job on making sure all of the code worked as it should.  I wasn't able to find a single issue with anything.  All of the code provided were complete examples.  A+

Everything builds on top of what you've done in the previous chapter, so I don't recommend skipping around.  Lots of inheritance and code reuse, which is good!

The Content

Most of the book's pages are dedicated to the generation of mazes in a 2D space.  In the beginning he talks about some simple algorithms like Binary Tree and Sidewinder, but later moves on to other methods that generate some more interesting maze designs.  There really isn't much of anything in the realm of solving mazes outside of discussing Dijkstra's Algorithm.  I really wish there were more included.

There was more covered than maze generation for rectangles.  I found the sections on polar, triangle and hex grids really fascinating, but the Weave grids were the best in show (to me at least).  There was also some pages for fitting mazes to odd shapes and designs.

In the later chapters Buck does show you how to generate a three dimensional maze (and talks a tad bit about 4D), but I found the representation of them to be a little difficult to follow (little red arrows are used to shift dimensions).  I would have favored something with 3D graphics instead.  That's a lot more complicated than 2D drawings and beyond the scope of this book though

One thing that was really well done was how algorithms were described with step-by-step drawings.  More books really should be doing this.  I've seen it too many times were only a single image or two are given when really seventeen should be provided  to show a run-through of an algorithm.  This made the algorithms really easy to understand without having to read any code.

Extra Cool Things

Something that I really appreciated is he included some code on how to display the mazes in a terminal window.  These only work for the 2D rectangular mazes (the early chapters), but I still found it nice since I love ASCII art.

At the end of the book there are two appendices that cover the maze algorithms explained.  The first one is an overview of what each algorithm does along with a picture of it.  The second one goes over some benchmarking/statistics of the various algorithms; very useful.

Final Thoughts

This book was worth the money I paid for it.  I don't think I'll be using anything I've learned in it immediately, but I know I will sometime down the road in my video game endeavors.  It's not a definitive source on mazes but a really good starting point.  I really would have loved some more chapters on maze solving.  One on interacting with the puzzles we generate would be cool too, but that falls more into game programming.  It has also done something for me that I've never expected; opening me up to Ruby.

It's been a while since I've read a programming book that wasn't overly dry.  Everything flowed nicely and kept me interested in learning what was coming next.  I really recommend reading this book if the subject matter sounds interesting to you.  It will be enjoyable.

While I've been underway working on the C# Networking tutorial series I've been doing quite a few site updates.  It's given me a chance to add some Dart code to the site and I've decided to share some of the little playthings that I make with it.  You can find them over here.  It's not supposed to be a rational tutorial/walkthrough; nothing builds upon itself.  They are one-shot samples.  I don't plan on regularly updating it, just when I want to.