3D 空間でパスファインディングを実行するために使用したい octree があります。特定のノードの近くにあるノードを簡単に見つけられるようにするために、モートン コードを使用してノードを並べ替えています。うまく機能しているようです。取得したノードのサブセットは、比較的近くにクラスター化されています。私が苦労しているのは、ノードの直接の隣人を取得する効率的な方法を見つけることです。
ツリーの以前のバージョンでは、葉がすべて同じサイズのノードで、必要なサイズになるまで、ツリーを細分化していました。これにより、各ノード間に一貫したオフセットがあったため、隣接ノードを簡単に見つけることができました。そのため、ノードを見つけると予想される位置でモートン コードを再計算し、コードに基づいてノードを取得することができました。しかし、ジオメトリがあまりない領域 (たとえば、8 つの空の子を取得する場所) ではツリーを分割しないことで、ツリーをより効率的にしようとしています。その結果、特定のノードが持つ可能性のあるネイバーの数も、ネイバーのサイズもわかりません (2 のべき乗であることを除いて)。
私の最初の考えは、配列内のいずれかの方向で近くのノードを検索することでした。これは機能しますが、すべての隣接ノードを取得することを保証するにはあまりにも広いネットをキャストする必要があり、大量のノードを評価するのに時間を費やしていました。それは私には必要ありません。簡単なテストでは、アレイ内のいずれかの方向に 50 個のノードがあっても、すべての近隣ノードを取得できる保証はないことがわかりました。
ツリーは静的であるため、上記のブルート フォース メソッドを使用してノードの隣接ノードを 1 回生成し、隣接ノードを保存することができます。しかし、これによりプログラムの初期ロード時間が許容レベルを超えて増加する可能性があるのではないかと心配しています. 隣人をリアルタイムで見つけることができるアルゴリズムはありますか?
編集：探しているものと試したことを明確にするために質問を言い換えました。