Chapter3 今天来学习画一棵树（I）学学人家DOM 自己用递回做一个树状图结构

你是说...树吗?

嘿~丢！铁人赛至今已经过半，实在是油尽灯枯，想不到主题了，刚好看到这两个很赞的树，觉得很适合这次的主题！加上笔者我又对大自然的碎形相当着迷，接下来的游戏就拿种树来做收集养成的要素吧，也该是时候拿第二章聊过的物件来实作了！
https://openprocessing.org/sketch/90192
https://openprocessing.org/sketch/1009781

刚刚洗澡时我稍微构思了一番如何设计，接着读一下人家的程序码，欸！果然逻辑大同小异，来帮萌新们入门一下，这个所谓的递回函式在我国中时可是搞死我了，当时不善於沟通的我，在准备程序竞赛时遇到了一个题目开始学习用递回函式，却不断写错造成无穷回圈，花了五个中午耗时无果，就被电脑老师以为我在偷懒，没写半个题目，被骂了个臭头，今天，就让我们拆分成好几个步骤，以循序渐进的方式打败这个大魔王吧！

何谓递回

简单来说就是，重复的事情一直做，比方说田径校队今天要徵选，共有10人参加，教练说要考验大家的耐力，因此要进行5轮的3000公尺长跑，每一轮会淘汰1人，最後剩下5人入围。

如果要用程序做出这样的竞赛（可以想像成google的奥运游戏），刚开始写程序的人，可能就会很直接地想，那我就准备五个比赛，每次淘汰一人即可，先不说这样要写多久，如果今年报名人数突然暴涨，共有20~30人不等，人数不确定，那怎麽只淘汰到剩五人呢？（也先不说教练有多变态让大家跑3000公尺数十次）

其实答案很简单，就是把重复的最小基本单位给定义出来，在这个例子中就是每一轮的比赛，设计的关键是每次的输入人数都不同，让人数持续减少，因此，也许你已经看过这样的写法：

let people = 10; // 输入10人
race(people);
function race(N){
    // 进行一轮淘汰赛
    N--;
    if(N > 5) race(N);
    else alert('共有' + N + '人入围') // 输出5人
}

递回存在的意义

不过如果仅仅只是这样，肯定会被质疑，用for回圈或是while回圈不是一样能完美解决吗？是的，如果问题的确那麽单纯，进一步想，假设今天教练希望分别招募一队和二队，因此在每一场比赛後将所有人分成AB两组，不淘汰，而让AB两组再分别做竞争，继续分成A-1、A-2、B-1、B-2组，而且每一个组别根据人数不同，有不同的赛式，如果仅剩3人以下，则以1000公尺竞速取胜，剩4人则进行2对2的对抗大队接力，剩5人以上则继续采用3000公尺，那麽事情就不单纯了。

其实这就是树状图的概念，但是要用一般的回圈实现，会遇到的第一个问题就是，那到底有几场比赛需要进行？答案也很单纯：比了才会知道！因此如果有一个函式，能帮我们在比赛进行的当下，依据目前剩下的人数，判断应该采用甲乙丙三种赛事中哪一种，然後在每一个次进行比赛後，分割好两组，并且重复呼叫该函式，就能达到事半功倍的效果了。

树状图

让我们回到画一棵树的主题，前面基於现实的比喻或许还是过於抽象，让我们从一棵树的基本单位开始：树枝，搭配第二章学到的物件，我们可以开始设计一个树枝，它有三个完整的部件：

1. 树枝本身
2. 有父节点（靠近根部）
3. 有子节点（靠近叶子）

先从一个最简单易懂的代码来做演示：如果树枝完全没有分支

let Tree = function(x, y, times){
    // 树枝本身(的属性)
    this.startX = x;
    this.startY = y;
    this.vectorX = 0;
    this.vectorY = -10; // 每一节只有10像素，并且只会向正上方成长
    
    // 根据输入条件判断是否创建新的树枝
    if(times > 0){
        let endX = x + this.vectorX;
        let endY = y + this.vectorY;
        this.son = new Tree(x + vectorX, y + vectorY, times - 1);
    }
    else{
        alert("too many isn't it?"); // 在树枝的最末稍停止递回时，会触发
    }
};
let justAVar = new Tree(10, 10, 100);

其实就跟最一开始举例的3000公尺淘汰赛一样单纯

不过，我们已经透过物件的型式，相当妥善的把每一节树枝接起来了，把以上整段代码贴上console就会看到如下的画面，去点开每一个树枝，都会看到里面又有它的子树枝，一环接一环：

接着我们就可以进一步设计，让每一个树枝都会进行分岔，成为两个长度各只有一半的子树枝，角度分别设定正负30度，并且计算每一树枝的末梢位置endX、endY，用来连结子树枝的起始点startX、startY：

let Tree = function(father, x, y, r, theta, times){
    this.father = father;
    this.startX = x;
    this.startY = y;
    this.r = r;
    this.theta = theta;
    if(times > 0){
        let endX = x + r * Math.cos(theta / 180 * Math.PI);
        let endY = y + r * Math.sin(theta / 180 * Math.PI);
        this.son = [new Tree(this, endX, endY, r / 2, theta - 30, times - 1),
                    new Tree(this, endX, endY, r / 2, theta + 30, times - 1)];
    }
    else{
        // 如果要让末端开花结果，就写在这
    }

    this.Draw = function(x = this.startX, y = this.startY,
                         r = this.r, theta = this.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();
        // 如果有子树枝，就继续呼叫所有的子树枝
        if(this.son) this.son.forEach(branch => branch.Draw()); // 递回
    };
};

接着将物件实例化：
myTree = new Tree(window, WIDTH/2, HEIGHT, HEIGHT/4, -90, 10);

在我们准备好动画框架处写上该物件的绘图方法 myTree.draw()，可以和上面的建构式做对照，这也是属於一个递回函式：

function Redraw(){
    Clear(context);
    myTree.draw();
}

如此一来就能很轻松地画出这颗树了呢！

摁?你说它长得有点丑吗，确实，毕竟，这不是一颗真正的树，明天我们再来美化吧！

顺带一提，可以透过改变角度和长度的比例（上面的例子是30度和1/2），来达到不一样的效果：

有没有曾经在哪里看过很眼熟呢？这个就叫做碎形（又是一个大坑），像是雪花就是典型的碎形了，其不仅呈现出大自然之美，也有着许多值得讨论的地方，有兴趣的朋友可以去找碎形的影片来看，这次系列文就不着墨了！

demo 明天再补上吧！早点睡休息重要

後记

再累还是要後记，原本想用Branch(分支)来命名的，结果脑子一昏就写成Tree(树)，整个很奇怪呀~~怎麽这棵树是由一堆树组成的呢？後来想想算了懒得改了哈哈，说不定Branch是个生词很多人看不懂（自我安慰）。