• Explore
• My scripts
• Calculator

Our implementation of the dragon curve. Implementation is joint work with Susi and Chris. Thanks!

We implemented 3 designs. All naive implementations ran out of memory after 9-11 iterations. But we generated A014707 (http://oeis.org/A014707) for 20 iterations and looked for patterns to compress the sequence. This resulted in the current implementation of turn() handling up to 20 iterations.

License: MIT license, Feedback: admin@lukas-prokop.at

import time      # 'cos I like to sleep
import kandinsky # 'cos I like to draw

# constants
L = 1   # Left turn
R = -1  # Right turn

# default configuration
iterations = 12
width = 4
x_center = 160
y_center = 111

# color wheel palette
colors = [
    (0, 0, 255), (0, 170, 255),
    (0, 255, 255), (25, 255, 160),
    (0, 255, 0), (160, 255, 25),
    (255, 255, 0), (255, 127, 0),
    (255, 0, 0), (255, 0, 170),
    (255, 0, 255), (127, 0, 255)
]
colors = [kandinsky.color(*c) for c in colors]

# algorithms
def make_turn(cur_x, cur_y, prev_x, prev_y, turn, w=width):
    """Given the segment's end points (prev and cur),
    and some turn direction, determine the next end point
    and draw all intermediate line points
    """
    if cur_x != prev_x:
        d = 1 if (prev_x > cur_x and turn == L
               or prev_x < cur_x and turn == R) else -1
        for yr in range(0, w + 1):
            yield cur_x, cur_y + d * yr
    elif cur_y != prev_y:
        d = 1 if (prev_y > cur_y and turn == R
               or prev_y < cur_y and turn == L) else -1
        for xr in range(0, w + 1):
            yield cur_x + d * xr, cur_y

X = 1826909284  # 0b1101100111001000110110001100100
def _turn64(i):
    j = i % 64
    if j == 15:
        return L
    elif j == 31:
        return L if (i % 128) < 64 else R
    elif j == 47:
        return R
    elif j != 63:
        return L if (X >> (j % 32)) & 1 == 0 else R
    else:
        return _turn64(i // 64)

def turn(i):
    """Returns whether a L or R turn shall be made in step i"""
    if i >= 1048575:
        raise NotImplementedError("only 20 iterations supported")
    j = i % 32
    if j == 15:
        return L if (i % 64) < 32 else R
    elif j != 31:
        return L if (X >> j) & 1 == 0 else R
    else:
        return _turn64(i // 32)

def _dragon(cur_x, cur_y, prev_x, prev_y, n, width):
    iteration = 1
    col = colors[iteration]

    for i in range(2**n - 1):
        if i == 2**iteration - 1:
            iteration += 1
            col = colors[iteration % len(colors)]
            time.sleep(0.5)
        for new in make_turn(cur_x, cur_y, prev_x, prev_y, turn(i), width):
            prev_x, prev_y = cur_x, cur_y
            cur_x, cur_y = new
            if 0 <= cur_x <= 320 and 0 <= cur_y <= 222:
                kandinsky.set_pixel(cur_x, cur_y, col)


def dragon(n=iterations, w=width):
    """Dragon curve implementation"""
    for rx in range(0, width + 1):
        kandinsky.set_pixel(x_center + rx, y_center, colors[0])
    _dragon(x_center + width, y_center, x_center, y_center, n, w)

# print manual
print('Dragon curve')
print('May 2019, MIT license')
print('by Chris, Lukas & Susi\n')
print('dragon({}, {})'.format(iterations, width))
print('  :n: iterations to do')
print('  :w: width of a segment')