3D길찾기를 시도하면서 큰 목표중 하나가 복셀맵에서 길찾기를 하는것이었다. marching cube알고리즘으로 일단 voxel지형에서 삼각형을 생성할 수 있다. 이걸 네비게이션 매시로 사용해서 길찾기를 하면 되기는 하는데…..문제가 있다. 복셀 매시로부터 삼각형 매시를 생성. 삼각형이 미친듯이 많이 나온다. 복셀 매시로부터 생성한 삼각형을 최적화. 인접한 삼각형간에 엣지를 공유할 수 없게 된다. 엣지를 공유하지 않으므로 네비게이션 매시로 사용할 수 없게 된다. … More 3D 길찾기 구현중 #4 – voxel지형으로부터의 네비게이션 매시 생성

Stupid Funnel 알고리즘을 적용했다. 알고리즘 내용은 아래 링크에서 참고. http://jceipek.com/Olin-Coding-Tutorials/pathing.html#funnel-algorithm 처음엔 명확하게 이해가 안됐다. 어떤 문서에선 실로 감싼다는 개념으로 설명하는데 이해가 되지 않았다. 일단 꺽이는 위치의 좌표를 구하는건 스킵하고 직선이동이 가능한 경로를 찾는데 촛점을 맞춰서 구현을 시작했다. 몇 일 작업을 하다보니 이 알고리즘의 기본 원리가 보였다. 이거 3D에서 가시성 검사할때 사용하는 Portal-Culling이랑 개념이 같다. Room/Portal방식에서 … More 3D 길찾기 구현중 #3 – visibility 테스트와 유사한 Stupid Funnel 알고리즘 적용

‘복셀 데이터 -> 마칭큐브로 삼각형 변환 -> 네비게이션 매시 변환’ 을 해보고 나서서 인접한 엣지를 타고 삼각형들간의 그래프 자료구조를 만드는게 더럽게 느리다는 사실을 깨달았다. 코드를 왕창 뜯어고쳐서 50배쯤 빠르게 만들고나서 다시 테스트를 했다. 복셀맵으로부터 생성한 네비게이션 매시는 삼각형 분포가 너무 조밀하거나(최적화 안했을때), 혹은 엣지가 자료구조상 연결이 될 수 없거나(최적화 했을때) 복셀쪽은 생각을 좀더 해보기로 하고 … More 3D 길찾기 구현중 #2

퀘이크3처럼 bot과의 전투를 넣으려고 한다. 그러기 위해선 bot이 알아서 길을 찾아야한다. 당초 기술기반을 구축할때 3D길찾기는 고려하지 않았다. 몬스터는 충분히 바보같아야하고 따라서 각자의 스폰 영역을 벗어날 필요가 없었다. 그런데 bot과의 1:1 전투를 하려면 bot이 똑똑할 필요가 있다. 물론 bot을 똑똑하게 만들 자신은 없다. 그래도 bot이 플레이어를 잡으러 돌아는 다녀야 한다. 그러려면 길찾기가 필요하다. 그래서 일단 길찾기는 … More 3D 길찾기 구현중 #1