【コードゴルフ】5行でフラクタル図形【JavaScript】

はじめに

前回、簡易エディタをコードゴルフしてみました。
今回はcanvasで、フラクタル図形を描画してみたいと思います。
特に深い理由はないです。コードゴルフする意味も特にありません。

フラクタル図形についてとても興味深い動画がこちら。おすすめです。

まずは普通に描く

今回はフラクタル図形の中でも取り分け有名な、シェルピンスキーのギャスケットを描きます。

以下のコードで、こういった描画になります。

シェルピンスキーのギャスケット.html

<canvas id="canvas" width="1000" height="1000"></canvas>
<script>
    const ctx = document.getElementById("canvas").getContext('2d');

    /** 最初の始点 */
    const X = 1000;
    const Y = 1000;

    /** 最初の辺長 */
    const LENGTH = 1000;

    // 最初の三角形を描画
    function drawIniTriangle() {
        ctx.beginPath();
        ctx.moveTo(X, Y);
        ctx.lineTo(X - LENGTH, Y);
        ctx.lineTo(X - LENGTH / 2, Y - LENGTH * 3 ** 0.5 / 2);
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }
    drawIniTriangle();

    // k=1の場合の、始点を求める
    function calcKeyPoint(x, y, l) {
        return [{
            x: x - l / 4,
            y: y - l * 3 ** 0.5 / 4
        }]
    }

    // k>=2の場合の、始点を求める
    function calcKeyPoints(x, y, l) {
        return [{
            x: x - l / 4,
            y: y - l * 3 ** 0.5 / 4
        }, {
            x: x + l / 4,
            y: y + l * 3 ** 0.5 / 4
        }, {
            x: x - l * 3 / 4,
            y: y + l * 3 ** 0.5 / 4
        }]
    }

    // 始点から下向き正三角形を描画
    function drawTriangle(x, y, l) {
        ctx.beginPath();
        ctx.moveTo(x, y);
        ctx.lineTo(x - l, y);
        ctx.lineTo(x - l / 2, y + l * 3 ** 0.5 / 2);
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }

    // k=1の下向き正三角形を描画 始点が1つ
    let point = calcKeyPoint(X, Y, LENGTH);
    point.forEach(v => drawTriangle(v.x, v.y, LENGTH / 2));

    // 前回の始点、辺長を保持
    let beforePoints = point;
    let beforeLength = LENGTH / 2;

    // k>=2の下向き正三角形を描画
    function drawFrame() {
        if (beforeLength < 10) {
            clearInterval(id);
            console.log('end')
        }
        let points = beforePoints.reduce((v, w) => {
            return v.concat(calcKeyPoints(w.x, w.y, beforeLength));
        }, []);
        points.forEach(v => drawTriangle(v.x, v.y, beforeLength / 2));
        beforePoints = points;
        beforeLength /= 2;
    }
    // requestAnimationFrameのほうがよいが、今回は簡易的なものなので省略
    let id = setInterval(drawFrame, 1000);
</script>

いったん解説

基本的には座標を求めるだけです。複素数は今回は使用しません。
Mathematicaではこちらで取り上げられていますので、複素平面を用いた手法について等がお好みの方はどうぞ。
まずはベースとなる正三角形の描画。

始点座標を(x, y)、辺長をnとした時
(ソース中ではlengthの頭文字でlにしてますが、数式でエルは見づらいためnとした)

始点から見て水平に左側の点は

(x-n, y)

てっぺんの点は

(x-\frac{1}{2}n, y+\frac{\sqrt{3}}{2}n)

となります。
※canvasなので左上が原点です。
よってソースはこう。

    // 最初の三角形を描画
    function drawIniTriangle() {
        ctx.beginPath();
        ctx.moveTo(X, Y);
        ctx.lineTo(X - LENGTH, Y);
        ctx.lineTo(X - LENGTH / 2, Y - LENGTH * 3 ** 0.5 / 2);
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }

そして内側に、下向きの正三角形を描きます。
この時、描画回数のことをkとして、今回はk=1の場合と呼ぶことにします。

始点は、最初の正三角形を書いた時の始点(x, y)、最初の辺長nを用いて

(x-\frac{1}{4}n, y-\frac{\sqrt{3}}{4}n)

と表せる。

    // k=1の場合の、始点を求める
    function calcKeyPoint(x, y, l) {
        return [{
            x: x - l / 4,
            y: y - l * 3 ** 0.5 / 4
        }]
    } // なんか使いまわせそうで配列にした

