SPE V1 - 길찾기용 지형구조

대략 Ssook Path Engine라는 이름이다..;
사실은 지형데이터이지만 Level이란 네이밍은 지형렌더링쪽에 쓰고 있고, Space란 네이밍은 실제 폴리곤용 네이밍에 쓰고 있는데다..공간 데이터도 아닌지라..;;
마땅히 쓸 네이밍이 없어서 결국 Path라는 네이밍을 썼다..;

알고리즘의 내용은 Multi Height Tile정도가 되겠다.
여러개의 높이를 가지고 있는 타일 데이터다..

김성민씨의 Space Filling Volume을 보고 나니 이럴바엔 예전 2D때 쓰던 방식을 그냥 쓰는게...으흠? 그거 괜찮겠는걸... 하고 만든 내용이다..
사실 만든 내용이라기보단 말한대로 2D때 많이 쓰던 내용이다.
( 아닌가 나만 쓴 내용인가-_-a 2D때도 어디서 보고 만든건 아니긴 했지만 )

일단 잡설은 접어두고 스샷부터 보쟈

대충 이런식이다.
보면 다리위와 아래에 높이 데이터가 있고 오브젝트가 있는부분은 높이 데이터가 없다.
그냥 타일로 나누었고, 하나의 타일은 갈 수 있다/없다가 아니라 높이 값을 가진다.
그리고 여러개의 높이 값을 가지고, 그 높이 값을 비교해서 갈 수 있다/없다 를 판단한다는 내용이다.

내용이 긴 관계로 자세한 내용을 보실분은 more를 클릭해서 보세요.

위에 보이는건 꽃무늬-_-가 아니라.. 하나의 타일에서 옆타일을 갈 수 있나/없나 를 나타낸다.
화살표가 있으면 그 쪽 방향으로 갈 수 있다는걸 말한다.
파일에 저장하지는 않는다.

마을의 전경은 대략 이런 느낌이다.

생성 알고리즘은 간단하다.
적당한 단위(1미터를 사용하고 있다.)안에 들어오는 폴리곤 리스트를 추려내서 bsp에서 사용하는 삼각형 쪼개기로 정확히 단위 안에 들어오는 부분들을 추려낸뒤 적당히 충돌폴리곤과 겹치지 않는 밟을수 있는 폴리곤들을 추려내면 된다.

집오브젝트의 입구부분이다.
파란색은 밟을수 있는 폴리곤 빨간색은 충돌 폴리곤 흰색은 지형이다.

와이어 프레임만 보면 이런 느낌

거기서 한 타일을 위에서 얘기한것처럼 분류별로 영역안(1미터*1미터)안에 들어오는 폴리곤들을 뽑은 이미지다.
실제로는 bsp는 삼각형단위로 쪼개기 때문에 속도를 위해서 라인단위로 뽑을 수 있게 만들었다.
잘보면 삼각형으로 구성되어 있지 않은걸 알 수 있다.

원래의 이미지와 함께 보면 이런 느낌
이런 경우는 블록킹용 폴리곤덕분에 밟을 수 있는 높이는 없다! 라고 나온다.
젤 높은 밟을 수 있는 폴리곤 부터 검사해서 위쪽으로 4미터이내에 다른 폴리곤이 있으면 그 높이는 못쓰는높이-_-a다 라고 판단하고 있다.

머 대략 알고리즘의 내용은 이게 끝이다-_-
간단하다..;

장점은 구현이 간단하고 타일이라 접근속도도 빠르고, 길찾기라던가 여러가지들이 작업하기 편하다...이고
단점은 타일이라 실제로 보기에는 갈 수 있어도 못간다던가 하는 문제가 생긴다.
클라이언트의 경우 폴리곤으로 한번 더 검사를 할 수 있으니 공중에 뜬다던가 하는건 막을 수 있다.
하지만 단점의 경우는 작은 단위를 사용하면 충분히 해결 될 수 있는 문제이다.
한 0.2미터 정도면 충분히 디테일해서 실제로 돌아다녀봐도 어색하지 않다.

현재 게임은 맵이 워낙 넓어놔서 1미터단위를 사용할 수 밖에 없지만.

일단 내용은 서버와 클라이언트가 동일한 지형정보를 처리하여서 서버상에서 벽을 뚫고 다닌다던가 하는 핵을 봉쇄하고, NPC의 길찾기에도 쓰쟈.. 라는 내용으로 나온 내용이다.

그럼 메모리를 계산해보자..
현재 사용하는 맵은 약4,000*4,000미터에 1미터단위를 기준으로 하고 있다.(너무 넓다-.ㅜ)
보통의 경우는 1000*1000미터에 0.25미터 단위를 기준으로 하면 같은 메모리가 나온다.

