У меня есть октодерево, которое я хочу использовать для поиска пути в трехмерном пространстве. Я использую коды Мортона для упорядочения узлов, чтобы иметь возможность легко находить узлы рядом с любым заданным узлом. Кажется, он отлично работает; любое подмножество узлов, которые я захватываю, сгруппировано относительно близко друг к другу. Где я борюсь, так это в том, чтобы найти эффективный способ получить непосредственных соседей узла.
В более ранней версии дерева оно подразделяло дерево до тех пор, пока все листья не были узлами одинакового размера с размером, который я хотел. Это упростило поиск соседей, поскольку между каждым узлом было постоянное смещение, поэтому я мог просто пересчитать код Мортона в той позиции, в которой я ожидал найти узел, а затем получить узел на основе кода. Но я пытаюсь работать с деревом более эффективно, не разбивая его так сильно в областях, где не так много геометрии (например, где я получил бы 8 пустых дочерних элементов). В результате я больше не знаю, сколько соседей может иметь данный узел, ни размер любого из соседей (кроме степени числа 2).
Моя первоначальная мысль состояла в том, чтобы искать близлежащие узлы в любом направлении в массиве, что сработало бы, но мне пришлось бы использовать слишком широкую сеть, чтобы гарантировать получение всех соседей, и я бы потратил время на оценку тонны узлов. что мне не нужно. Быстрый тест показывает, что даже 50 узлов в любом направлении в массиве не гарантируют получение всех соседей.
Дерево статично, поэтому я мог бы, возможно, сделать однократную генерацию соседей узла, используя описанный выше метод грубой силы, и сохранить соседей; но я боюсь, что это может увеличить начальное время загрузки программы сверх допустимого уровня. Есть ли алгоритм, который может найти соседей в режиме реального времени?
Изменить: вопрос изменен, чтобы уточнить, что я ищу и что пробовал.
