搵路 (電腦)

**搵路**（參見）係指運用電腦程式搵出兩點之間最短嗰條可能路線。用嚟做搵路嘅演算法會攞以下呢三樣嘢做輸入：表示移動空間嘅圖、起點以及終點；然後個演算法就需要計出一條由起點去終點嘅路線。

典型嘅搵路演算法通常會同另外兩個特定嘅演算法一齊用：一方面，搵路演算法一般唔能夠直接對要探索嘅環境作出運算，而係要靠另外一個演算法 `simp`，`simp` 要以個環境嘅地圖做輸入，將幅地圖抽象化，變成圖論式嘅**圖**做輸出，等個搵路演算法用呢幅圖做輸入；另一方面，因為搵路演算法做嘅只係搵條路線出嚟，所以喺搵路演算法行完之後，個程式要將條路線交俾另一個演算法，教個人工智能移動 `follow`，等 `follow` 教部電腦執行**沿條路線移動**呢個動作。

用嚟做搵路嘅演算法有好多實用價值：例如係喺機械人學上教機械人喺自己周圍嘅空間當中搵出要行嘅路線，以及係喺遊戲製作上教遊戲 AI 控制啲 NPC 喺遊戲空間入面搵出要行嘅路線呀噉，都要用到搵路演算法。

## 輸入

搵路演算法用起上嚟通常要配以將環境轉化成圖嘅演算法：喺實際應用上，搵路演算法通常唔曉直接處理環境，而係要靠第個演算法（以下叫 `simp`）－`simp` 要將個環境變成一幅圖。圖論定義上嘅「圖」係一個數學結構；一幅噉嘅圖會
*若干個**節點**，並且
*指明邊啲節點之間有連結；
喺應用上，一個可能嘅做法係以數字（成一個陣列）表示幅圖，輸入最先嗰個數字代表節點嘅數量，跟住嘅數字表示邊啲節點之間有連結，例：用陣列 `[6, 1-2, 1-5, 2-5, 2-3, 5-4, 3-4, 4-6]` 表示個圖有 6 個節點，節點 1 同節點 2 之間有連結（可以由節點 1 行去節點 2 或者相反）、節點 1 同節點 5 之間有連結（可以由節點 1 行去節點 5 或者相反）... 如此類推；`simp` 要做嘅嘢係攞要探索嗰個環境做 `input`，俾出一個噉嘅陣列做 `output` 表示個環境當中有邊啲重要位置（節點）同邊啲位置之間有路能夠互通（連結）嘅圖，再將呢個 `output` 交俾個搵路演算法。
### 分區做法
喺實際應用上，表示環境嘅圖通常會將個環境分拆做數量相對少嘅幾個區域。舉個例說明，想像一隻電子遊戲，隻遊戲嘅虛擬世界係 10,000 個單位長、40,000 個單位闊嘅四方形，有成 10,000 × 40,000 咁多個可能位置，而如果部電腦要計晒咁多個可能位置會好吃力；不過呢個虛擬世界可以分割做六大區域，而每個區域下又有得細分，於是個遊戲程式可以用分層式嘅做法，先睇吓要郁嗰個個體要由邊個區去邊個區，然後忽略唔使考慮嗰啲區域－運算起上嚟就輕鬆好多。

### 權重表
電子遊戲用嘅搵路演算法通常仲會有一個**權重表**，意思即係話個表每條連結都會有個數值，表示嗰條路線嘅**成本**：例如有個負責整圖嘅演算法會每條路俾個權重值佢，個數值愈大表示條路愈難行（成本高）；想像其中兩個節點之間有兩條可能路線 `a` 同 `b`，`a` 係一條完全冇機關嘅平路，而 `b` 長過 `a` 之餘仲有十個陷阱設咗喺度，噉正路嚟講，假設 `a` 同 `b` 喺其他因素上完全相等，`b` 嘅權重值理應會大過 `a` 嘅。

喺電子遊戲嘅搵路當中，仲有好多變數能夠影響搵路嘅權重。例如 AI 角色本身嘅特性亦都可能會影響佢嘅搵路權重：想像有隻戰略遊戲，玩家旗下嘅軍隊有兩種單位－步兵同偵察兵，當中偵察兵有特殊能力，令佢哋行起崎嶇不平嘅路嗰陣快啲。噉對於由 AI 控制嘅偵察兵嚟講，**條路嘅平坦程度**對佢哋路線權重嘅影響理應會冇咁大。

## A* 搜尋