また、始点から下向きに正三角形を描くには、最初の大元となった正三角形の
「てっぺんの点」のy座標を求める際の符号が逆転するだけなので、以下になります。

    // 始点から下向き正三角形を描画
    function drawTriangle(x, y, l) {
        ctx.beginPath();
        ctx.moveTo(x, y);
        ctx.lineTo(x - l, y);
-       ctx.lineTo(X - LENGTH / 2, Y - LENGTH * 3 ** 0.5 / 2);
+       ctx.lineTo(x - l / 2, y + l * 3 ** 0.5 / 2);
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }

    // k=1の下向き正三角形を描画 始点が1つ
    let point = calcKeyPoint(X, Y, LENGTH);
    point.forEach(v => drawTriangle(v.x, v.y, LENGTH / 2));

次に、kが2以上の場合について
以下のように、前回の始点1つにつき、3つの始点が生まれます。

前回の始点から、上の始点は (k=1のときと同様の点で)

(x-\frac{1}{4}n, y-\frac{\sqrt{3}}{4}n)

すぐ下側の始点は

(x+\frac{1}{4}n, y+\frac{\sqrt{3}}{4}n)

左のほうの始点は

(x-\frac{3}{4}n, y+\frac{\sqrt{3}}{4}n)

と、前回の始点ひとつ→次の始点3つが算出できます。

    // k>=2の場合の、始点を求める
    function calcKeyPoints(x, y, l) {
        return [{
            x: x - l / 4,
            y: y - l * 3 ** 0.5 / 4
        }, {
            x: x + l / 4,
            y: y + l * 3 ** 0.5 / 4
        }, {
            x: x - l * 3 / 4,
            y: y + l * 3 ** 0.5 / 4
        }]
    }

前回の始点から次の始点を全て求め、辺長を半分にしながら、始点から下向き正三角形を描画します。

    // 前回の始点、辺長を保持
    let beforePoints = point; // ここではk=1のときの始点(1つのやつ)をセット
    let beforeLength = LENGTH / 2;

    // k>=2の下向き正三角形を描画
    function drawFrame() {
        // 無限に描画しないように、辺長が10を切ったら終了
        if (beforeLength < 10) {
            clearInterval(id);
            console.log('end')
        }

        // 前回の始点から、今回の始点を計算。3つずつ算出したものを、一つの配列にまとめている。
        let points = beforePoints.reduce((v, w) => {
            return v.concat(calcKeyPoints(w.x, w.y, beforeLength));
        }, []);

        // 今回分の全ての始点に対し、下向き正三角形を描画する。
        points.forEach(v => drawTriangle(v.x, v.y, beforeLength / 2));

        // 次ループのために今回分の始点を保持
        beforePoints = points;
        beforeLength /= 2; // 正三角形描画時に1/2倍で計算しているため、ここで辺長を半減してやる
    }
    // requestAnimationFrameのほうがよいが、今回は簡易的なものなので省略
    let id = setInterval(drawFrame, 1000);

これらにより、晴れて描画ができました。
最初のソースをcodepenで埋め込んだものがこちらです。（0.25xを押してください！）

See the Pen SierpinskiGasket by serna37 (@serna37) on CodePen.

リファクタする

現状、以下が特殊パターンとなってしまっています。
・最初の（外枠の）正三角形のみ、上向きである
・k=1の場合のみ始点が1つであり、以降は3個ずつ生まれる

これを解決するため、kを有効活用します。
・大元の正三角形の時をk=-1
・最初の下向き正三角形の時をk=0
となるようにしてみましょう。

<canvas id="canvas" width="1000" height="1000"></canvas>
<script>
    const ctx = document.getElementById("canvas").getContext('2d');

    /** 最初の始点 */
    const X = 1000;
    const Y = 1000;

    /** 最初の辺長 */
    const LENGTH = 1000;

    /** カウント */
    let k = -1;

-    // 最初の三角形を描画
-    function drawIniTriangle() {
-        ctx.beginPath();
-        ctx.moveTo(X, Y);
-        ctx.lineTo(X - LENGTH, Y);
-        ctx.lineTo(X - LENGTH / 2, Y - LENGTH * 3 ** 0.5 / 2);
-        ctx.closePath();
-        ctx.strokeStyle = "black";
-        ctx.stroke();
-    }
-    drawIniTriangle();

-    // k=1の場合の、始点を求める
-    function calcKeyPoint(x, y, l) {
-        return [{
-            x: x - l / 4,
-            y: y - l * 3 ** 0.5 / 4
-        }]
-    }

+   // 始点を求める
    function calcKeyPoints(x, y, l) {
        let points = [{
            x: x - l / 4,
            y: y - l * 3 ** 0.5 / 4
        }, {
            x: x + l / 4,
            y: y + l * 3 ** 0.5 / 4
        }, {
            x: x - l * 3 / 4,
            y: y + l * 3 ** 0.5 / 4
        }]
// 大元は最初の始点、次は1つ目の始点のみを返却するようにした
+       return k == -1 ? [{x:X,y:Y}] : k == 0 ? [points[0]] : points;
    }

    // 始点から下向き正三角形を描画
    function drawTriangle(x, y, l) {
        ctx.beginPath();
        ctx.moveTo(x, y);
        ctx.lineTo(x - l, y);
// 大元の場合のみ符号が逆転するようにした
+       ctx.lineTo(x - l / 2, y + (l * 3 ** 0.5 / 2)*(k==-1?-1:1));
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }

