遊戲中把敵人打到戰鬥不能後，敵人不是會噴血、噴錢、噴道具嗎？那同學們知道這些噴出來的東西，在程式中是怎麼選擇降落的位置嗎？該不會以為是亂數隨便選一選的吧！

其實小哈也不知道其他人是怎麼做的，但是小哈自己有一套方法來幫助遊戲選擇比較好的噴錢、噴道具的位置。

漩渦式搜索法

今天要和大家分享的，是一個在格狀地圖，從中心點開始，以漩渦的方式由內向外遍歷周圍格子的演算法。

仔細跟隨上圖中的漩渦式搜索，就可以觀察到這個搜索進程是有規律的。

• 往前一步 ➜ 轉 ➜ 往前一步 ➜ 轉
• 往前兩步 ➜ 轉 ➜ 往前兩步 ➜ 轉
• 往前三步 ➜ 轉 ➜ 往三兩步 ➜ 轉
• 往前四步 ➜ 轉 ➜ 往前四步 ➜ 轉
• 往前五步 ➜ 轉 ➜ 往前五步 ➜ 轉

我們試著把這個規律轉變為程式的邏輯。

1. 定義ｎ=１、定義始初方向、定義轉向角度θ（順時針 90°, 逆時針 -90°）
2. （ 往前走(ｎ步) ➜ 轉向θ ）x 兩次
3. ｎ=ｎ＋１
4. 回步驟２

程式碼實作

在進入演算法的程式碼之前，要先寫一個將向量轉向90度的函式。這裏會用到向量的旋轉公式，不熟的同學可以回去複習《Trick 10: 向量的旋轉原來要歪看正著》。

一個向量(x, y)旋轉θ角度後成為(x', y')的計算公式：

在θ等於９０度（順時針）或負９０度（逆時針）時，這個計算的公式可以大幅簡化。因為cos(90°)與cos(-90°)都等於０，加上sin(90°)=1且sin(-90°)=-1，所以公式可以簡化為：

• 順時針旋轉後的座標(x', y') = (-y, x)
• 逆時針旋轉後的座標(x', y') = (y, -x)

/** 將向量旋轉90度的函式 */
function rotateVector(vector: Point, clockwise: boolean) {
    if (clockwise) {
        vector.set(-vector.y, vector.x); // 順時針
    } else {
        vector.set(vector.y, -vector.x); // 逆時針
    }
}

接著就可以來寫演算法的類別了。

/** 漩渦式搜索演算法 */
class SwirlPath {
    // n: 向前幾步
    n = 1;
    // 前進方向（預設朝右方）
    direction = new Point(1, 0);
    // 順時針旋轉
    clockwise = true;
    // 自上次n+1之後轉了幾次
    turnIndex = 0;
    // 自上次轉向後前進了幾步
    moveIndex = 0;
    // 目前所在格子
    currentLoc: Point;

    /** 建構子，需要知道從哪一點開始 */
    constructor(center: Point) {
        // 複制成目前位置
        this.currentLoc = center.clone();
    }

    /** 計算出下一點的位置 */
    nextLoc(): Point {
        // 依照前進方向往前一格就是下一步的位置
        this.currentLoc = this.currentLoc.add(this.direction);
        // 記錄我們剛剛向前走一步了
        this.moveIndex++;
        // 如果目前方向已前進了n步
        if (this.moveIndex == this.n) {
            // 轉向
            rotateVector(this.direction, this.clockwise);
            // 記錄轉向次數增加1
            this.turnIndex++;
            // 重置前進步數，因為轉向了
            this.moveIndex = 0;
            // 如果轉向兩次
            if (this.turnIndex == 2) {
                // n要加1
                this.n += 1;
                // 重置轉向次數
                this.turnIndex = 0;
            }
        }
        // 回傳目前所在格子
        return this.currentLoc;
    }
    
    /** 計算接下來amount個點的位置 */
    nextLocs(amount: number): Point[] {
        // 建立結果路徑，先將目前位置放在開頭
        let result = [this.currentLoc];
        for (let i = 0; i < amount; i++) {
            // 取下個位置放在路徑的最後
            result.push(this.nextLoc());
        }
        // 回傳結果路徑
        return result;
    }
}

使用漩渦式地圖搜索演算法，可以很方便地由近而遠點取得地圖上某處周圍的格子。這個類別的使用方法大致如下：

// 從哪出發
let start = new Point(0, 0);
// 建立演算法
let swirlPath = new SwirlPath(start);
// 取出之後的１００個點
let result = swirlPath.nextLocs(100);

CG示範專案

在遊戲中可以這樣使用：

1. 當人物戰鬥不能後，發現他身上有兩個武器外加三枚金幣要丟到地上。
2. 以漩渦式地圖搜索法，找出離人物最近的１０個格子。
3. 從１０個格子裏隨機取出５格來丟武器和金幣。
4. 如果因為周圍的牆壁、大石等無法丟東西的格子太多，找不到５格來丟東西。
5. 繼續以漩渦式地圖搜索法，找出下１０個格子，直到武器與金幣都找到能安置它們的地方。

當然，演算法的使用時機端看遊戲設計者的巧思，這裏只是簡單提供一個使用情境給同學們參考。

今天的示範演示了如何將我們平常觀察到的規律，以程式設計的思路轉換為程式碼，希望能帶給同學們更多創作的靈感。