개발일기 - 길찾기 최적화

두나리버스에서 길찾기로직은 A*를 사용합니다.

각 유닛은 레벨에 따라 다른 thinkStep을 갖게됩니다. 1.0에서 0.4 까지 변합니다.

만약 thinkStep이 1.0이라면 1초에 한번씩 생각을 합니다.

적이 무기 사정거리안에 있는지

시야 안에 적 유닛이 있는지

시야 안에 적 타워가 있는지

시야 안에 아이템이 있는지

등등

우선순위에 따라 행동을 하게됩니다. 이 안에서 길찾기를 사용하게됩니다.

예를들어 시야안에 적이 들어왔다고 생각해봅시다. 

적을 향해 이동해야 합니다. 

내 위치와 적 위치를 길찾기 매니져에게 알려주고 해당 경로가 열려있는지(경로가 존재하는지)와 열려있다면 어떠한 좌표들의 모음으로 가야 하는지를 반환해줍니다.

길찾기 매니져는 이러한 요청을 큐에 담아놓고 처리하는대로 결과를 반환해 줍니다.

가까운 목적지에 길찾기하면 빠른시간안에 결과를 받지만 멀리 있는 목적지에 길찾기를 하면 훨씬 많은 시간이 필요합니다.

8개의 유닛(아군 유닛만 우선 고려합니다. 물론 적 유닛도 길찾기를 합니다)이 길찾기를 하면 8개의 길찾기 요청이 들어오고 이 길찾기를 제때처리하지못하면 요청이 큐에 잠시 쌓였다가 처리되게 됩니다.

유닛들은 결과가 돌아오기전까지는 멈추어있기 때문에 이동했다가 잠시 멈춰있는 현상이 나타납니다. 이러한 현상은 유닛이 많고 목적지까지의 경로가 길수록 명확하게 나타납니다.

해결방법에 대한생각

길찾기를 매번 하는게 아니라 한번해놓고 캐싱해놓고 쓰면 어떨까?

• 길 경로에 위치하는 유닛이나 건물등이 동적으로 바뀌므로 경로도 매번 달라져야 한다.

먼 목표를 가는것이 아니라 미리 지정해놓은 몇개의 목표를 순차적으로 이동하는 마커를 추가한다.

• 그나마 이게 맞는 방법같다. 잘 구현된 길찾기 로직은 경로를 그래프로 만들어서 모서리 지점같은것을 노드로 설정하고 그것을 이용해 최적화를 하는것 같더라.
• 자동으로 노드를 만들어내는것까지는 무리겠지만 복잡한 맵에 한해서 수동으로 몇개의 노드를 추가해주는것은 괜찮은 생각인 것 같다.

마커를 추가 한 후에 눈에 띄는 성능 향상은 이루어지지 않았다.

A*알고리즘에서 물이퍼져나가듯이 목표지점을 탐색하게 되는데 이 물이 퍼지는 방향에 대해서는 별도로 지정해준 바가 없다.

비교적 가까운 위치라 하더라도 엉뚱한 방향으로 먼저 탐색을 하다가 나중에서야 목표지점을 찾게되는 경우가 많은 듯 하다.(추정)

결국 길찾기 요청 횟수를 줄이는 방법을 찾아야 한다.

길찾기 결과 얻어진 경로를 캐싱하여 사용해야 한다. 

일단 자고 내일 계속하자...