문제 정의

• 즉 경로를 찾기 위해 방문하는 노드의 수가 증가된다는 것이다. 본 논문에서는 기존의 휴리스틱보다 정보가 많은 두 가지 휴리스틱(more informed heuristic)을 고안함으로서 A*의 탐색 성능을 향상시켜서 빠른 전술적 경로찾기가 가능하도록 한다. 시뮬레이션을 통해 제안된 두 가지 휴리스틱과 기존의 휴리스틱과의 탐색 성능 차이를 비교하고 각 휴리스틱의 장단점을 분석한다.
• RPG(Role Playing Game) 게임에서 지도 제작을 위한 편집기들은 대부분 그리드-기반 혹 셀-기반이다. 본 논문에서는 시뮬레이션을 위해 이들 편집기와 유사하게 그리드-기반 환경을 자바로 구현하였다. 편집기에서는 게임배경을 만들고 수정할 수 있으며 장애물과 위협 요소의 위치에 따라 위치 평가 함수가 계산되고 휴리스틱을 선택하여 경로를 계획할 수 있다.
• 이에 대한 해결책으로서 NPC의 동작 영역을 제한하거나 계층적 탐색을 통해 탐색 상태공간을 줄이려는 시도를 하였고 과소 추정 휴리스틱의 본질을 이용하여 탐색 효율을 개선하고자 하지 않았다. 본 논문에서는 직선 거리 휴리스틱, h(n) = dist(n,g)보다 큰 휴리스틱, h₁(n)과 h₂(n), 두 가지를 소개하고 각 휴리스틱의 최적성과 탐색 효율에 대해 논한다. f_i(n)은 노드 n의 i번째 특성을 나타내며 m개의 특성이 있다고 가정한다.
• 이와 같은 이유로 전술적 경로찾기를 구현하거나 다룬 게임과 문헌들에서 전술적 경로찾기의 문제점으로 탐색 효율의 저하를 지적하고 있다. 이에 대한 해결책으로서 NPC의 동작 영역을 제한하거나 계층적 탐색을 통해 탐색 상태공간을 줄이려는 시도를 하였고 과소 추정 휴리스틱의 본질을 이용하여 탐색 효율을 개선하고자 하지 않았다. 본 논문에서는 직선 거리 휴리스틱, h(n) = dist(n,g)보다 큰 휴리스틱, h₁(n)과 h

  제안 방법

  • 거리 이외의 특성으로는 위협으로부터의 거리, 지형 종류, 벽 껴안기(wall-hugging) 성질 등, 3가지를 고려하였으며 이동 거리를 고려한 비용함수와 비례하기 위해 작은 값을 선호하도록 값을 할당하였다. 자세한 점수 할당은 그림 1에 소개한 바와 같다.
  • 지형 정보는 일반 땅에 비해 좌측 상단의 얼음 부분과 우측 하단의 숲은 각각 15, 18점의 높은 값이 할당되었다. 벽 껴안기(wall-hugging)는 벽에 너무 가까운 경우에 이동 경로로서 어색하므로 이를 고려하여 3단계로 점수를 할당하였으며 세 번째 그림은적(ENEMY)으로부터 가까울수록 높은 값을 할당하였다. 
  • 본 논문에서는 기존의 휴리스틱보다 정보가 많은 두 가지 휴리스틱(more informed heuristic)을 고안함으로서 A*의 탐색 성능을 향상시켜서 빠른 전술적 경로찾기가 가능하도록 한다. 시뮬레이션을 통해 제안된 두 가지 휴리스틱과 기존의 휴리스틱과의 탐색 성능 차이를 비교하고 각 휴리스틱의 장단점을 분석한다.
  • 위치 평가 함수 사용의 효율성을 위해 제안한 두 가지 휴리스틱 h1(n)과 h2(n)에 의해 개선된 정도를 에 정리하였다.