[ActionScript 3.0] 四分木からグラフを構築して、最短経路を探索する。│miscellaneous下のデモでは赤い円を障害物と見立て、円に衝突しないように左上から右下まで最短ルートを求めて緑の線を引いています。 赤い円はマウスで移動できます。移動するごとにルートを再探索します。 次の手順でルートを探索しています。 1. 赤い円の位置を元に四分木を構成。（黒い線が四分木の境界です） 2. 四分木の領域の中心点を頂点と見立ててグラフを構築。領域同士が隣あっている場合頂点同士を結んで辺とする。（青い線がグラフの辺です） 3. 構築されたグラフを元にダイクストラ法で最短路を探索。（頂点間の距離を辺の重みとしています） 障害物がない部分では四分木の領域が広くなるため、必ずしも領域の中心位置が最短の経路上にくるとは限りません。 したがってこの方法で求めた経路が平面状の最短距離にはなりませんが、四分木の領域が広いということはグラフの頂点の数が減るわけですから 経路を求める際の計算量は少なくなることに
