몬스터에 A* 알고리즘 적용관련 최적화

 

A* 알고리즘 

길찾기 알고리즘. 터레인에 임의의 개수,위치의 노드를 배치하고 알고리즘을 적용하여 벡터에(벡터든 다른 컨테이너든) 타겟까지의 노드들을 순서대로 저장 후 참고하여 이동.

PatrolState는 목표지점이 한번 정해지면 그 지점에 갈때까지 목표지점이 바뀔일이 없기 때문에(다른 State로 바뀌는게 아니라면) 목표지점에 도착할 때마다 새 목표지점에 대해 한번만 경로갱신해주면 된다.

  그러나 StalkingState같은 경우는 실시간으로 움직이는 대상에 대해 이동하기 때문에 경로갱신도 일정주기로 해줘야한다. 그냥 프레임단위로 실행해버리면 바로바로 경로가 업데이트되니 보기엔 좋아보이지만, 당연히 그만큼 cpu자원을 많이 먹기 때문에 프레임이 떨어진다. 그래서 개발자가 원하는 임의의 시간단위로 경로갱신해주기 위해 따로 함수를 만들어서 적용했다.

void ExecuteAStarUpdateFunction(function<void(Vector3)> funcPointer, Vector3 param1, float periodTime); 

그냥 콜백함수를 이용한 지극히 간단한 일정주기실행 함수이다. (sleepAndExecute)
param1은 funcPointer가 사용할 매개변수이고 periodTime은 몇초단위로 실행할지에 대한 float값이다.

어쨌든 이렇게 만들고 적용했더니 문제가 발생했다. 실행주기를 1초로 설정해놓고 터레인에 노드를 적당히 일정간격으로 지형상관없이 배치해놓고 실행했더니 몬스터가 대각선상의 노드를 이동할때 제대로 이동하지 못하고 바로 이전노드를 다시 왔다갔다하는 문제가 발생했다. 
 
-> 다음 노드까지 거리의 절반을 가기전에 경로갱신이 될 경우, 가까운노드를 찾아가는 특성상 다시 출발한 노드로 이동. 좀 더 상황설명을 하자면, 현재 객체가 위치해있는 노드가 1번, 타겟노드(다음 이동할 노드)가 2번이라고 가정할 시 2번노드까지 절반이상 걸어가기전에 새로 경로갱신이 될 경우 타겟노드가 현 위치에서 가장 가까운 노드가 선택되어지고(1번노드가 다시 선택되어짐) 결국 2번노드를 가지못하고 사이에서 왔다갔다 반복.
 

방안 1. 노드를 좀 더 빽빽이 배치한다.
            -> 좋지 않은방법이다.  게임기획상,혹은 성능상 노드를 띄엄띄엄 배치해야 하는 경우도

                충분히 있기 때문. 노드를 빽빽이 배치해야한다는 상황을 강제한다는 것 자체가

                잘못 코딩한것 같다. 필요이상으로 노드를 배치할경우 경로계산하는 비용도 증가한다.
 
방안 2. 객체이동속도를 증가시킨다.
             -> 1과 거의 동일한 이유로 좋지 않은 방법이다.
                 인게임오브젝트의 설정값을 강제해서 버그를 고친다는건 좋지 않다.

                 애초에 오류를 해결하는게 아니라 가리는 방법이다.

방안 3. 타겟노드까지 강제로 이동시키고 경로갱신을 한다.
           ->  타겟노드까지의 방향벡터를 계속 가지고 있다가 그 방향벡터의 반대방향벡터(                                      currentTargetNodeDir * -1.0f)가 될 경우, 위와 같은 문제가 발생했다고 가정하고 강제로

                타겟노드까지 이동시키게 한다. 
                강제이동시에는 경로갱신을 못하게 잠깐 막아놓는다. 타겟노드까지 이동을 마치면 열어놓는다.


일단 방안3로 임시로 해결하긴 했다. 

임시로 해결했다고 말하는 이유는, 일단 타겟노드까지는 강제로 이동을 하기때문에 인게임내에서 좀 어색해보일 수 있다. 그리고 위의 버그외에도 자잘한 버그까지 포함해서 코드를 고쳤더니 다른 작은 버그가 또 생겨났다.

 

나중에 다시 이부분을 고치려고 할 때 잊어버릴걸 대비해 적어놓는다. 이부분은 무시해도 좋다.

객체가 타겟을 향해 일직선으로 달려올 때 (mPath.size() == 1) 로테이션을 1번만 실행시키기 위해 경로갱신을 할때마다 mPath.size() 만큼 bool Vector에 따로 체크해두고 true일때만 회전시키고 false로 변경(각

노드당 한번씩만 회전시키기 위함)

-> DirectPath로 바뀔경우 Rotation이 실행 안되는경우가 있음. 아마 방안3하는 과정에서 mPath 내용물이 변경되는데 그 과정에서 bool         Vector와 매치가 잘 안되서 그런것같다.                      

 

 

 

포폴관련된 글에는 아마 내 능력부족에 대한 글이 많이 올라올것같다. 

그래도 나중에 비슷한 실수를 안하려면 남겨놔야할 것 같아서 남긴다.