Recursive Squares

Use recursion to pack squares inside squares inside squares

Preview

In this tutorial, we'll create a variation of the following image:

The program we'll be writing will generate this image by creating a grid of squares, randomly coloring them, then recursively placing another randomized grid of squares within each square of the larger grid, and so on. It produces a very unique output.

Before continuing, please ensure you have Xylo properly installed as per the instructions in the Quickstart.

Creating a Grid

Let's start by partitioning the canvas into a 2x2 grid:

root = l 0 FILL : collect (rows 0.0 0.0 (height / 2.0) 2)

rows x y size tiles =
    for i in 0..tiles
        collect (cols x y size tiles i)

cols x y size tiles i =
    for j in 0..tiles
        let x_pos = x - size + (i + 0.5) * size / tiles * 2
            y_pos = y - size + (j + 0.5) * size / tiles * 2
        ->
            t x_pos y_pos (ss (size / tiles - 2) SQUARE)

Here, we start in the root function by defining a fill with 0% lightness and composing it with the shapes from the rows function. We need to use collect because rows returns a list of shapes.

rows takes in four arguments: the x and y position of the center of the grid, the size of the grid (which is equal to half the dimensions), and the amount of tiles per row/column.

In our case, we're centering the grid on (0, 0), which is the center of the image, setting the grid to take up the full height of the image, and setting the amount of tiles to 2 by 2.

We call cols for each tile in the row, passing in the information we need as well as an additional i variable that represents the column number. Then, we create a square for each column, using j as the row number.

We then use some basic math to determine the position of each square in the grid. Each square is placed in a position based on the dimensions of the grid divided by the tiles and scaled to give a padding of 2 pixels. Keep in mind that the left and bottom sides of the canvas are always negative on the x and y axes respectively.

Let's see what the code generates:

xylo generate [filename].xylo

Great, it works! Let's continue by giving each square a random color.

To give it a consistent look and feel, we're going to use a color palette. You can choose your own if you want, but for this tutorial we'll use a Blue Screen palette found on Lospec.

We can copy the hexadecimals of this palette into our code by using the hex type. Then, we can generate a random number and match it to a color's hex value.

To do this, define this function:

rand_color =
    match randi_range 0 6
        0 -> 0xffffff
        1 -> 0xb8b8ef
        2 -> 0x7474e8
        3 -> 0x4646cc
        4 -> 0x2e2e8c
        5 -> 0x16164d

This will generate a random integer within the exclusive range [0, 6), which actually means from 0 to 5. You could also write this as randi_rangei 0 5, the first "i" meaning integer and the second "i" meaning inclusive range.

Once the integer is generated, the function uses a match statement to assign it to one of six RGB values within the palette, returning the hex type.

Once we have a hex value, we can assign it to a shape using the hex function. Let's do this within the cols function:

cols x y size tiles i =
    for j in 0..tiles
        let x_pos = x - size + (i + 0.5) * size / tiles * 2
            y_pos = y - size + (j + 0.5) * size / tiles * 2
        ->
            hex rand_color (t x_pos y_pos (ss (size / tiles - 2) SQUARE))

Now each square is being assigned a random color!

Let's generate some more images to make sure it works as intended:

Cool! It will now produce a different output each generation with a consistent color scheme.

Recursion

What we have is a good start. However, we're not here just to generate a simple grid, are we?

Want we want to do is take our grid, and create another, smaller grid within each square of the larger grid. Then, we want to do it again, and again, until the image is filled with tiny squares inside of bigger squares.

How can we do this? The answer is simple: recursion. We can define a grid function that creates a square, then generates a grid inside of it. Then, inside our cols function, we can call that grid function instead of creating a SQUARE, but giving it a different translation and smaller scale.

Let's begin by moving our root code to a grid function:

root = grid 0.0 0.0 (height / 2.0)

grid x y size =
    hex rand_color (t x y (ss size SQUARE))
    : collect (rows x y size 2)

If you run the code right now, you'll get a similar output as before. But this time, instead of using a black fill, we're appending the rows to a randomly colored square with a position and size that's the same as the grid.

Now, let's take things a step further and edit our cols function.

cols x y size tiles i =
    for j in 0..tiles
        let x_pos = x - size + (i + 0.5) * size / tiles * 2
            y_pos = y - size + (j + 0.5) * size / tiles * 2
        ->
            grid x_pos y_pos (size / tiles - 2)

