go4game의 spatial partition을 octree로 바꿨습니다.
By SeukWon Kang
설명: ai3의 회피 알고리즘 테스트 동영상 - 글내용과 무관함 ^^
기존 wxgame2에서 부터 충돌 검사와 AI 를 의해 사용해 오던 준 동적 공간분할 대신 나름 정통 공간 분할인 octree로 바꿨습니다.
기존에는 공간을 매 프레임 마다 총 object의 수에 비례하는 (축당 math.pow(ocount, 1/3)) 배열로 분할 해서 충돌 검사 및 AI에게 주변 환경정보를 제공하는데 사용해 왔습니다.
하지만 아무래도 약식이라 부족한 점이 많아서 공간 분할을 하는 몇가지 알고리즘 중에 일단 octree를 선택, 구현 해봤습니다.
바꾸고 나서 테스트 해보니.
일단 느려졌습니다. ^^;; 30%정도는 느려진듯 합니다. ( 960만 -> 650만 정도 ) 기존에 사용하던 방법이 약식이라 유연성과 확장성이 떨어지는 문제로 바꾼거라 느려질것으로 예상은 했습니다.
대신 기존의 문제점을 해결 할수 있게 되었습니다. 공간을 등분해서 충돌 검사를 하고 또 클라이언트에게 이 분할 정보를 제공하는 형태를 사용 했었는데 각 클라이언트(+AI)에게 주변 가시 거리내의 object 정보만 제공하기 위해서는 상당히 많은 양의 코드를 작성해야 했었으나 이제는 간단하게 HyperRect만 지정하면 그 안의 object list를 제공할수 있게 되었습니다. 그리고 이로 인해 기존 네트웍 사용량이 많던 문제도 같이 해결되었습니다.
그리고 결과적으로 코드가 더 작아지고 유지보수성도 올라갔습니다.
결과적으로 온라인 게임에서 필요한 각 클라이언트에게 모든 월드 내 object 정보를 제공하는 것이 아니라 각 클라이언트 시야 내의 object 정보만을 제공하는 것이 가능하게 되었습니다. ( 이로 인해 네트웍 사용량과 서버 처리양도 같이 줄어드는 효과도 있습니다. )
아직은 매 프레임 마다 octree를 만들고 있는데 효율을 위해서 octree를 만들고 각 프레임별 변화만을 반영해서 octree를 수정하는 형태로 만드는 것이 가능할지 고민 중입니다. ( 조금 복잡한 문제가 있는 것이 현재는 team이 각 world간 이동에 상당히 자유로운지라 world별 octree에서 팀이 통채로 빠지거나 추가되는 것이 필요합니다. )