움직이는 물체에 대한 쿼드, KD트리 효율 질문

Question

강의 잘들었습니다 😊 😊 강의를 들으면서 한가지 의문이 생겼는데요 쿼드트리나 KD트리를 이용하면 다수의 물체에 대한 충돌체크에 쓰이면 좋을거 같다는 생각을 했습니다. 강의에서는 고정된 물체에 대해서 트리를 구축하고 질의(Query)를 실행하는데요 만약 물체가 움직이게 된다면 위치값이 계속바뀌닌까 이 알고리즘을 사용할수 없을수도 있을거 같았습니다. 움직일때마다 트리를 재구축 해줘야하닌까 더 비효율적이지 않을까요?? 움직이는 다수의 물체에 대해 충돌체크를 하려면 쿼드트리를 사용하고 물체가 이동할때마다 트리 노드가 들고있는 물체 목록을 옮겨 다니는 로직을 만들어야 할까요?

ideugu · Answer

네 좋은 질문입니다.
지금 설명한 알고리즘은 배경과 같은 정적인 물체에 대해 진행하는 것이 맞습니다.
보통 실전에서 이런 충돌처리는 게임 엔진 내부의 물리 엔진이 담당하는데, 물리 엔진은 정적인 물체와 동적인 물체를 구분해 별도로 충돌 처리를 진행합니다. 물리 엔진의 충돌 처리방법은 2D, 3D에 따라 다르며, 기밀 유지를 위해 블랙박스로 제공되어 있어, 정확한 구현 방식을 알 수 없습니다.
본 강의에서 설명하는 알고리즘은 이를 공부하기 위해 필요한 기초 알고리즘이라고 보시면 될 것 같아요.
구현 자체는 그리 어렵지 않기 때문에 간단한 게임 로직을 구현할 때 응용해 사용할 수 있습니다.