// 大元の正三角形、最初の下向き正三角形は、独自で描画しなくてよくなる
-   // k=1の下向き正三角形を描画 始点が1つ
-   let point = calcKeyPoint(X, Y, LENGTH);
-   point.forEach(v => drawTriangle(v.x, v.y, LENGTH / 2));

    // 始点、辺長を保持
+   let beforePoints = [{x:X,y:Y}];
+   let beforeLength = LENGTH * 2; // 辺長を半分にしてから計算するように変えた
// 初めは2倍しておく

-   // k>=2の下向き正三角形を描画
+   // 大元、最初、k>=1の描画
    function drawFrame() {
        if (beforeLength < 10) {
            clearInterval(id);
            console.log('end')
        }
        // この時点で保持変数を上書いちゃう
+       beforePoints = beforePoints.reduce((v, w) => {
            return v.concat(calcKeyPoints(w.x, w.y, beforeLength));
        }, []);
+       beforeLength /= 2; // この時点で半分にしとこう
        beforePoints.forEach(v => drawTriangle(v.x, v.y, beforeLength));
+       k++;
    }
    // requestAnimationFrameのほうがよいが、今回は簡易的なものなので省略
    let id = setInterval(drawFrame, 1000);
</script>

1度しか呼ばれない関数を排除することができました。

簡潔に

次に冗長、というか省略可能な部分を圧縮します。

<canvas id="canvas" width="1000" height="1000"></canvas>
<script>
    const ctx = document.getElementById("canvas").getContext('2d');
+ // ループ上限を辺長ではなく回数の最大値で判定
    const MAX = 4;
    let k = -1;
+ // 初期値の宣言等をまとめた
    let beforePoints = [[1000,1000]];
    let beforeLength = 2000

+ // オブジェクトでの宣言を2次元配列に変更
    function calcKeyPoints(x, y, l) {
        let points = [[
             x - l / 4,
             y - l * 3 ** 0.5 / 4
        ], [
            x + l / 4,
            y + l * 3 ** 0.5 / 4
        ], [
            x - l * 3 / 4,
            y + l * 3 ** 0.5 / 4
        ]]
        return k == -1 ? beforePoints : k == 0 ? [points[0]] : points;
    }

    function drawTriangle(x, y, l) {
        ctx.beginPath();
        ctx.moveTo(x, y);
        ctx.lineTo(x - l, y);
        ctx.lineTo(x - l / 2, y + (l * 3 ** 0.5 / 2)*(k==-1?-1:1));
        ctx.closePath();
        ctx.strokeStyle = "black";
        ctx.stroke();
    }

+ // setTimeoutに変更
    function drawFrame() {
        beforePoints = beforePoints.reduce((v, w) => {
            return v.concat(calcKeyPoints(w[0], w[1], beforeLength));
        }, []);
        beforeLength /= 2;
        beforePoints.forEach(v => drawTriangle(v[0], v[1], beforeLength));
+       if (k++ < MAX) {
+         setTimeout(drawFrame, 1000);
+       }
    }
    drawFrame()
</script>

最初の大元の三角形のためにk=-1を無理やり描画していますが
始点の計算と、三角形描画の順番を入れ替えれば

        return k == -1 ? beforePoints : k == 0 ? [points[0]] : points;

ここの分岐が一つ減るかと思いますが、ちょっと頭がこんがらがるので特にいじってません。
もしかするとこのあたり、そもそものアルゴリズムの改善ができるかもしれません。
なんの参考文献も見ずに適当に遊んだだけなので許してください

ショートハンド

最後にもっとショートハンドを使用して、できる限り圧縮します。
・html idの省略
・functionをアロー関数に
・命名、変数宣言を圧縮
・全てdrawFrame関数内に入れることで引数lを排除
・-1である判定をビット反転演算に
・0である判定をイコール使わないように
・withでctxをまとめた
・文字列代入をバッククォートで省略
・スプレッド構文と分割代入で配列を連結、引数を渡す
・ifを短絡演算に
等を行います。

また、strokeStyle未指定でも黒い線を引けたので削除したり、
計算上、変数宣言すれば文字数を削れる部分等を削ります。

結構面影が残っていて解読しやすいです。

追記
@htsign さんよりコメントでご指摘いただきました。ありがとうございます！
mapの引数、reduceをflatMapに修正しました。

