dc.py

Created by prokls

Created on May 04, 2019

2.74 KB

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.

```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')