About

Showing posts with label graftal. Show all posts
Showing posts with label graftal. Show all posts

2/14/10

Coding: Graftal snowtree

Recursive deterministic graftal algorithm

This nice algorithm that I found in Computer Graphics: Principles & Practice inspired me to implement it. I it will generate a set of data that you can parse to construct a tree-like graphics structure. This algorithm is bases on a alphabet of 6 symbols:

The algorithm shall use those 6 symbols to mutate a starting-axiom into a full tree. These are the two simple rules of this sorta game-of-life:

To initialize the algorithm, you must choose a starting axiom. Following the rules indicates that 'A' is not a good choice, since that will only produce new 'A's. (A->AA). Therefore we choose 'B' wich will tranform into A(B)AA[B] and produce a standard pattern to generate the tree off. This is the produce string after just ONE recursion.

This is the string buffer after two runs. When implementing this algorithm, it is recommended to have overflow-safe stacks and buffers!. Now it is up to you to parse the tree and make the drawing happen. When parsing the tree after generating it, the 6 symbols have the current meaning: A and B(nodes) = continue to draw in current direction; [ and ) means rotate left; ] and ( means rotate right.

Basically you want two char[] buffers so as to render from buffer 1 to buffer 2 and from 2 to 1 in the next iteration. Remember that the buffer is filled up at a exponential rate. (In this picture, snowfall was also simulated). This code of mine implements it. (Never ask me about that code)