Dragon curve

From Rosetta Code

Jump to: navigation, search
This page uses content from Wikipedia. The original article was at Drachenkurve. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU Free Documentation License.

Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.

Code examples should be formatted along the lines of one of the existing prototypes.
Create a dragon curve fractal.

Contents

[edit] BASIC

Works with: FreeBASIC

Works with: QuickBasic version 4.5 

 
DIM SHARED angle AS DOUBLE
 
SUB turn (degrees AS DOUBLE)
    angle = angle + degrees*3.14159265/180
END SUB
 
SUB forward (length AS DOUBLE)
    LINE - STEP (COS(angle)*length, SIN(angle)*length), 7
END SUB
 
SUB dragon (length AS DOUBLE, split AS INTEGER, d AS DOUBLE)
    IF split=0 THEN
        forward length
    ELSE
	turn d*45
	dragon length/1.4142136, split-1, 1
	turn -d*90
	dragon length/1.4142136, split-1, -1
	turn d*45
    END IF
END SUB
 
' Main program
 
SCREEN 12
angle = 0
PSET (150,180), 0
dragon 400, 12, 1
SLEEP
 

[edit] Common Lisp

Library: CLIM

This implementation uses nested transformations rather than turtle motions. with-scaling, etc. establish transformations for the drawing which occurs within them.

The recursive dragon-part function draws a curve connecting (0,0) to (1,0); if depth is 0 then the curve is a straight line. bend-direction is either 1 or -1 to specify whether the deviation from a straight line should be to the right or left. 

