목차
1. RecastDemo의 findPath 함수
2. 폴리곤 경로 탐색
3. 부드러운 경로 탐색
4. 요약
1. RecastDemo의 findPath 함수
일전에 네비게이션 빌드의 결과로 navQuery와 navMesh 객체를 생성하는 것을 확인했다. 이제 빌드된 네비게이션 맵 위에 경로의 시작점과 끝 점을 설정했을 때 경유해야할 지점들을 어떻게 얻어낼 수 있는지 알아보자.
RecastDemo 프로젝트를 실행한 후 Test Navmesh 옵션이 활성화된 상태에서 지면에 마우스를 클릭하면 경로의 시작점과 종점을 지정할 수 있다. 이렇게 경로를 지정할때마다 NavMeshTesterTool 클래스의 recalc 함수가 호출되는데, 시작점과 종점이 모두 지정된 상태라면 일전에 생성한 navQuery 객체로부터 findPath 함수가 호출된다.
2. 폴리곤 경로 탐색
void NavMeshTesterTool::recalc()
{
if (!m_navMesh)
return;
if (m_sposSet)
m_navQuery->findNearestPoly(m_spos, m_polyPickExt, &m_filter, &m_startRef, 0);
else
m_startRef = 0;
if (m_eposSet)
m_navQuery->findNearestPoly(m_epos, m_polyPickExt, &m_filter, &m_endRef, 0);
else
m_endRef = 0;
m_pathFindStatus = DT_FAILURE;
if (m_toolMode == TOOLMODE_PATHFIND_FOLLOW)
{
m_pathIterNum = 0;
if (m_sposSet && m_eposSet && m_startRef && m_endRef)
{
#ifdef DUMP_REQS
printf("pi %f %f %f %f %f %f 0x%x 0x%x\n",
m_spos[0],m_spos[1],m_spos[2], m_epos[0],m_epos[1],m_epos[2],
m_filter.getIncludeFlags(), m_filter.getExcludeFlags());
#endif
m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);
m_nsmoothPath = 0;
findPath 함수는 시작좌표와 끝 좌표로부터 가장 가까운 시작 폴리곤, 끝 폴리곤의 레퍼런스를 가져오고, 시작부터 끝 폴리곤까지 가면서 경유하게 되는 폴리곤들의 레퍼런스들도 가져온다.
3. 부드러운 경로 탐색
if (m_npolys)
{
// Iterate over the path to find smooth path on the detail mesh surface.
dtPolyRef polys[MAX_POLYS];
memcpy(polys, m_polys, sizeof(dtPolyRef)*m_npolys);
int npolys = m_npolys;
float iterPos[3], targetPos[3];
m_navQuery->closestPointOnPoly(m_startRef, m_spos, iterPos, 0);
m_navQuery->closestPointOnPoly(polys[npolys-1], m_epos, targetPos, 0);
static const float STEP_SIZE = 0.5f;
static const float SLOP = 0.01f;
m_nsmoothPath = 0;
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
이제 시작점부터 종착점까지 전진거리(STEP_SIZE)를 0.5로 잡고 경로에 위치한 경유지점들을 찾아내야 한다. 시작점과 종착점을 시점 폴리곤과 종점 폴리곤 위에 사영시켜 이터레이터용 좌표변수(iterPos)를 시점으로부터 초기화한다.
// Move towards target a small advancement at a time until target reached or
// when ran out of memory to store the path.
while (npolys && m_nsmoothPath < MAX_SMOOTH)
{
// Find location to steer towards.
float steerPos[3];
unsigned char steerPosFlag;
dtPolyRef steerPosRef;
if (!getSteerTarget(m_navQuery, iterPos, targetPos, SLOP,
polys, npolys, steerPos, steerPosFlag, steerPosRef))
break;
bool endOfPath = (steerPosFlag & DT_STRAIGHTPATH_END) ? true : false;
bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION) ? true : false;
지금부터는 반복문에 진입하여 부드러운 경로(smoothPath)를 만들어내는 구간이다.
getSteerTarget함수는 네비게이션 메시가 목적지까지 가기 위해 직진하다가 경로를 꺾어야(Steer) 하는 지점을 찾아준다. 더 이상 경로를 꺾을 것도 없이 직진만 해도 목표지점에 도달할 수 있다면 endOfPath가 참 값이 된다.
만약 경로를 꺾어야 하는 지점이 네비게이션 메시 바깥에 존재한다면 offMeshConnection이 참 값이 된다.
// Find movement delta.
float delta[3], len;
dtVsub(delta, steerPos, iterPos);
len = dtMathSqrtf(dtVdot(delta, delta));
// If the steer target is end of path or off-mesh link, do not move past the location.
if ((endOfPath || offMeshConnection) && len < STEP_SIZE)
len = 1;
else
len = STEP_SIZE / len;
float moveTgt[3];
dtVmad(moveTgt, iterPos, delta, len);
먼저 전환점(steerPos)과 현재위치(iterPos)의 변위벡터(delta)를 구한 다음, 이로부터 현재위치와 전환점 사이의 거리(len = dtMathSqrtf(dtVdot(delta,delta)))를 구한다. 그리고 현재위치로부터 변위벡터 방향으로 보폭(STEP_SIZE)만큼 떨어진 곳을 이동대상지점(moveTgt)으로 정한다. 목표 경유지까지 딱 한걸음만 이동하려는 것이다. 만약 거리가 보폭보다 짧다면 딱 전환점까지만 이동한다.
// Move
float result[3];
dtPolyRef visited[16];
int nvisited = 0;
m_navQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &m_filter,
result, visited, &nvisited, 16);
npolys = fixupCorridor(polys, npolys, MAX_POLYS, visited, nvisited);
npolys = fixupShortcuts(polys, npolys, m_navQuery);
float h = 0;
m_navQuery->getPolyHeight(polys[0], result, &h);
result[1] = h;
dtVcopy(iterPos, result);
이제 네비게이션 쿼리의 moveAlongSurface 함수를 호출하면 목표위치로 이동을 시도하고, 이동이 끝난 좌표를 result에 저장한다. 길을 찾아 진행하는 과정에서 어떤 네비게이션 폴리곤들을 탐색하였는지에 대한 결과를 visitied,nvisited 변수로 받아온다. fixupShortcuts 함수는 탐색된 경로에 유턴이 없는지 확인하고 수정한다. fixUpCorridor도 유사하게 잘못된 경로를 수정하는 역할인 것 같은데, 정확하게 뭔지는 모르겠다.
// Handle end of path and off-mesh links when close enough.
if (endOfPath && inRange(iterPos, steerPos, SLOP, 1.0f))
{
// Reached end of path.
dtVcopy(iterPos, targetPos);
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
}
break;
}
만약 경로의 끝(endOfPath)에 도달했다면 현재위치를 종착점으로 바꾸고 반복문을 종료한다.
else if (offMeshConnection && inRange(iterPos, steerPos, SLOP, 1.0f))
{
// Reached off-mesh connection.
float startPos[3], endPos[3];
// Advance the path up to and over the off-mesh connection.
dtPolyRef prevRef = 0, polyRef = polys[0];
int npos = 0;
while (npos < npolys && polyRef != steerPosRef)
{
prevRef = polyRef;
polyRef = polys[npos];
npos++;
}
for (int i = npos; i < npolys; ++i)
polys[i-npos] = polys[i];
npolys -= npos;
// Handle the connection.
dtStatus status = m_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, startPos, endPos);
if (dtStatusSucceed(status))
{
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], startPos);
m_nsmoothPath++;
// Hack to make the dotted path not visible during off-mesh connection.
if (m_nsmoothPath & 1)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], startPos);
m_nsmoothPath++;
}
}
// Move position at the other side of the off-mesh link.
dtVcopy(iterPos, endPos);
float eh = 0.0f;
m_navQuery->getPolyHeight(polys[0], iterPos, &eh);
iterPos[1] = eh;
}
}
만약 다음 목표지가 현재 탐색중인 폴리곤 바깥에 존재한다면(offMeshConnection) 현재 폴리곤을 다음 경유 폴리곤으로 바꾼다.
// Store results.
if (m_nsmoothPath < MAX_SMOOTH)
{
dtVcopy(&m_smoothPath[m_nsmoothPath*3], iterPos);
m_nsmoothPath++;
}
반복문의 마지막 단계에서는 경유지 포인트의 정보를 m_moothPath로 지정한다. 이 코드 이후는 얻어낸 경유지마다 디버그 그래픽스 객체를 그리는 내용이다.
4. 요약
전체 프로세스를 간략하게 표시하면 이렇게 된다.
다음 글에서는 detour 군집(dtCriwd)에게 이동 명령을 내렸을 때 이 주체들이 어떻게 각자 충돌 크기를 가지고 실시간으로 경로를 계산하며 이동하는지 확인해보겠다.
'자체엔진 Yunuty > RecastNavigation' 카테고리의 다른 글
자체 게임 엔진에 RecastNavigation 이식하기 (0) | 2023.11.01 |
---|---|
RecastNavigation - Detour Crowd의 분석 (0) | 2023.10.25 |
RecastNavigation 경로맵 빌드 코드의 분석 (0) | 2023.10.19 |