howto는 QuadTree에서 A * Navigation을 수행합니다.

Question

QuadTree에서 내비게이션/A *를하고 싶습니다.

이미 QuadTree를 구현했거나 적어도 QuadTree라고 생각합니다. 한편 일부에서는 내부 노드에도 요소가 들어있는 것을 보았습니다. 광산에서 내부 노드는 자식 노드에만 연결되고 요소는 리프 노드의 컬렉션에 저장됩니다. 각 노드가 상위 노드에 연결되어 있지만 (현재) 이웃 노드에 대한 링크가 없으며 형제 노드 나 다른 분기의 노드도 없습니다. 요소는 단지 점이 아닌 영역입니다.

그리드에서 꽤 오랜 시간이 걸렸지 만 QuadTree의 데모에서도 보았습니다. 그러나 이것은 세부 사항이 아닙니다.

내가 주된 질문은 내 이웃 사람들에게 어떻게 신속하게 도달 할 수 있을까요?

잎이 서로 연결되어 있어야하는지 잘 모르겠습니다. 그러나 요소가 자신의 위치를 ​​업데이트 할 때 나무가 동적이기 때문에 이것은 지옥 일 것입니다. 큰 잎이 한 방향 (예 : 동쪽)에 작은 잎을 많이 가질 수있는 노드 크기에 따라 링크에 동적 컬렉션의 왕이 필요합니다. 이것을 업데이트하려는 노력은 아주 거대하게 보입니다. 현재 어떻게해야할지 모릅니다.

들으 N 개의 RGDS

Answer 1

A *는 마무리 노드로 시작 노드에서 최단 경로를 찾는 알고리즘이다. 최단 경로는 항상 처음부터 least-common-ancestor까지 올라간 다음 끝까지 내려 가기 때문에 나무에서는별로 의미가 없습니다.

어떤 이유 때문에 트리에서 마무리를 찾을 수없는 경우 나무를 일반 그래프로 처리하고 너비가 먼저 검색 (또는 A * 발견의 일종)

나는 주요 질문은 내가 빨리 내 이웃에 도착 어떻게 것 같아요?

트리 내의 각 노드의 상위 노드에 대한 포인터를 저장하십시오. 그런 다음 노드의 형제는 모든 부모의 자식을보고 볼 수 있습니다.

Answer 2

가능하지만 확실히 최적이 아닙니다. A *는 그래프 데이터 구조에서 수행됩니다. 여기서 '그래프'는 노드가 매우 빠르게 액세스 될 수 있음을 의미합니다. 직접 포인터/참조를 통해 선호됩니다.

quadtree를 통해 인접 항목을 가져 오는 일반적인 방법은 explained on wikipedia입니다. 따라서 하위 항목이 쿼리 범위 내에 있으면 반복적으로 확인하십시오. 또한 already implemented입니다.

또한 A *가 필요한 경우 일반 그래프를 사용하고 A *를 수행하고 가장 가까운 이웃 검색 directly on the graph을 구현하십시오.