(defpackage #:dragon
  (:use #:clim-lisp #:clim)
  (:export #:dragon #:dragon-part))
(in-package #:dragon)

(defun dragon-part (depth bend-direction)
  (if (zerop depth)
      (draw-line* *standard-output* 0 0 1 0)
      (with-scaling (t (/ (sqrt 2)))
        (with-rotation (t (* pi -1/4 bend-direction))
          (dragon-part (1- depth) 1)
          (with-translation (t 1 0)
            (with-rotation (t (* pi 1/2 bend-direction))
              (dragon-part (1- depth) -1)))))))

(defun dragon (&optional (depth 7) (size 100))
  (with-room-for-graphics ()
    (with-scaling (t size)
      (dragon-part depth 1))))

[edit] D

A text version of Dragon curve.
The Dragon curve drawn using an L-system.

  • variables : X Y F
  • constants : + −
  • start  : FX
  • rules  : (X → X+YF+),(Y → -FX-Y)
  • angle  : 90° 
 
module txdraco ;    // text dragon curve
import std.stdio ;
 
const int[][] dirs = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]] ;
const char[]  trace = r"-\|/-\|/" ;
 
struct Board {
  char[][] b = [[0]] ; // set at least 1x1 board
  int shiftx = 0 ;
  int shifty = 0 ;
  const char spc = ' ' ;  
  void clear() {  shiftx = shifty = 0 ; b = [[0]] ; } 
  void check(int x, int y) {
    while( y + shifty < 0) {
      char[] newr = new char[b[0].length] ; 
      newr[] = spc ;
      b = newr ~ b ;
      shifty++ ;
    }
    while( y + shifty >= b.length) {
      char[] newr = new char[b[0].length] ;     
      newr[] = spc ;
      b ~= newr ;     
    }
    while( x + shiftx < 0) {
      foreach(inout c ; b) 
        c = [spc] ~ c ;
      shiftx++ ;
    }
    while ( x + shiftx >= b[0].length ) 
      foreach(inout c ; b) 
        c ~= [spc] ;
  } 
  char opIndexAssign(char value, int x, int y) {
    check(x,y) ;
    b[y + shifty][x + shiftx] = value ;
    return value ;
  } 
  string toString() {
    string s ;
    foreach(c ; b)
      s ~= std.format.format("%s\n",  c) ;
    return s ;
  }
}
struct TState {
  int x = 0, y = 0, heading = 0;
}
struct Turtle {
  TState t ;
  void reset() { t.x = t.y = t.heading = 0 ; } 
  void turn(int dir) { t.heading = (t.heading + 8 + dir) % 8 ; }
  void forward(inout Board b) {
    with(t) {
      x += dirs[heading][0] ;
      y += dirs[heading][1] ;
      b[x,y] = trace[heading] ;
      x += dirs[heading][0] ;
      y += dirs[heading][1] ;
      b[x,y] = b.spc ;
    }
  }
}
void dragonX(int n, inout Turtle t, inout Board b) {
  if(n >= 0) {  // X -> X+YF+
    dragonX(n - 1, t, b) ;
    t.turn(2) ;
    dragonY(n - 1, t, b) ;
    t.forward(b) ;
    t.turn(2) ;
  }   
}
void dragonY(int n, inout Turtle t, inout Board b) {
  if(n >= 0) {  // Y -> -FX-Y
    t.turn(-2) ;
    t.forward(b) ;
    dragonX(n - 1, t, b) ;
    t.turn(-2) ;
    dragonY(n - 1, t, b) ;
  }   
}
void main() {
  Turtle t ;
  Board b ;
                       // initiator : FX
  t.forward(b) ;       // <- F
  dragonX(8, t, b) ;   // <- X 
  writefln(b) ; 
}

[edit] Logo

to dcr :step :length
  make "step :step - 1
  make "length :length / 1.41421
  if :step > 0 [rt 45 dcr :step :length lt 90 dcl :step :length rt 45]
  if :step = 0 [rt 45 fd :length lt 90 fd :length rt 45]
end

to dcl :step :length
  make "step :step - 1
  make "length :length / 1.41421
  if :step > 0 [lt 45 dcr :step :length rt 90 dcl :step :length lt 45]
  if :step = 0 [lt 45 fd :length rt 90 fd :length lt 45]
end

The program can be started using dcr 4 300 or dcl 4 300.

Or removing duplication: 

to dc :step :length :dir
  if :step = 0 [fd :length stop]
  rt :dir
  dc :step-1 :length/1.41421  45
  lt :dir lt :dir
  dc :step-1 :length/1.41421 -45
  rt :dir
end
to dragon :step :length
  dc :step :length 45
end

An alternative approach by using sentence-like grammar using four productions o->on, n->wn, w->ws, s->os. O, S, N and W mean cardinal points. 

to O :step :length
  if :step=1 [Rt 90 fd :length Lt 90] [O (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end

to N :step :length
  if :step=1 [fd :length] [W (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end

to W :step :length
  if :step=1 [Lt 90 fd :length Rt 90] [W (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end 

to S :step :length
  if :step=1 [Rt 180 fd :length Lt 180] [O (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end

[edit] Pascal

using Compas (Pascal with Logo-expansion): 

 
 procedure dcr(step,dir:integer;length:real);
  begin;
   step:=step -1;
   length:= length/sqrt(2);
   if dir > 0 then
    begin
      if step > 0 then
      begin
        turnright(45);
        dcr(step,1,length);
        turnleft(90);
        dcr(step,0,length);
        turnright(45);
      end
      else
      begin
        turnright(45);
        forward(length);
        turnleft(90);
        forward(length);
        turnright(45);
      end;
    end
   else
    begin
      if step > 0 then
      begin
        turnleft(45);
        dcr(step,1,length);
        turnright(90);
        dcr(step,0,length);
        turnleft(45);
      end
      else
      begin
        turnleft(45);
        forward(length);
        turnright(90);
        forward(length);
        turnleft(45);
      end;
    end;
 end;
 

main program: 

 
 begin
  init;
  penup;
  back(100);
  pendown;
  dcr(step,direction,length);
  close;
 end.
 

[edit] Python

Translation of: Logo

Library: turtle 

 
from turtle import *
 
def dragon(step, length):
    dcr(step, length)
 
def dcr(step, length):
    step -= 1
    length /= 1.41421
    if step > 0:
        right(45)
        dcr(step, length)
        left(90)
        dcl(step, length)
        right(45)
    else:
        right(45)
        forward(length)
        left(90)
        forward(length)
        right(45)
 
def dcl(step, length):
    step -= 1
    length /= 1.41421
 
    if step > 0:
        left(45)
        dcr(step, length)
        right(90)
        dcl(step, length)
        left(45)
    else:
        left(45)
        forward(length)
        right(90)
        forward(length)
        left(45)
 

This is an idiomatic python version: 

 
from turtle import *
 
def dragon(step, length, zig=right, zag=left):
    if step <= 0:
        forward(length)
        return
 
    step -= 1
    length /= 1.41421
 
    zig(45)
    dragon(step, length, right, left)
    zag(90)
    dragon(step, length, left, right)
    zig(45)           
 
Retrieved from "http://rosettacode.org/wiki/Dragon_curve"
Personal tools