Lindenmayer Systems and the Logo Turtle
Posted by on September 21, 2011
Lindenmayer Systems, or L-Systems are not complicated. Take a string as a set of instructions in turtle graphics. “L” means “turn left”, “R” means “turn right”, and “F” means “go forward”.
Now imagine starting with a string “A” and a set of rules. You replace the characters in this string according to the rule a fixed number of times. Then for every type of character, you can either replace it with one of “L”, “R” or “F”, or ignore/remove it.
For example, suppose you have one rule,
A → AAAFLLAA
and a final rule
A → L
In this example, it takes 12 “L” or 12 “R” turns to turn completely around.
We start with “A” and apply the rule to get “AAAFLLAA”. We apply the rule again to get “AAAFLLAAAAAFLLAAAAAFLLAAFLLAAAFLLAAAAAFLLAA”, and so forth. In my example, I stopped when I got a string that would have 5000 forward moves in it.
Here’s what it looks like:
That’s one continuously traced path, all thanks to string rewriting. I’ve also created a page with a large number of random rules. It takes a lot of memory because of all the thumbnails, but if you’re curious about the rules used to generate a shape, simply follow the link to the SVG and “view source” to see what generated that shape.
Project Euler Level 5
Posted by on August 21, 2011
I finally made to to 200 problems! Better yet, I picked two of the problems that had been pestering me for a while:
As I was working on “Robot Walks”, I figured out that I’d come very close to the solution last year. I had a lookup table, but it had an incorrect value for orientation in cases where the robot moved in a complete circle right or left.
Another SVG animation
Posted by on July 29, 2011
Based on the same space-filling curve, but with a little more variety in the parameters.
SVG and javascript together
Posted by on July 28, 2011
Even though SVG allows for animation, sometimes it isn’t enough. It turns out that the SVG document object model (DOM) can be modified by self-contained javascript.
Here’s an example:
A grid is divided into cells, and then two cells that aren’t yet connected are joined, until the entire grid is connected. It’s a simple maze generator, and the number displayed in red is current highest cell number.
When javascript is included in XML, it’s not enough to put it in an <img> tag. You’ll need to embed it in an <object> tag, like so:
<object width=”501″ height=”245″ data=”http://ipsin.org/content/maze.svg” type=”image/svg+xml”></object>
the javascript module pattern
Posted by on July 13, 2011
This is definitely my favorite javascript pattern, since it allows for clean, modular libraries. If you’re writing your own javascript library, it’s an approach worth considering, even if you don’t use the YUI wrappers.
jpeg and tiles
Posted by on July 12, 2011
When slicing and dicing images, it’s important to pay attention to the format. JPEG 1992 uses minimum coded units of varying sizes, but using 16×16 blocks will guarantee that you don’t divide a block in all cases.
JPEG 2000 is a little more complicated, as the block size is variable.
Mercifully, few browsers support it.
SVG paths and declarative animations
Posted by on July 7, 2011
Suppose that you’re trying to create an animated path in SVG:
<path stroke="black">
<animate attributeName="d" dur="10s" repeatCount="indefinite"
values="&path1;&path2;&path3;&path1;"/>
</path>
One important thing you should note is that each path in the set of values should have exactly the same number of steps. If you don’t, the animation will be choppy and unpleasant.
If you do, though, your browser has at least some chance of animating it smoothly. I’m not sure if this is explicit in the spec, but in Chrome, at least, it’s currently necessary.
Here’s an example, animating the Hilbert curve at varying depths:
