Chpater3 今天來學習畫一棵樹（IV）淺談效能和演算法，以迭代取代遞迴吧！

2021 iThome 鐵人賽

DAY 18

Modern Web

從零開始打造網頁遊戲－造輪子你也辦的到！系列第 18 篇

13th鐵人賽 javascript 物件導向 (object-oriented，oo) canvas binary tree

jerrythepotato

2021-09-25 23:59:26

1047 瀏覽

分享至

昨天發完文後，覺得對於演算法還是心有不甘，便上網搜尋了一下，雖然沒直接給到答案，間接的給了我一些大膽的想法。

具體參考的是這篇：
https://ithelp.ithome.com.tw/articles/10231115
而當下的我了一個很草率的結論：迭代的效能比遞迴好

說回迭代(for)

在樹的開篇有提到使用遞迴的原因是一般的迴圈做不出樹狀結構，但是效能上卻有瓶頸，接著我就意識到，先前的作法根本是「為了遞迴而遞迴」，我們只是需要透過樹狀結構來指定父子關係，那為什麼每次更新（渲染繪圖）的時候都還要跑遞迴呢？

因此我的思路是，把需要遞迴的放在建構式裡面，其他則透過跑迴圈的方式，於是，簡化了一開始的流程，分別只對樹根Tree進行定位，對於樹枝Stick只提供長度跟角度，接著在這個過程中把樹狀圖給扁平化，把眾樹枝們放到treeNodes裡面。

let treeNodes = [];
let Tree = function(x, y, r, theta, times){
    treeNodes = [this];
    this.startX = x;
    this.startY = y;
    this.endX = x + r * Math.cos(theta / 180 * Math.PI);
    this.endY = y + r * Math.sin(theta / 180 * Math.PI);
    this.r = r;
    this.theta = theta;
    this.grow = 0;
    let shrink = 0.65 + random(0.1);
    let diff = random(0.3) - 0.15; // +-0.15
    this.son = [new Stick(this, (shrink - diff), 30 * (a+b+1), times - 1),
                new Stick(this, (shrink + diff), 30 * (a-b-1), times - 1)];
}
let Stick = function(father, shrink_diff, angleOffset, times){

    this.father = father;
    this.r = this.father.r * (shrink_diff);
    this.theta = this.father.theta + angleOffset;
    this.grow = 0;
    treeNodes.push(this);
    if(times > 0){
        let shrink = 0.65 + random(0.1);
        let diff = random(0.3) - 0.15; // +-0.15
        this.son = [new Stick(this, (shrink - diff), 30 * (a+b+1), times - 1),
                    new Stick(this, (shrink + diff), 30 * (a-b-1), times - 1)];
    }
}

於是，在物件實例化的過程中，我們就拿到了treeNodes

裡面有三處標記，說明一下：

treeNodes[0]是一開始放進去的Tree物件

Tree有兩節子樹枝，其中一枝和它後面2^9的子子孫孫都會排序其後

右下角顯示該樹枝沒有子代，表示到treeNodes[10]實際上已經遞迴10次

然後就可以把每一偵都要跑的，原本遞迴寫法Transform和Draw通通改成for迴圈，這邊和之前主要的差異在於，之前要用this，現在用node = treeNodes[N]，和判斷樹枝在左側或右側。

Tree.prototype.Transform = function(){
    let a = myMouse.pointX;
    let b = myMouse.pointY;
    for(let N = 1; N < treeNodes.length; N++){
        let node = treeNodes[N];
        let index = node.father.son.indexOf(node);
        let parameter = ((index == 0)?(a+b+1):(a-b-1));
        // if(index == 0) console.log(0);
        // else console.log(1);
        node.theta = node.father.theta + 30 * parameter;
        // 已知father, r, theta 三個參數，透過father取得座標後進行計算
        let x = node.father.endX;
        let y = node.father.endY;
        let r = node.r;
        let theta = node.theta;
        node.startX = x;
        node.startY = y;
        node.endX = x + r * Math.cos(theta / 180 * Math.PI);
        node.endY = y + r * Math.sin(theta / 180 * Math.PI);
    }
};
Tree.prototype.Draw = function(){
    for(let N = 1; N < treeNodes.length; N++){
        let node = treeNodes[N];
        let x = (node.startX - WIDTH/2) * node.grow + WIDTH/2,
            y = (node.startY - HEIGHT)* node.grow + HEIGHT,
            r = node.r * node.grow,
            theta = node.theta;
            
        context.beginPath();
        context.moveTo(x, y);
        context.lineTo(x + r * Math.cos(theta / 180 * Math.PI),
                       y + r * Math.sin(theta / 180 * Math.PI));
        context.lineWidth = 1 + r/50;
        context.strokeStyle = 'rgba(179, 198, 213, 1)';
        context.stroke();
        
        node.grow = Math.min(node.grow + 0.01 / (0.8 + 2 * node.grow), 1);
    }
};