알고리즘 확인(?) 질문

이득우의 꼭 배워야하는 게임 알고리즘

4강 쿼드트리의 개요와 동작원리

작성

304

수정됨

아직 아리까리해서 확인 질문드립니다 ㅜㅜ...

강의 예시 부분에서 주황색영역(AABB체크할 영역)에 포함되는 노드를 찾아 검사대상에 올리는데요.

깊이3 쿼드트리 노드 85개 전체를 돌면서 주황생영역이 포함된 노드를 찾게 되는 것일까요?

그런다음 검사대상인 노드만 돌면서 노드에 등록된 물체에 대해 AABB충돌체크를 진행 하게 되는걸까요?

답변 2

지식공유자

네 트리를 사용하는 목적은 탐색의 횟수를 크게 줄이는데 있습니다. 쿼드트리는 log4N의 복잡도를 가지게됩니다.

제공해주신 코드를 보면,
85개 노드 전체를 돌면서 주황색영역이 포함된 노드를 찾지 않습니다.
주황색 영역이 포함된 노드(루트 노드부터 시작)를 검사대상 노드로 추가하고,

또 그 노드의 4개의 노드중 주황색 영역이 포함된 노드를 검사 대상 노드에 추가하고... 이런식으로 로직이 만들어져 있네요

1. 체크하기 원하는 주황색영역이 포함된 자식 노드를 찾고 (4개로 나뉘어진 범위중 어떤 범위에 속해 있는가/ 여러개일 수 있음)

포함된 자식 노드에서 다시 또 주황색 영역이 포함된 자식노드를 찾아 possibleNode에 넣어줍니다. (자식 노드에서 다시 4개로 나뉘어진 범위중 어떤 범위에 속해 있는가를 찾아 넣어줍니다.)
이 과정을 반복합니다

이후 넣어준 범위들을 순회하며 충돌 가능 대상 목록에 넣어줍니다.

질문자

다음강의 코드 설명에서 나오는군요 감사합니다 ㅎ

지식공유자

휴가 중이라 답신을 못 드렸는데, 임형국님이 친절하게 답신해주셨네요.

감사합니다!

인프런 커뮤니티 질문&답변