BSP(Binary Space Partitioning)法とは、壁などの境界を延長して、空間を2分して
行く方法です。3DFPSの原点の一つ(技術的には本当に原点)DOOM(id Software)で
位置解析や、AIのI空間認識、パス探索システムのデータ、などに採用されたことから、Quake シリーズを通して引き継がれています。
http://www.beyond3d.com/content/articles/102/2
http://www.beyond3d.com/images/articles/ingenu-part-2/bsp.png
@ Quake Wars における BSP法
intechweb
http://intechweb.org/
その中でも、
Motion Planning
http://intechweb.org/book.php?id=74&content=title&sid=1
この分野は、これからレベルデザインが複雑化するにつれて、AIのための、
地形情報(世界表現)を生成する上で、欠かすことの出来ない技術分野で、
より専門化が進むと予想されます。
22 Automated Static and Dynamic Obstacle Avoidance in Arbitrary 3D Polygonal Worlds
J.M.P. van Waveren and L.J.M. Rothkrantz
で使用された、AIのためのパスデータ自動生成法が解説されています。
[概説]
@全ての三角形メッシュの傾きを計算する。45度以上のメッシュは通行不可とする。
A通行不可のメッシュを境界として、延長しマップ全体を再分割する(BSP法)。
B動的なパス検索に関しては、落下して来たオブジェクトを床に対して射影し、
その輪郭をパスとすることで対応する。
J.M.P. van Waveren の一連の論文を読まれていると、より理解が深まることでしょう。
http://mrelusive.com/publications/pubs_bydate.html
特に、彼の修士論文(CEDEC2006の自分の講演で示唆したことがあるのですが)は、
BSP法が詳しく解説されています。
The Quake III Arena Bot
J.M.P. van Waveren
Master of Science thesis, Delft University of Technology, June 2001
A 3DFPSにおけるBSP法の源流を訊ねる(有名人大集合…)
以下の、Michael Abrash氏のコラムに情報があります。
Michael Abrash's Graphics Programming Black Book Special Edition
http://www.phatcode.net/res/224/files/html/index.html
ちょっと面白いので引用してみましょう。
http://www.phatcode.net/res/224/files/html/ch60/60-01.html
1993年、私はクリスヘッカーを雇った。その年の暮れ、クリスは私にDOOMのアルファ版を
見せてくれた。私は、驚いて椅子から転げ落ちそうになった…。
BSP ツリーは、ジョンカーマックがDOOMに組み込むことで注目を集めた技術なんだ。