Stupid Funnel 알고리즘을 적용했다. 알고리즘 내용은 아래 링크에서 참고.
http://jceipek.com/Olin-Coding-Tutorials/pathing.html#funnel-algorithm
처음엔 명확하게 이해가 안됐다. 어떤 문서에선 실로 감싼다는 개념으로 설명하는데 이해가 되지 않았다. 일단 꺽이는 위치의 좌표를 구하는건 스킵하고 직선이동이 가능한 경로를 찾는데 촛점을 맞춰서 구현을 시작했다. 몇 일 작업을 하다보니 이 알고리즘의 기본 원리가 보였다.
이거 3D에서 가시성 검사할때 사용하는 Portal-Culling이랑 개념이 같다.
Room/Portal방식에서 visibility테스는 다음과 같이 이루어진다.
- Room과 Room은 Portal(다각형)로 연결된다.
- 현재 카메라가 위치한 Room으로부터 연결된 Portal을 순회하며 Portal이 view-frustum에 교차되는지 테스트한다.
- portal에 교차하는 경우 view-frustum을 portal에 맞게 줄여나간다.
- portal을 통해 다음번 room으로 진입. 여기서 렌더링 후보를 수집한다.
- 일반적으로 portal 통과할때마다 frustum사이즈가 점점 작아지므로 portal을 통과할수록 수집되는 렌더링 후보의 수도 줄어든다.
Stupid Funnel알고리즘도 기본적으로 frustum을 가지고 시작점에서 출발하여 경로들을 연결한 엣지(portal)을 통과하며 frustum사이즈를 줄여나간다. portal이 교차하지 않거나 portal의 길이가 너무 짧아지면 이후의 경로로 ‘직진으로는’ 이동할 수 없다. 즉 한번에 직선으로 최대한 이동가능한 목표 좌표를 구할 수 있다.
여기까지 이해하고나서 3D visibility 테스트와 같은 방식으로 Stupid Funnel 알고리즘을 구현했다. 구현은 다음과 같다.
- 경로 상의 각 삼각형이 연결되는 엣지를 portal로 설정한다.
- 시작 위치와 최초로 만나는 portal을 연결하면 삼각형이 나온다. 이 녀석이 3D가시성 테스트에서의 view-frustum에 해당된다.
- 최초의 frustum과 이후 경로를 따라 만나는 portal들에 대해서 다음과과 같이 처리
- portal이 furstum에 완전히 포함할 경우 지금 만난 portal에 맞춰서 frustum의 크기를 줄인다.(frustum을 이루는 삼각형의 밑변이 좁아진다)
- frustum이 portal에 완전히 포함될 경우(엣지의 두 점 사이에 frutum이 위치할 경우) frustum의 크기 그대로 유지.
- frustum이 portal에 걸칠 경우(엣지의 한 점은 frustum내부에, 다른 한점은 frustum바깥에 있을때) frustum이 portal의 엣지를 벗어나지 않도록 frustum크기를 줄인다.
- 이외의 경우, 즉 furstum과 portal이 전혀 겹치지 않는 경우. 이 portal은 통과 불가. 루프를 끝낸다.
- portal이 통과 가능할 경우 현재 portal의 엣지의 중점을 목적지 좌표로 설정하고 다음번 portal을 방문한다.
- 루프가 끝났을때의 최종적으로 저장된 목적지 좌표가 경로상에서 최대한 직선으로 움직일 수 있는 좌표가 된다.
일단 네비게이션 메시의 삼각형의 무게중심을 기준으로 A*알고리즘을 적용하는 방식은 기존과 같다. 따라서 최단경로를 이루는 네비게이션 삼각형 목록은 그대로다. 경로를 따라가는 이동방식을 바꿔서 이전보다 훨씬 효율적으로(지그재그 움직임이 줄어들어) 움직이게 됐다.
현재는 네비게이션 메시도 충돌처리용 삼각형을 사용하기 때문에 난간, 기둥, 벽등의 지형이 네비게이션 메시 위에 위치하게 된다. 이로 인해서 멀쩡히 경로를 따라가다가도 벽에 부딪쳐서 전진하지 못하는 상황이 생긴다. 그래픽 디자이너가 작업해주면 간단하지만 그래픽 디자이너가 없으니 자동생성해야한다. 정확한 네비게이션 메시를 생성하는 방법을 연구해야한다.
[2020/11/16에 추가]
길찾기 디버깅용 렌더링 코드를 조금 수정했다. 흰색 선과 흰색 구는 매 포탈을 지날때마다 중간 생성된 프러스텀과 목적지 좌표.녹색 선과 녹색 구는 연결된 경로들의 최단연결하는 최종적인 프러스텀과 목적지 좌표.
yuchi's development 