Aug 23, 2010

I Have Sold My Soul

I feel I must publicly admit this here to you all. I have purchase some Apple products. I have an interest in making apps for the iPad, so I went out and bought one. However it turned out to be fairly useless for development on its own, an actual Mac is necessary. So I picked up a Mac Mini off eBay for dirt cheap and have started working with that.

So what are my thoughts on it? Well, my first thoughts are that it is a pain in the ass. It isn't the interface really (learning a new OS is always tricky, so I'm not really factoring that into my considerations). What I'm talking about is Apple itself. The system is not that old, it is running Tiger, but it is a bit annoying to get things from Apple for it. They seem adamant on trying to get you to purchase Snow Leopard at every turn (which I ended up having to do anyway, since XCode with the correct iOS SDK does not work with Tiger). At least with Windows stuff still works on XP (I can't believe I'm sticking up for Microsoft) without having Windows 7 being stuffed down your throat. However to even things out, Mac software upgrades are far cheaper than Windows ones, so it doesn't hurt that much paying for it if I am considering it as a potential business investment.

Anyway, it might be that I am just not used to the system yet, but I still haven't seen what all the Mac fanboys are raving about. The only thing that I do know at this point is that Apple has bothered me enough that I have absolutely zero desire to purchase any more of their products - although I may end up doing it anyway, depending on how well this whole iPad app thing goes.

What about my Touch Book? Well, I wasn't especially enamoured with it. It was a bit too sluggish for the things I wanted to do and since I bought the iPad I really had no more use for it. I hope the new owner is happy and may it serve him well.

Anyway you can expect a few Objective-C related posts coming up here in the near future.

Aug 3, 2010

Introducing L-Systems

My apologies, I haven't been writing as much these days; I've been having a bit of a blogger's block as to what to write about. I've got a few other statistics articles in mind, however since I enjoy variety I don't really want to write about the same thing all the time. So I'll reach out to the readers, is there any topic in particular you'd like me to write about?

Now that that is taken care of, we can get down to business. I've been doing a lot of reading these days, and one thing that I've stumbled upon are a nifty little computer science topic called L-systems. These things are quite simple to describe, yet are able to produce all sorts of interesting results (have you noticed a common theme to some of my blog posts these days?).

You need 3 things to describe an L-system. The first is an alphabet. An alphabet is very simple, it is just a set of characters that you will use within your alphabet - nothing more, nothing less. This is similar to a programming language where your alphabet is some subset of the ASCII character set unless you're using something more esoteric like APL (which is actually pretty neat, I've been looking at it a bit recently and I might put up a post about it soon - I guess I don't have blogger's block after all! You're still welcome to give requests though :) ).
The next thing you need for an L-system is an axiom. An axiom is simply a finite, non-empty string from your alphabet. You can also call it a seed if you like. The axiom (or seed) serves as the basis for the growth of the system.
The third thing is the most important - the production rules. What these do is map a character in the alphabet to some string. You apply the production rules on the axiom by converting each character in the axiom to whatever the rules say it maps to.

Let's consider an example L-system:
Alphabet: F, +, -
Axiom: F++F++F
F -> F-F++F-F
+ -> +
- -> -
It is not necessary to specify the rules for + and -, since if you don't include them it is assumed that they just map to themselves (the identity function).

Let's run this L-system through one iteration. Begin with the axiom:
Then apply the rules:
I'd go for another iteration or two, but as you can see this thing will grow quickly and the text would probably run outside of this div. I'll just let you use your imagination as to what the next iteration would look like.

You may wonder why I picked this specific alphabet, as it looks rather peculiar. It turns out that this alphabet is directions for a turtle. The F means go forward, the + means turn left, and the - means turn right, all the while drawing a line.

Suppose we make the angle that the turtle turns equal to 60 degrees and iterate 4 times, you'll end up with a picture like this:

If you iterated this L-system an infinite number of times and at each iteration divide the distance that the turtle moves on each F by 3, you would end up with a fractal called the Koch snowflake (I made the mistake of saying that name out loud to my girlfriend, which caused her to giggle uncontrollably - perhaps I pronounced it wrong).

The next thing we can do is give our turtle an upgrade. In the current state, the turtle is limited to only drawing convoluted lines. While this is good, there are a great many interesting things to draw that aren't lines. We can change this by adding a powerful new feature to the turtle with these two symbols: [ and ]. The [ will push the current state of the turtle onto a stack (there is only one stack, so I should call it the stack), and ] will pop that state off of the stack and restore the turtle to that state.

This gives us a lot more power to create interesting images. Consider this L-system:
Alphabet: F, [, ], +, -
Axiom: F
F -> FF-[-F+F+F]+[+F-F-F]
If you iterate this system 4 times, use an angle of 22.5 degrees and a step size of 6 pixels for your turtle, you get something like this (grabbed from The Algorithmic Beauty of Plants (The Virtual Laboratory)):

That's a bit cooler! And that image is generated by a completely deterministic process (aka no randomness). Which means that unlike my fractal trees, you will get exactly the same picture if you follow the rules above.

You can take these L-system things much much further, however I can see your eyes beginning to glaze over, so I will save that discussion for another day. As for code, you can see the L-system parser here, and the turtle graphics renderer here.