A* 搜尋演算法係最原始嗰種搵路演算法，喺廿世紀同廿一世紀初成日俾人用嚟教電子遊戲人工智能控制 NPC 喺遊戲世界入面移動：一隻電子遊戲嘅虛擬世界可以想像成二維嘅平面，個平面會有若干個可以去嘅地點，地點之間有路線，而因為遊戲世界會有障礙物，某啲地點之間嘅空間會唔能夠通行。A* 搜尋演算法嘅做法係將個空間當做一幅有若干個節點嘅圖，喺每一步，個演算法會
*Foreach 相鄰點（可以由自己位置移去嘅地點）計嗰個相鄰點嘅 f 值；f 表示**成本**（即係行去嗰點要嘥幾多時間精神等資源），數值係 g 同 h 嘅總和；
*g 表示由現時點去嗰個相鄰點要用嘅移動成本（時間同氣力等），呢個數值可以由現時點同目標點之間嘅路線嘅特性（有幾崎嶇等）估計；
*h 係按某啲啟發法估計嘅「由嗰個相鄰點去最終點嘅成本」－例如如果終點喺山頂，而望緊嗰個相鄰點位置低過現時點，按「盡可能喺高度上接近最終點」嘅啟發法，望緊嗰個相鄰點就會有高嘅 h 值；
然後個演算法會揀 f 值最低嗰點做下一個要去嘅點，唔好去經已去過嘅點，並且一路重複做上述嘅嘢，順利嘅話就會一路做到到達終點為止。A* 搜尋演算法仲可以狹義化，變成迪卡斯特拉演算法：迪卡斯特拉演算法係指 h 永遠等如 0 嘅 A* 搜尋演算法，即係話迪卡斯特拉演算法唔會嘗試估下一點有幾有利於最後去到終點。

A* 搜尋演算法可以用噉嘅虛擬碼表示：
  初始化
  個程式有兩個 list，**開放表**（open list）同**封閉表**（closed list）；
    *// 開放表表示未去過嘅點，而封閉表表示去咗嘅點。*
  將起點擺入去 open list；
  While open list 唔係空嘅，做...
    搵 open list 當中 f 值最低嘅點；
    將呢點變做現時點；
    將呢點擺入去 closed list； *// 等個程式唔會返去經已去過嘅點。*
    **Foreach** 由現時點去得到嘅點，
      **if** 嗰點喺 closed list 入面，忽略佢；
      **if** 呢點唔喺 open list 入面，將佢擺入去 open list；
      將現時點設做呢點嘅 parent；
      計呢點嘅 f 值；
      **if** 最終目的地入咗 closed list，終止運作； *// 成功到咗目的地。*
      **if** open list 係空嘅，但又搵唔到目的地嗰點，終止運作； *// 搵路失敗。*
   將個演算法行過嗰條路線俾做 output。

呢個演算法嘅最壞情況複雜度係 `O(E)`，當中 `E` 係幅圖嘅節點間連結嘅數量。
### 計 h

A* 同迪卡斯特拉演算法嘅分別在於 A* 會考慮 h 呢個數值。原則上，h 可以用兩大方法計：
*個演算法可以試吓計 h 嘅精確數值，即係例如考慮晒所有由目標點去終點嘅可能路線，再計出 h 嘅最細可能數值；呢種做法有個明顯嘅缺點－噉做會消耗大量嘅運算資源，而且仲假設咗個演算法有能力鳥瞰噉睇晒成幅地圖同埋事先知道晒每條路線嘅成本值。所以
*喺實際應用上，h 嘅數值通常會用某啲啟發法估計：啟發法係認知心理學上嘅概念，指人類或者人工智能思考嗰陣可以用嘅「認知捷徑」，即係一啲簡單（唔使做太大量嘅運算）、可以用嚟解難嘅法則，例如家陣個搵路演算法要由喺山腳嘅起點行去喺山頂嘅終點，一個可能嘅啟發法就可以係「盡可能行去高嘅點」（h 嘅數值同望緊嗰點嘅高度成反比）。A* 演算法有多種啟發法可以用嚟估計 h 嘅數值，多數係靠計終點同望緊嗰點之間嘅距離，而「距離」嘅計法有幾種：
**曼哈頓距離：想像兩個點之間嘅空間用格仔嚟代表，而假設一個個體淨係有得沿住啲格仔嘅邊線行（好似係喺曼哈頓揸車搵食嘅的士司機噉）嘅話，噉喺是但兩點（設呢兩點做 p 同 q）之間穿梭都會有多條「最短路線」，呢啲路線嘅長度就係所謂嘅曼哈頓距離。喺二維空間嘅情況下，曼哈頓距離計法如下：
**:\text{MD} = | p_x - q_x | + | p_y - q_y |；當中 p_x 係指 p 嘅 x 座標值、p_y 係指 p 嘅 y 座標值... 如此類推。
**棋盤距離：指兩點之間最大座標差異，兩點之間嘅棋盤距離係指將兩點嘅同位座標相減（兩點嘅 x 座標相減、兩點嘅 y 座標相減... 等等）所得嘅最大數值，條式如下：
**:D_{c}(p,q) := \max_i(|p_i -q_i|)
**歐幾里得距離：指兩點之間嘅直線距離，二維嘅歐幾里得距離計法如下：
**:d(p,q)=\sqrt{(p_x-q_x)^2 +(p_y-q_y)^2}

