空間分割

A*でパス探索をするには、場所がどんな状態であるかを知る必要があります。
その場所や状態を定義する方法が、「空間分割」です。
　
さて、Game Programming Gemsには５つの空間分割法が載っていたのですが、
理解できたのは、「矩形グリッド」と「クオドツリー」だけですね…。
　
矩形グリッドは、タクティクスオウガのように、すべて同じ大きさの矩形に分割した空間ですね。
うん、これはよく使われるからすぐ分かりました。
　
で、クオドツリーは、空間に障害物が含まれる場合に４分割を再帰的に行う方法ですね。
（正確には、中心点を結んだ線が障害物を通る場合、４分割を行う）
　
と、ここまでは理解できたのですが、「凸型ポリゴン」と「可視ポイント」と「一般化角柱」が分からないですね。
以下引用。

凸型ポリゴンとは、空間を一様な凸型ポリゴンで分割することである。

凸型ポリゴンってなんだろ…。まずはそこからですね。

可視ポイントとは、探索ポイントを提供する。
探索ポイントは、障害物の頂点あたりに配置する。

あ、これは書いているうちに分かりました。（・∀・）ノ
つうか、そのまんまですね。
障害物の曲がり角を通るようにするわけですね。
　

一般化角柱とは、隣接した障害物間のスペースを２Dの角柱とみなす。
各隣接障害物のペア間で中心点を計算する。

なんとなく、わかったようなわからないような…。
可視ポイントとは逆に、道の真ん中をとおるような感じですかね。
　
おお、凸型ポリゴン以外は書いているうちになんとなく分かってしまいましたね。
わかんなくても書き出してみると、意外に分かるものなのですね。