[🐣질문] 쿼드 트리 구현해보신분??

[익명(222.120)]

매 프레임마다 어떤 오브젝트 A 근처에 몇개의 다른 오브젝트가 존재하는지 찾아서 특정 처리를 하는식인데 이게 그냥 구현하면 빅오 n^2 라서 오브젝트 수가 어느정도 많으면 성능이 말도 안되게 느려지더라구요..

한 1000개만 넘어가도 개느려져서 방법이 없나 찾아보는데 공간 분할 자료구조? 가 필요하다고 알게 됐읍니다. 그래서 쿼드트리라는 놈을 알아내서 얘를 구현해보려고 하는데 공부할만한 자료나 구현 팁 같은것 있다면 좀 알려주시면 감사하겠습니다.

[익명(1.235)]

트리가뭔지알면 그냥자동아님?

[익명(14.32)]

구현 가능성을 떠나서 접근 방법으로 좋은지 모르겠다.. 실시간으로 갱신될 필요가 있는 데이터 같은데 쿼드 트리 쓰는게 맞나 모르겠네..

[익명(14.32)]

만약 건물같이 자주 변경되지 않는 오브젝트들에 대한 충돌 처리를 생각하고 있는 거라면 건물이 추가될 때마다만 쿼드 트리를 갱신하면 되니까 적합한 상황으로 보임.. 근데 그게 아니라 실시간으로 위치가 변경되는 오브젝트들 간의 충돌 처리라면 쿼드트리를 구성하는 비용때문에 오히려 낭비일수도 있다.. 물론 매 프레임에 모든 오브젝트가 다 충돌 테스트가 필요하면 프레임 별로 한번씩 만들고 재이용하는데 의미가 있을지도 모르겠긴 한데;;;

[익명(14.32)]

오히려 옛날에 심리스 게임 같은데서 사용하던 로컬 섹터 기반으로 뷰를 구성해서 인접 섹터까지만 검색하는 방식이 더 좋을지도.. 문제 상황을 들어봐야 알겠다만

[익명(14.32)]

쿼드 트리 실시간으로 변경되는 동적 데이터에는 적용하기 별로라고 알고있는데 아님?

[익명(14.32)]

몰라 GPT가 그랬어.. 쿼드트리 알고리즘이 성능적인 이점을 제공하긴 하지만, 어떤 경우에는 성능이 저하될 수 있습니다. 이러한 성능 저하를 유발할 수 있는 요인들 중 일부 예시는 다음과 같습니다. 불균형한 트리: 데이터가 공간적으로 균일하게 분포되어 있지 않거나, 데이터가 특정 영역에 몰려 있는 경우 쿼드트리는 불균형한 구조를 가질 수 있습니다. 이렇게 되면 트리의 깊이가 불필요하게 커져 검색, 삽입 및 삭제 작업의 성능이 저하될 수 있습니다. 동적 데이터: 데이터가 빈번하게 추가되거나 삭제되는 경우, 쿼드트리 구조를 유지하고 업데이트하는 데 추가적인 비용이 발생합니다. 재조정 작업이 필요한 경우 성능 저하가 발생할 수 있습니다.

[소닉쫄따구테일즈(dcz3xv7zgu14)]

동네 초딩쓰라고 만든게 쿼드 트리임. 그래서 나도 이거밖에안써... 다른건 모르겟음.. 동적으로 변경되는거 탐지해서 재구성해주는거 귀찮아서 매프레임 트리 재구성해주는데도 정말 빠름.