Trick 8: 狙擊槍的彈著點是在哈囉？

14th鐵人賽 typescript 演算法遊戲開發 javascript

小哈片刻

2022-09-11 02:47:22

1743 瀏覽

相信就算沒玩過射擊遊戲的同學，也多少看過別人玩Counter Strike或Call of Duty之類的遊戲吧。在類似的槍戰遊戲中都會出現射擊瞄準用的準星。
3D準星
一般準星是使用一個圓形來表示，當玩家射擊時，系統會從這個圓形的範圍裏隨機取一個點來當作子彈實際會穿過的目標，並以此計算彈道。
光暈準星
國內著名的(?!)2D射擊遊戲《光暈戰記》也採用了類似的準星概念，藉由調整準星的半徑長度，來控制不同槍枝的射擊準度。
圓內特效
不只射擊遊戲，還有許多地方也會遇到圓內隨機取點的問題，比如在上圖的遊戲中，騎士正施展著一個圓形範圍的魔法，魔法劍特效會特續從圓內的魔法範圍中升起，如果無法均勻地在其中隨機選擇魔法劍出現的位置，那麼這個特效播放起來可就遜掉了。

剔除法

單純使用Math.random()能在一條數線上的某個範圍內均勻地隨機擇點，那麼用上兩個Math.random()，就能在矩形內均勻地隨機取點，方式如下，

function getRandomInRectangle(rect: Rectangle): Point {
    let point = new Point(
        rect.x + Math.random() * rect.width,  // 在寬的範圍內隨機取點
        rect.y + Math.random() * rect.height, // 在高的範圍內隨機取點
    );
    return point;
}

既然我們知道如何在一個矩形內均勻取點，那麼是不是就能在圓形的外面畫一個剛好把圓圍起來的正方形，然後在正方形裏均勻地隨機取點，把這個點當成是圓內的隨機取點，如果取到的點不小心跑到了圓的外面，那麼再重新取一次就得了。
方圍圓
沒錯，這就是一般程式最常用的剔除法。

/** 以剔除法在圓內隨機取點, 參數為圓心與半徑 */
function getRandomInCircle_filter(center: Point, radius: number): Point {
    // 先找到剛好圍住圓的正方形
    let square = new Rectangle(
                        center.x - radius, // x
                        center.y - radius, // y
                        radius * 2,        // width
                        radius * 2         // height
                 );
    // 以while迴圈持續取點
    while(true) {
        // 在正方形裏隨機取點
        let point = getRandomInRectangle(square);
        // 如果取得的點在圓的範圍內，就回傳這個點
        if(Point.distance(point, center) < radius) {
            return point;
        }
        // 否則就回到loop裏，繼續下一次的隨機取點
    }
}

這個方式比較糟糕的問題在於，正方形和圓形的面積比4:3.14，約為1.3倍，所以平均下來，每次取點需要迴圈跑1.3次才能得到一個位於範圍內的點，浪費的時間以比例來說其實蠻多的。第二個糟糕的地方在於，每次取點耗費的時間不一定，有時運氣好可能在迴圈的第一次就得到範圍內的結果，有時卻可能要花上十多次，導至程式運行效率不穩定。

所以大家準備好，我們要改用一個比較帥的方法了。

極座標法

平面上的點通常是以一組x,y的座標來表示，不過其實還有另一種表示方法，極座標系統(Polar coordinate system)。

和x,y平面座標類似，極座標系統也是由兩個數字來表示一個位置，一個是和x軸的夾角θ(theta)，一個是離原點的距離length。

將極座標轉換成x,y座標的方法也很簡單，

/** 將極座標轉換成x,y座標的函式，參數依序是
 * length: 距離原心的距離
 * angle: 和x軸的夾角（以弧度表示）
 */
function polarToXY(length: number, angle: number): Point {
    return new Point(
        Math.cos(angle) * length, // x值
        Math.sin(angle) * length  // y值
    );
}

關於上面程式使用的Math.sin()和Math.cos()都是三角函數的範疇。
三角函數是遊戲中非常常用的工具，在往後幾日的文章中會再詳加解釋。

有了極座標和xy座標的轉換公式，那我們不就可以把原本用來產生x,y的兩個亂數，改成距離和夾角，用這兩個參數在極座標上隨機取點，再轉換回x,y座標。

這個想法很棒吧，我們把它寫下來。

function getRandomInCircle_polar(center: Point, radius: number): Point {
    /** 首先產生極座標的兩個參數
     * length要介於0到radius（隨機取一個距離）
     * angle要介於0到2π（隨機取一個角度）
     */
    let length = Math.random() * radius;
    let angle = Math.random() * 2 * Math.PI;
    // 然後將極座標轉成xy座標的Point
    let point = polarToXY(length, angle);
    // 然後再把點平移到以center為圓心
    point.x += center.x;
    point.y += center.y;
    // 最後把這個point傳出去就行了
    return point;
}

用這個方法取得的點，一定會落在圓的範圍內，畢竟polarToXY的第一個參數就是離圓心的距離了嘛，只要離圓心的距離控制在半徑以下，選出來的點就不可能跑到圓的外面去。

我們看看示範程式使用兩種不同的方法各選出兩千個點的結果，比較一下剔除法（藍）與極座標法（紅）選出來的點的密度。
比較剔除法與極座標法

各位應該發現極座標選點的問題了吧！用它選出來的兩千個點密度不平均，比較多集中在圓心，越靠圓周密度越稀。會出現這樣的結果是因為我們用了平均分配的亂數去取極座標的距離，但是在圓形中距離圓心越遠的地方涵蓋的面積越大，所以理論上在選距離的時候，離圓心越遠的距離，被選到的機率要越高才對。

我們再推論一下，距離和面積的比例關係是什麼？沒錯，面積應該和距離的平方成正比，反過來說，距離就應該要和面積的平方根成正比，所以我們在用亂數取距離的時候，只要先把介於０到１的亂數開個根號，這個亂數就會有比較大的機率靠向１，再把他乘以最大距離就會比較容易選到靠邊的區域，如此一來取點的比例就會平衡了。

/** 比較好的極座標隨機取點函式 */
function getRandomInCircle_polar_better(center: Point, radius: number): Point {
    /** 首先產生極座標的兩個參數
     * length要介於0到radius, 亂數要先開根號: Math.sqrt()
     * angle要介於0到2π
     */
    let length = Math.sqrt(Math.random()) * radius;
    let angle = Math.random() * 2 * Math.PI;
    // 然後將極座標轉成xy座標的Point
    let point = polarToXY(length, angle);
    // 然後再把點平移到以center為圓心
    point.x += center.x;
    point.y += center.y;
    // 最後把這個point傳出去就行了
    return point;
}

最後來看看以上三種方法各產生兩千個點的結果吧。
三種圓中取點法的比較