1

QuadTree でナビゲーション/A* を実行したい。

私はすでに QuadTree を実装しているか、少なくとも私が QuadTree だと思っているものを実装しています。一方、内部ノードにも要素が含まれている場所をいくつか見てきました。私の場合、内部ノードはその子にのみリンクし、要素はリーフ ノードのコレクションに格納されます。各ノードはその親にリンクしていますが、(現在) 隣接ノードへのリンクはなく、兄弟も他のブランチのノードもありません。要素は領域であり、点だけではありません。

また、グリッドで A* をかなりの時間見たり、QuadTree でデモを見たりしましたが、これには詳細がありませんでした。

主な問題は、どうすればすぐに隣人にたどり着くことができるかということだと思います。

葉を互いにリンクしたままにしておくべきかどうかはわかりません。しかし、要素が位置を更新するにつれてツリーが動的になるため、これは大変な作業になります。また、ノードのサイズによっては、大きなリーフが一方向 (東など) に多くの小さなリーフを持つ可能性があるため、リンクの動的コレクションの王様も必要になります。これを更新するための努力は非常に大きなものに思えますが、現在はどうすればよいかわかりません。

Thx n rgds

4

2 に答える 2

0

可能ですが、最適ではないことは確かです。A* はグラフのデータ構造に対して行われます。「グラフ」は、ノードに非常に高速にアクセスできることを意味します。直接ポインタ/参照を使用することをお勧めします。

四分木を介して隣人を取得する通常の方法は、ウィキペディアで説明されています。そのため、サブエントリがクエリの境界内にあるかどうかを再帰的に確認します。また、すでに実装されています。

さらに A* が必要な場合は、逆の方法で実行できます。通常のグラフを使用し、その上で A* を実行し、グラフに直接最近傍検索を実装します。

于 2012-09-28T09:01:05.500 に答える
0

A* は、開始ノードから終了ノードまでの最短経路を見つけるためのアルゴリズムです。これはツリーではあまり意味がありません.

何らかの理由でツリー内の終了点を見つけることができなかった場合は、ツリーを通常のグラフとして扱い、幅優先検索(または、ある種のヒューリスティックがある場合は A*) を実行する必要があります。

主な問題は、どうすればすぐに隣人にたどり着くことができるかということだと思います。

ツリー内の各ノードの親へのポインターを格納します。次に、ノードの兄弟は、その親のすべての子を表示することで表示できます。

于 2012-09-24T19:19:00.000 に答える