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

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

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

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

Наверное, главный вопрос в том, как мне быстро добраться до соседей?

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

Спасибо, с уважением


navigation path-finding a-star pathfinder quadtree
person Klaus Koeder    schedule 24.09.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

Наверное, главный вопрос в том, как мне быстро добраться до соседей?

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

person BlueRaja - Danny Pflughoeft    schedule 24.09.2012

arrow_upward
0
arrow_downward

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

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

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

person Karussell    schedule 28.09.2012