You may notice that we're giving the grid the same position and size that we were giving the square that was here earlier (a position of (x_pos, y_pos) and a scale of size / tiles - 2).

Let's try running this. Once it's finished generating you should see-

Max call stack depth reached.

Wait, what is this? It seems like there's an issue with the code.

The grid function calls the rows function, which then calls the cols function, which then calls the grid function, which then calls the rows and cols functions again...

It's an infinite loop! It'll never stop running.

Xylo provides a max call stack depth that can be set with the --max-depth option. By default, it's set to 1500, which means a function can only call itself 1500 times before it fails. This feature allows infinite loops to be caught before they potentially crash your computer.

This is why recursive programs need what's called a base case. We can check for a certain condition where we want the program to end, then stop creating shapes upon reaching that position.

Let's go back to our grid function and stop the program when the size parameter is below a specific value:

grid x y size =
    if size <= height / 16.0
        EMPTY
    else
        hex rand_color (t x y (ss size SQUARE))
        : collect (rows x y size 2)

Now, when the size is eight times as small as what we started with, instead of returning more squares we return what is known as the "empty shape." In Xylo, empty shapes are simply skipped in the rendering process.

This means that grid will only be called four times. First, when we fill the screen with a grid of the size height / 2.0.

Then, once it reaches cols, it will created more grids with sizes of height / 4.0 - 2.

The next iteration, it creates grids with sizes `height / 8.0 - 3`.

And finally, it calls grid from cols one last time with a size of height / 16.0 - 3.5. At this point, it is less than height / 16.0, so instead of creating another square and calling rows again it returns an empty shape.

Let's see what this outputs:

Cool! Now that the program has a stopping point, it can render the shapes it creates.

What we have here are grids inside of grids. But what if we want grids inside of grids inside of grids inside of grids?

We just need to change the base condition to a smaller value! Let's do so:

grid x y size =
    if size <= height / 64.0
        EMPTY
    else
        hex rand_color (t x y (ss size SQUARE))
        : collect (rows x y size 2)

It's starting to look pretty neat! Let's add some more variation.

Currently, we are only generating 2x2 grids. We can make the outputs more interesting by randomizing the tile amounts.

For example, let's see what we get when we pass in a random integer from 2 to 5:

grid x y size =
    if size <= height / 64.0
        EMPTY
    else
        hex rand_color (t x y (ss size SQUARE))
        : collect (rows x y size (randi_rangei 2 5))

Now every image is even more unique!

Final Result

You may remember that at the start of this tutorial you were shown an image that included thousands of tiny squares. How was this created?

Simple. It simply used a smaller value for the base condition and a larger image size.

This will be our final code:

root = grid 0.0 0.0 (height / 2.0)

grid x y size =
    if size <= 2
        EMPTY
    else
        hex rand_color (t x y (ss size SQUARE))
        : collect (rows x y size (randi_rangei 2 5))

rows x y size tiles =
    for i in 0..tiles
        collect (cols x y size tiles i)

cols x y size tiles i =
    for j in 0..tiles
        let x_pos = x - size + (i + 0.5) * size / tiles * 2
            y_pos = y - size + (j + 0.5) * size / tiles * 2
        ->
            grid x_pos y_pos (size / tiles - 2)

rand_color =
    match randi_range 0 6
        0 -> 0xffffff
        1 -> 0xb8b8ef
        2 -> 0x7474e8
        3 -> 0x4646cc
        4 -> 0x2e2e8c
        5 -> 0x16164d

The only change made here is that instead of basing the condition on the height, we're simply setting it to a fixed 2, which means it will stop executing when size is less than 2 pixels.

It also means that the program will do deeper recursion the larger you set the image size.

Let's generate our final image with the following command:

xylo generate [filename].xylo --width 2048 --height 2048

Now let's see what a 2048x2048 image looks like with the final version of our code:

Holy moly! It looks kind of awesome, doesn't it?

So, what's next?

Play around with different values. You can change the image size, base condition, tile amounts, or color palette. Perhaps you can even arrange the squares a different way, for example by figuring out how to implement a square packing algorithm.

Just make sure not to create an infinite loop this time around.

That'll conclude this tutorial. If you enjoyed, be sure to leave a star in the GitHub repository and share it on social media. See you in the next one!