万维百科粤语版

搵路演算法

(由搵路演算法跳轉過來)
Jump to search
而家要由 A 點去 B 點,一個設計得好嘅搵路演算法能夠搵出一條路線。

搵路粵拼wan2 lou6英文pathfinding / pathing)係指運用電腦程式嚟搵出兩點之間最短嗰條可能路線嘅技術。一個用嚟做搵路嘅演算法會攞以下呢幾樣嘢做輸入(input[1][2]

  1. 一幅表示移動空間嘅(graph)、
  2. 起點、以及
  3. 終點,

然後個演算法就需要計出一條由起點去終點嘅路線(output)。用嚟做搵路嘅演算法有好多實用價值,例如係喺機械人學上教機械人探索自己周圍嘅空間,以及喺遊戲製作上教遊戲人工智能控制啲 NPC 喺遊戲空間入面搵出要行嘅路線[3][4]

一個搵路演算法用起上嚟通常會配以第個將環境轉化成圖嘅演算法:喺實際應用上,搵路演算法通常唔會直接處理一個環境,而係靠第個演算法(以下叫 simplify),將個環境變成一幅(graph);圖論(graph theory)當中嘅一幅圖會有若干個節點(node),並且指明邊啲節點之間有連結,通常做法係個輸入最先嗰個數字代表節點嘅數量,跟住嘅數字表示邊啲節點之間有連結,例如 [6, 1-2, 1-5, 2-5, 2-3, 5-4, 3-4, 4-6] 表示個圖有 6 個節點,節點 1 同節點 2 之間有連結(可以由節點 1 行去節點 2 或者相反)、節點 1 同節點 5 之間有連結(可以由節點 1 行去節點 5 或者相反)... 如此類推;simplify 要做嘅嘢係攞要探索嗰個環境做 input,俾出一個 output 表示個環境當中有邊啲重要位置(節點)同邊啲位置之間有路能夠互通(連結)嘅圖,再將呢個 output 交俾搵路演算法[1][5]

輸入

一幅圖論當中嘅圖;通常一個搵路演算法會用呢啲圖做輸入。
睇埋:圖論

一般嚟講,一個搵路演算法會以一幅抽象化嘅圖作為 input。喺圖論(graph theory)上,一幅圖論定義上嘅(graph)係一個數學結構;一幅圖會有

  • 若干個節點(node),並且
  • 指明邊啲節點之間有連結[1]

喺應用上,一個可能嘅做法係以一柞數字表示幅圖,例如個輸入最先嗰個數字代表節點嘅數量,跟住嘅數字表示邊啲節點之間有連結,例如頭先提到嘅 [6, 1-2, 1-5, 2-5, 2-3, 5-4, 3-4, 4-6] 噉;

電子遊戲入面用嘅搵路演算法通常仲會用一個權重表(weighted graph),意思即係話個表每條連結都會有個數值[註 1],表示嗰條路線嘅「成本」(cost)[6]:例如有個負責整一幅圖嘅演算法會每條路俾個權重值佢,個數值愈大表示條路愈難行(成本高);想像其中兩個節點之間有兩條可能路線 aba 係一條完全冇機關嘅平路,而 b 長過 a 之餘仲有十個陷阱設咗喺度,噉正路嚟講,假設 ab 喺其他因素上完全相等,b 嘅權重值理應會大過 a[註 2][7]

一個權重表;一條路掕住嘅數字表達嗰條路有幾易行[註 3]

註釋

  1. 喺實際應用上,呢啲數值通常一定係 0 或者正數,因為好多常用嘅搵路演算法一撞到負數嘅權重值就會出錯。
  2. 喺實際應用上,一個 AI 角色本身嘅特性亦都可能會影響佢搵路嘅權重。想像有隻戰略遊戲,玩家旗下嘅軍隊有兩種單位:步兵同偵察兵,當中偵察兵有特殊能力,令佢哋行起崎嶇不平嘅路嗰陣快啲。噉對於由 AI 控制嘅偵察兵嚟講,「條路嘅平坦程度」對佢哋路線權重嘅影響會冇咁大。
  3. 有啲演算法仲會精細到考慮埋連結之間嘅方向性:即係有啲路可能淨係可以向其中一個方向通行,又或者由一個方向行嘅成本同由第個方向行嘅唔同。

睇埋

  1. 1.0 1.1 1.2 Millington, I. (2019). AI for Games. CRC Press. Ch. 4.
  2. Hagelback, Johan, and Stefan J. Johansson. "Dealing with fog of war in a real-time strategy game environment." In Computational Intelligence and Games, 2008. CIG'08. IEEE Symposium On, pp. 55-62. IEEE, 2008.
  3. Cui, X., & Shi, H. (2011). A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1), 125-130.
  4. Boyarski, E., Felner, A., Stern, R., Sharon, G., Tolpin, D., Betzalel, O., & Shimony, E. (2015, June). ICBS: improved conflict-based search algorithm for multi-agent pathfinding. In Twenty-Fourth International Joint Conference on Artificial Intelligence.
  5. Pathfinding Algorithms. Medium.
  6. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0. "A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e."
  7. Antsfeld, L., Harabor, D. D., Kilby, P., & Walsh, T. (2012, October). Transit routing on video game maps. In Eighth Artificial Intelligence and Interactive Digital Entertainment Conference.


本页面最后更新于2020-07-08 17:23,点击更新本页查看原网页

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器