Как сделать A* Навигация на QuadTree

Question

Я хочу сделать навигацию /A* на QuadTree.

Я уже внедрил QuadTree, или, по крайней мере, то, что я считаю QuadTree. Между тем я видел некоторые, где также внутренние узлы содержат элементы. В моем случае внутренние узлы связаны только со своими дочерними элементами, а элементы хранятся в коллекциях в конечных узлах. В то время как каждый узел ссылается на своего родителя, в настоящее время нет ссылок на соседние узлы, а также на узлы и узлы других ветвей. Элементы - это регионы, а не просто точки.

Я также видел A * довольно давно на сетках и даже демо на QuadTree, но это было без подробностей.

Я предполагаю, что главный вопрос - как быстро добраться до моих соседей?

Я не уверен, стоит ли мне связывать листья друг с другом. Но это было бы адской работой, поскольку дерево динамично, поскольку элементы обновляют свою позицию. Также потребуется некоторый король динамического сбора ссылок, так как в зависимости от размера узла у большого листа может быть много маленьких листов в одном направлении (например, на восток). Попытка обновить это кажется довольно большой, даже в настоящее время не знаю, как я это сделаю.

Thx n rgds

Answer 1

Это возможно, но точно не оптимально. A* делается на графических структурах данных. Где "график" означает, что узел может быть доступен очень быстро - предпочтительно через прямой указатель / ссылку.

Обычный способ получения соседей через quadtree описан в википедии - поэтому проверяйте, находится ли подстрока в границах запроса. Это также уже реализовано.

Если вам дополнительно нужен A *, вы можете пойти другим путем: использовать нормальный граф, выполнить A * на нем и выполнить поиск ближайших соседей непосредственно на графике.

Answer 2

A* - алгоритм поиска кратчайшего пути от начального узла до конечного узла. Это на самом деле не имеет большого смысла в деревьях, так как самый короткий путь всегда должен идти вверх от начала до наименьшего общего предка, а затем до конца.

Если по какой-то причине вы не смогли найти финишную черту в дереве, вам пришлось бы рассматривать дерево как нормальный граф и выполнять поиск в ширину (или A*, если у вас была какая-то эвристика)

Я предполагаю, что главный вопрос - как быстро добраться до моих соседей?

Сохраните указатель на родительский узел каждого узла в дереве. Затем можно просмотреть братьев и сестер узла, просмотрев всех потомков его родителя.