### 任何角度

Theta* 係進階版嘅 A* 搜尋演算法，特徵係曉靠自己檢查現時位置周圍嘅點（睇埋任何角度路線計劃）：Theta* 嘅主要過程同 A* 一樣，不過喺每次睇周圍節點嗰陣，唔淨只會睇同現時點 par(s) 有連繫嘅節點，而係睇晒所有由 par(s) 望得到嘅點，而如果有個點 s' 係由 par(s) 望得到嘅，噉個演算法有可能會選擇由 par(s) 直接移去 s'－就算 par(s) 同 s' 之間冇直接嘅連繫都一樣。即係話：
  ... *// 其餘部份同一般嘅 A* 一樣。*
  **Foreach** 由現時點去得到嘅點，
    **if** 嗰點喺 closed list 入面，忽略佢；
    **if** 呢點唔喺 open list 入面，將佢擺入去 open list；
    **Update vertex** *// 呢個[[子程序]]係 theta* 同 A* 嘅分別；簡單講係睇勻周圍嘅望得到嘅點，揀成本最低嗰個，然後再由現時點直接畫條路去嗰度。*
    將現時點設做呢點嘅 parent；
    計呢點嘅 f 值；
  ...

## 進階技術
### 幅度同深度

幅度優先搜尋同深度優先搜尋係搜尋演算法上兩個相關嘅概念。幅度優先搜尋係先入先出嘅，喺開始做搜尋嗰陣，會睇晒所有「下一個可能去嘅點」先，然後再睇下一列可能地點－「以幅度廣為先」；深度優先搜尋就係用後入先出嘅，會先攞一個點，然後集中睇嗰點之後嘅可能點－「以深度高為先」。對搵路嘅演算法研究會思考「幅度優先同深度優先分別擅長喺邊啲情況下搵出總成本低嘅路線」，並且按情況揀啱用啲嗰種做法。

喺實用上，幅度優先搜尋同深度優先搜尋嘅演算法都會有某啲可調節嘅參數：例如深度優先搜尋嘅演算法通常會掕住個數值 d，表示「搜尋深度」，例如 d = 3 就表示「喺一個可能點後嘅點嗰陣，頂櫳耖三層，先去耖另一個可能點後嘅點」－例如係教電子遊戲人工智能幫啲 NPC 搵路噉，喺某啲遊戲入面，遊戲嘅虛擬世界可以大得好交關（可以睇開放世界遊戲），即係每個可能點後面都有大量嘅地點，如果吓吓都要耖晒一個可能點後嘅點（d = \infty），部電腦會唔夠運算資源幫啲 NPC 會及時搵到路，唔能夠做到令玩家有真實感嘅世界。

### 多個體搵路
多個體搵路演算法係指幫多個個體喺一個環境入面搵出每個個體要行嘅路線，同時確保啲個體之間唔會相撞同埋將成本函數最佳化（將成本減到最低）－成本可以用（例如）「個體嘅路線長度總和」嚟衡量；多個體搵路要應付「要用嘅運算資源隨個體數量激增」等嘅問題。

喺現實應用上，多個體搵路演算法通常會將啲個體分做若干組－例如有隻射擊遊戲，由電腦控制嘅敵軍有 24 個士兵，而呢柞士兵可以分做 6 個小隊，一個小隊嘅成員會群體同步移動，即係用同一條路線，令到個搵路過程由「搵 24 條路」變成（消耗嘅運算資源比較少嘅）「搵 6 條路」，然後再有進一步嘅演算法，教每個體要同條路線成點嘅關係，例如小隊有個隱形（玩家睇唔到）嘅中心點，而每個士兵喺個小隊移動嗰陣，要確保自己一路都喺小隊中心點嘅 `-10 + (x * 5)` 咁遠嘅位置，當中 `x` 係佢係小隊入面第幾個士兵。
## 睇埋
*Google 地圖
*衞星導航系統
*解迷宮演算法
*運動規劃
*導航網格
*遊戲人工智能
*個體為本模型

## 文獻

*Abd Algfoor, Z., Sunar, M. S., & Kolivand, H. (2015). A comprehensive study on pathfinding techniques for robotics and video games (PDF). *International Journal of Computer Games Technology*, 11 pages.
*S. Koenig & M. Likhache. Incremental A* (PDF).
*S. Koenig & M. Likhache (2002). D* Lite (PDF).

## 註釋

## 歐詞

## 引咗

## 拎

* 清楚、視覺化嘅 A* 解釋 
* A* 嘅變種版：分層 A* 搵路 (HPA*)
* Smart Move：有智能嘅搵路，Gamasutra