우선은 높이리스트의 포인터를 가져야 하므로 하나의 단위가 4바이트의 메모리를 차지한다.
4000*4000*4하면 대략 64메가
보통 하나의 단위가 하나의 높이를 가지면(여러개의 높이를 가지기도 하지만 오브젝트덕에 안가지는 경우도 있으니)
4000*4000*2하면 대략 32메가(높이단위를 WORD로 했을때)
현재의 높이단위는 0.1미터로 해서 6553미터 정도를 사용할 수 있다.

이정도면 높이가 좀 복잡해도 100메가 이내이고 이정도면 서버에서 하나의 머신에 1기가 정도를 맵데이터용으로 할당한다면 10개정도의 맵을 가지고 있을 수 있다.

여기서 좀 최적화 하면 높이 데이터가 중복되는게 많기 때문에 그쪽의 용량은 더 줄일 수 있고
WORD인덱스를 사용할 수 있을정도로 줄일 수 있다면(높이 단위를 좀 더 넓히면 중복데이터가 더 많아진다) 40메가 이내로 줄일 수 있다.

아니면 그냥 사용한다고 해도 단위를 조절하면
만약 1000미터에 1미터 단위를 사용한다고 하면 6메가 1000미터에 0.5미터 단위를 사용한다면 24메가 정도이다.

위의 알고리즘은 현재 시스템이 높이에 의한 시스템(절벽에서 떨어지면 높이에 따라 데미지를 입는다던가 높이차에 따라 스킬사용이 제한된다던가)하는 내용이 있어서 그렇고
그렇지 않다면 높이값자체는 그다지 중요해지지 않기 때문에 공간분할을 사용하면 데이터를 확~ 줄일수도 있다.

일단은 여기까지가 버전1의 내용이고.. 새로 개발이 들어가는 버전2에는 다음 내용들이 들어간다.

- 중복데이터 제거를 통한 메모리 절약
내용은 위에 설명한 대로

- 높이데이터가 아닌 공간데이터 저장
데이터에 높이값을 종류를 구분하는 형식
10미터 (충돌 - 위쪽)
5미터 (충돌 - 아래쪽)
1미터 (밟음)
이런형태다. 1미터에 지형이 있고 5~10미터사이에 오브젝트가 걸려 있는 경우를 표현한다.
당연하게 열려있는 공간은 10미터 이상과 1~5미터 사이이다.

이 내용이 추가되면서 가능해지는건
* 크리쳐의 크기에 따른 충돌처리
위의 내용으로는 4미터 이하의 크리쳐만 지나갈 수 있다.
* 비행
공간 데이터로 날아다니는것에 대한 충돌처리가 가능하다.
크리쳐 용도보다는 발사하는 스킬형태에 대한 충돌처리용도
잠수상태의 수영 ( 물위에서의 수영은 쉽지만 잠수상태의 수영은 비행과 마찬가지로 공간데이터가 필요하다. )

- 길찾기 속도향상을 위한 갈수 있는 방향 데이터 저장
현재는 옆타일의 높이들을 직접 비교하고 있다.
그전에 방향별로 갈수 있는 높이가 있는 지를 검사할 수 있으면 길찾기 속도를 높일 수 있다.

뭐 이정도 내용이다.

현재 스케줄 조율을 하고 있지만. 어느정도까지 할 수 있을지는 모르겠다.

조금 먼 내용이지만 2.5에 넣을 내용중에 하나는
- 높이값에대한 충돌데이터 저장
위에 말한것처럼 현재 맵의 크기로 인해 단위를 크게 쓸 수 밖에 없어서
하나의 높이값 이내에 추가적으로 4*4정도로 충돌정보를 저장하면 0.25미터 단위를 쓰는 효과를 나게 할 수 있다.
물론 오브젝트 충돌의 경우만 가능하고 높이로 인해 못가는 경우는 좀 힘들다.
머 높이로 인해 못가는 경우도 하나의 높이를 다시 여러개로 쪼개서 각각 따로 충돌정보를 가지고 있을 수도 있겠지만...

아니면 이 내용대신에 공간 분할이 들어갈지도 모르겠다.
하지만 높이 데이터를 살리면서 공간 분할은 아무래도 힘들지도..흠..

어쨋건 전에 패스엔진을 고려해서 테스트 해보았는데 위에 있는 내용처럼 높이에 대한 처리라던가 메모리라던가 하는 내용들이 감당이 안되서 만든 시스템인데..
필요하신 분들이 있을까봐 정리해서 공개해둔다.