<canvas id=C>
<script>
    f = () => {
        R = n * 3 ** .5 / 4, // 使いまわせるので定数にした
// 始点を求めたのち、reduceで一つの配列にしていたが
-       c = ([x, y]) => {
-           t = [[x - n / 4, y - R], [x + n / 4, y + R], [x - n * 3 / 4, y + R]];
-           return ~k ? k ? t : [t[0]] : p
-       },
-       p = p.reduce((v, w) => [...v, ...c(...w)], []),
// flatMapを用いることで簡略した
+       p = p.flatMap(([x, y]) => {
+           t = [[x - n / 4, y - R], [x + n / 4, y + R], [x - n * 3 / 4, y + R]];
+           return ~k ? k ? t : [t[0]] : p
+       }),
        n /= 2;
// 引数を配列で宣言することで受け渡しを省略する
-       p.map(v => {
-           [x, y] = v;
+       p.map(([x, y]) => {
            with (C.getContext`2d`) {
                beginPath();
                moveTo(x, y);
                lineTo(x - n, y);
                lineTo(x - n / 2, y + (~k ? R : -R));
                closePath();
                stroke()
            }
        });
        k++ < M && setTimeout(f, a)
    };
    f(M = 6, k = -1, p = [[C.width = C.height = a = 1e3, a]], n = a * 2)
</script>

完成系.html

<canvas id=C>
<script>
    f = () => {
        R = n * 3 ** .5 / 4,
        p = p.flatMap(([x, y]) => {
            t = [[x - n / 4, y - R], [x + n / 4, y + R], [x - n * 3 / 4, y + R]];
            return ~k ? k ? t : [t[0]] : p
        }),
        n /= 2;
        p.map(([x, y]) => {
            with (C.getContext`2d`) {
                beginPath();
                moveTo(x, y);
                lineTo(x - n, y);
                lineTo(x - n / 2, y + (~k ? R : -R));
                closePath();
                stroke()
            }
        });
        k++ < M && setTimeout(f, a)
    };
    f(M = 6, k = -1, p = [[C.width = C.height = a = 1e3, a]], n = a * 2)
</script>

消せる空白と改行を消すと
79文字で、5行になりました。

<canvas id=C><script>f=()=>{R=n*3**.5/4,p=p.flatMap(([x,y])=>{t=[[x-n/4,y-R],[x
+n/4,y+R],[x-n*3/4,y+R]];return ~k?k?t:[t[0]]:p}),n/=2;p.map(([x,y])=>{with(C.g
etContext`2d`){beginPath();moveTo(x,y);lineTo(x-n,y);lineTo(x-n/2,y+(~k?R:-R));
closePath();stroke()}});k++<M&&setTimeout(f,a)};f(M=6,k=-1,p=[[C.width=C.height
=a=1e3,a]],n=a*2)</script>

いったん7行以下で抑えられたし、良しとしましょう。

ゴルファー御用達のfor(;;)を使えていないので
reduceやmapをもっと工夫できそうな気がして以下を考えてみました。

もし仮にfor-ofでも変数宣言を複数できれば

for(p=p.reduce((v,w)=>[...v,...c(...w)],[]),n/=2,v of p)d(...v);
k++<M&&setTimeout(f,a)

とか妄想しましたが、ループ数でなく配列全てでのループならやはりmapを用いた方が文字数が少ないようです。

※ショートハンドに興味が湧いた方はこちらがまとまっていて良いのでどうぞ

最後に

圧縮したコードでcodepenにしてみました。（これも0.25xをおしてください！）

See the Pen GOLF_SierpinskiGasket by serna37 (@serna37) on CodePen.

また、前述の6行の頭にdata:text/html,をつけて、DATA URLとしたものがこちらです。
(ブラウザで見てからコピべしたのでURLエンコードされてますが。)

data:text/html,<canvas id=C><script>f=()=>{R=n*3**.5/4,p=p.flatMap(([x,y])=>{t=[[x-n/4,y-R],[x+n/4,y+R],[x-n*3/4,y+R]];return ~k?k?t:[t[0]]:p}),n/=2;p.map(([x,y])=%3E{with(C.getContext`2d`){beginPath();moveTo(x,y);lineTo(x-n,y);lineTo(x-n/2,y+(~k?R:-R));closePath();stroke()}});k++%3CM&&setTimeout(f,a)};f(M=6,k=-1,p=[[C.width=C.height=a=1e3,a]],n=a*2)%3C/script%3E

これをブラウザのURLとしてコピペすれば、わざわざhtmlファイルを作成しなくても描画が見られて面白いです。

変数MAX(またはM)を変えるとどこまで描画するかが、
setTimeoutの第二引数を変えると描画スピードが変わりますので
上記のcodepenやDATAURLにてお試しあれ。

以下はM=9、遅延100での描画。

以上、フラクタル図形をコードゴルフしてみた、でした〜