3D 길찾기 구현중 #1

퀘이크3처럼 bot과의 전투를 넣으려고 한다. 그러기 위해선 bot이 알아서 길을 찾아야한다. 당초 기술기반을 구축할때 3D길찾기는 고려하지 않았다. 몬스터는 충분히 바보같아야하고 따라서 각자의 스폰 영역을 벗어날 필요가 없었다.

그런데 bot과의 1:1 전투를 하려면 bot이 똑똑할 필요가 있다. 물론 bot을 똑똑하게 만들 자신은 없다. 그래도 bot이 플레이어를 잡으러 돌아는 다녀야 한다. 그러려면 길찾기가 필요하다.

그래서 일단 길찾기는 넣기로 했다. 기본 아이디어는 다음과 같다.

  • 네비게이션 매시를 사용한다.
  • A* 알고리즘을 사용한다.
  • 네비게이션 매시로 사용하는 각 삼각형의 무게중심을 way point로 사용한다.
  • 삼각형 베이스 맵의 경우 충돌처리용 삼각형을, Voxel맵인 경우 Marching Cube알고리즘으로 삼각형 집합으로 변환한후 그 삼각형들을 네비게이션 매시로 사용한다.

이걸 해야되나 말아야되나를 하루에도 열두번씩 고민하며 그래도 꾸역꾸역 한두시간씩이라도 작업을 해서 일단 기본적인 길찾기/이동은 가능하도록 만들었다.

돌아는 가는데 예상대로 문제가 좀 있다.

  1. 충돌처리용 삼각형은 면 개수가 적은게 중요한데 이런 특성은 네비게이션 매시로서는 적합하지 않다.
  2. 충돌처리 삼각형 특성상 면적이 넓은데 따라서 무게중심 좌표가 심각하게 지그재그 패턴으로 배치된다. 무게중심 좌표를 way point로 사용하고 있으므로 이동 경로도 심각하게 지그재그가 된다.
  3. 충돌처리용 삼각형 특성상 모든 삼각형이 기하학적으론 붙어있어도 엣지는 공유하지 않는 상황이 많이 발생한다. 이를테면 커다란 바닥 삼각형 위에 기둥이 있는 경우다. 이럴땐 삼각형의 무게중심좌표(way point로 사용할)가 기둥 밑에 깔리게 된다. 캐릭터는 절대로 이 way point를 통과하지 못한다.

bot에 대해서만 길찾기를 사용할 것이고 bot이 몇 마리 안들어갈것이므로 속도는 전혀 문제가 안된다.

way point를 균일하게 분포시키는게 최대의 문제다. 복셀 맵의 경우 marching cube를 이용해서 삼각형으로 변환하면 꽤 균일하게 배치된 삼각형 집합을 얻는다. 따라서 오히려 문제가 안된다. 모델러 지원을 받을 수 없는 나로선 삼각형 베이스맵이 더 문제다.

자동으로 CSG를 해서 삼각형을 떼주던가..뭐 그런 방법을 생각해봐야할거 같은데. 좀 고민좀 해봐야겠다.


답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중