Algorithm Overview
This is an algorithm for computing a blocky fractal-like shape. It starts with a seed shape (usually a simple square). At each iteration, it doubles the size of the shape and adds and removes tiles around the edges.
BlockFractal can start with any shape, closed or open, as long as there are no holes and the path doesn't intersect itself. By default it starts with a 2x2 square, centered at 0,0:
The first step in each iteration is always to double the shape:
Now we loop through the edges in order. The first edge in the default shape is the north edge of the north-west-most tile:
Except for some special cases, there are three choices for each edge:
- Keep the edge as-is
- Shift the edge toward the negative side of its perpendicular axis
- Shift the edge toward the positive side of its perpendicular axis
The variation parameter controls how often the first choice is made. By default, variation is 0.4, meaning that 60% of the time the edge is unchanged, and 40% of the time it is moved. If it is moved, the choice of which direction to move is 50-50.
In the previous image, we might choose to move the edge north or south, or not at all. Say we move it to the south. We add new edges to keep it connected, and move on to the next edge like this:
If we choose not to shift this edge, we move on to the next edge:
To set up a special case, let's shift this one to the south as well:
The first special case is when we choose to shift two adjacent and same-axis edges in the same direction. If we shifted this edge to the south as well, we'll hit that special case. A normal shift to the south would cause an empty "spike", where the path goes north and then immediately south. To prevent that, BlockFractal detects this case and removes the spike:
Now we move on to the next edge, which happens to be around the corner:
This is another special case. If we visit an edge that occurs just before a turn, and we shift that edge in the direction of the turn, then the post-turn edge will have no good choices. Whatever we do, that edge will either cause a spike or cause the path to intersect itself.
So when this happens BlockFractal just removes the problematic edge:
And we move on to the next one:
Now let's skip several steps, letting the algorithm as described play out until we near the end:
At this location, if we shift the edge to the east, it will touch a previous part of the path. This is something the algorithm must consider at every step: it must never shift an edge to create an intersection.
But in this particular location, no matter what we do we're going to cause an intersection. At the very last two edges, BlockFractal begins to worry about hitting the beginning of the path. If this happens even when the edge is left in place, then the fix is to remove parts from the beginning of the path:
And then we close the shape. So after one iteration, we have this:
For the next iteration, we double the shape and start again with the first edge:
