A Pathfinding Algorithm Using Path Information

(1)

게임 프로그래밍

경로 정보를 이용한 길찾기 알고리즘^※

조성현 홍익대학교 게임학부

[email protected]

A Pathfinding Algorithm Using Path Information

Sung Hyun Cho

School of Games, Hongik University

요 약

A* 알고리즘은 잘 알려진 길찾기 알고리즘이다. 그러나 많은 상호 작용이 있거나 많은 장애 물들이 있는 맵에서 A* 알고리즘을 실시간에 사용하는데 한계가 있을 수 있다. 그래서 게임에 서는 최단의 경로를 찾는 대신에 게임 플레이어에게 자연스럽게 보이는 경로를 빠르게 찾을 필 요가 있다. 본 논문에서는 경로 정보를 사용하는 새로운 휴리스틱 함수를 제안하고, 제안한 휴 리스틱 함수를 이용한 길찾기 알고리즘이 다양한 그리드 맵에서 A* 알고리즘보다 상당히 빠르 게 경로를 찾을 수 있다는 것을 보여준다.

ABSTRACT

A* algorithm is a well known pathfinding algorithm. However, there may be a limit to use A* algorithm in real-time in a map where many interactions occur between objects or many obstacles exist. Therefore, it may be necessary to find a naturally looking path quickly instead of finding a shortest path in games. In this paper, we propose a new heuristic function to exploit path information in a map. We also show that the pathfinding algorithm based on the proposed heuristic function can find a good path much faster than A* algorithm on several grid maps.

Keywords : A* Algorithm, Pathfinding, Heuristic Function

※ 본 논문은 2010년도 홍익대학교 학술연구진흥비에 의하여 지원되었음.

Received: Jan. 14, 2013 Accepted: Jan. 29, 2013 Corresponding Author: Sung Hyun Cho(Hongik University) E-mail: [email protected]

ISSN: 1598-4540 / eISSN: 2287-8211

Ⓒ The Korea Game Society. All rights reserved. This is an open-access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.otg/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

(2)

1. 서 론

많은 게임에서 PC(player character)와 NPC (non-player character)를 위하여 길찾기 알고리즘 을 사용하고 있다. 특히 실시간 전략 게임에서는 서로 상호작용하는 많은 수의 NPC들이 각기 길찾 기 기능이 필요할 것이다. A* 알고리즘은 게임과 같은 가상세계에서 길찾기를 위하여 가장 널리 사 용되고 알고리즘이다[1].

A* 알고리즘은 휴리스틱(heuristic) 방법을 가장 효율적으로 사용하는 것으로 알려져 있다. 즉, 동 일한 비용을 가진 노드들 사이의 동점처리를 고려 하지 않는다면, 휴리스틱 함수가 동일할 때 A* 알 고리즘보다 더 적은 수의 노드들을 검색해서 최적 의 경로를 찾아낼 수 있는 검색 알고리즘은 없다 고 알려져 있다[2,3].

A* 알고리즘은 큰 사이즈의 맵에서는 열린 목 록과 닫힌 목록에 많은 노드가 삽입과 삭제가 되 기 때문에 많은 메모리 공간이 필요하고 검색시간 도 많이 걸린다[1]. 이런 경우에 실시간에 경로를 찾기 위하여 계층적으로 경로를 찾아야 할 것이다.

상위 계층에서 최적의 경로를 찾았다고 하더라도 하위 계층까지 고려하면 찾은 경로가 최적이 아닐 수 있다. 그리고 자원의 성능이 떨어지는 게임 환 경에서 최적의 경로보다는 게임 플레이어에게 자연 스럽게 보이는 경로를 빠르게 찾는 알고리즘이 필 요할 수도 있을 것이다.

최근에 PC들의 이동 경로를 실시간에 샘풀링하 여 항해메시(navigation mesh)를 생성하는 방법이 제안되었다[4]. 이 방법에서 생성된 PC들의 이동경 로 에 대한 정보를 활용하여 슈팅 게임에서 NPC 가 PC를 추적한다면 훨씬 흥미진진한 게임을 제작 할 수 있을 것이다. 또는 기획자가 NPC의 이동경 로 정보를 사전에 툴을 사용하여 입력할 수도 있 을 것이다. 본 논문에서는 경로 정보를 사용하여 길찾기를 빨리할 수 있는 방법을 제안하고자 한다.

본 논문에서는 경로 정보를 이용하여 빠르게 길 찾기를 할 수 있도록 새로운 휴리스틱 함수를 제

안하고, 이 휴리스틱 함수를 사용하는 A* 알고리 즘을 PIA* (Path Information based A*) 알고리 즘이라고 부른다. 실험을 통하여 본 논문에서 제안 하는 PIA* 알고리즘의 성능(찾은 경로의 질과 시 간)을 A* 알고리즘과 비교한다. 본 논문의 구성은 다음과 같다. 2절에서 관련 연구를 기술하고, 3절 에서 본 논문에서 제안하는 휴리스틱 함수를 설명 하고, 4절에서 실험 결과와 분석을 기술하고, 5절 에서 결론과 미래의 연구 방향을 논한다.

2. 관련 연구

2.1 길찾기 알고리즘

길찾기는 출발노드에서 목표노드까지 장애물을 피하고, 적군을 피하며, 이동비용(연료, 시간, 거리, 비용 등)을 최소화하는 좋은 경로를 찾는 문제이다 [1,5].

현재까지 IDA* 알고리즘과 D* 알고리즘과 같 은 A* 알고리즘을 기반으로 하는 많은 연구가 진 행되었다[6,7,8]. 큰 사이즈의 맵에서 최적의 경로 는 아니지만 빠르게 계산하기 위하여 계층적으로 경로를 찾는 방법도 제안되었다[9]. 그 외에도 동 적인 맵에서 경로를 찾는 방법들이 제안되었으며 [8,10,11], 다중 출발노드와 다중 목표노드가 있는 경우에 길찾기도 연구되었고[12], 유전자 알고리즘 을 기반으로 하는 여러 가지 길찾기 알고리즘도 연구되었다[13].

2.1.1 Dijkstra 알고리즘

Dijkstra 알고리즘은 출발노드에서 시작하여 가 까운 노드부터 시작하여 모든 방향으로 확장해 가 며 그래프에 있는 노드들을 방문하여 목표노드까지 의 경로를 찾는다. Dijkstra 알고리즘은 비효율적 이지만 출발노드에서 목표노드까지 항상 최단의 경 로를 찾을 수 있다는 장점이 있다[1,2].

(3)

2.1.2 Best-First-Search

탐욕적인 Best-First-Search도 Dijkstra 알고리 즘과 비슷하게 동작하지만 임의의 노드에서 목표노 드까지 거리가 얼마나 되는지 휴리스틱 추정치를 사용한다. 출발노드에서 가장 가까운 노드를 선택 하는 대신에 목표노드에 가장 가까운 노드를 선택 한다. Best-First-Search 알고리즘은 목표노드에 이르는 경로를 안내하는 휴리스틱 함수를 사용하기 때문에 Dijkstra 알고리즘보다 훨씬 빠르게 수행하 지만, 최단 경로를 보장하지는 못한다. 장애물이 없는 맵에서 최단 경로는 출발노드에서 목표노드까 지의 직선이며, Best-First-Search는 한 방향으로 검색하기 때문에 모든 방향을 검색하는 Dijkstra 알고리즘 보다 빠르게 수행한다[1,5,14].

2.1.3 A* 알고리즘

Dijkstra 알고리즘과 Best-First-Search의 장점 을 이용하여 A* 알고리즘은 고안되었다[1,2,5]. 일 반적으로 휴리스틱 방법은 최선의 해를 제공하지 못하고 근사적인 해를 제공한다. 그러나 A* 알고 리즘은 휴리스틱 방법에 기초하여 설계되었지만, 최단 경로를 보장한다[2].

A* 알고리즘에서 g(n)은 출발노드에서 임의의 노드 n까지 경로의 비용이고, h(n)은 노드 n에서 목표노드까지 비용의 휴리스틱인 추정치로 총비용 은 f(n) = g(n) + h(n)이다. A* 알고리즘은 출발 노드에서 목표노드로 이동하면서 g(n)과 h(n)을 이 용한다. [Fig. 1]은 A* 알고리즘의 유사코드이다.

A* 알고리즘은 while 루프가 반복될 때 마다 현재 노드에 인접한 노드들 중에서 f(n)이 최소인 노드 를 찾아서 그 노드로 이동하는 과정을 반복함으로 써 가장 적은 비용의 최종 경로를 찾는다. 그 노드 는 자신의 부모 노드, 즉 가장 적은 비용으로 자신 에 이르도록 한 노드를 가르키는 포인터를 가진다.

목표노드에 도달한 후에, 그 포인터를 사용하여 목 표까지 이르는 노드들을 출발노드까지 역으로 추적

하여 가장 적은 비용의 경로를 찾는다[1,2].

open – priority queue containing start closed – empty set

while lowest rank in open is not the goal current = remove lowest rank item from open add currrent to closed

for each child of current if child is present in closed continue

else

g(child) = g(current)+cost(current,child) f(child) = g(child) + h(child)

add child to open

set child’s parent to current end for

end while

[Fig. 1] Pseudo A* Algorithm

2.2 A* 알고리즘의 최적화

A* 알고리즘의 속도는 검색 공간의 크기에 크 게 영향을 받기 때문에 검색공간을 최소화하기 위 한 연구가 진행되었으며, 알고리즘 자체의 최적화 를 위하여 메모리 할당과 해제가 자주 발생하기 때문에 메모리 할당과 관리 문제, 그리고 정렬을 빨리 하기 위한 기법들이 연구되었다[15,16].

A* 알고리즘은 현존하는 최고의 검색 알고리즘 이지만, 맵의 크기가 크면 열린 목록과 닫힌 목록 에 많은 노드가 들어갈 수 있기 때문에 메모리와 수행속도에 문제가 있을 수 있다. A* 알고리즘의 가장 근본적인 약점은 열린 목록과 닫힌 목록을 관리하는 비용이다. 이를 극북하기 위하여 열린 목 록과 닫힌 목록을 사용하지 않는 IDA* 알고리즘 이 제안되었다[6,7]. 그러나 IDA* 알고리즘은 깊이 우선 검색을 사용하여 메모리 공간을 적게 사용하 는 대신 노드들을 재 방문해야하는 단점이 있다.

또한 A* 알고리즘과 IDA* 알고리즘 사이에 Fringe 알고리즘이 제안되었으나, Fringe 알고리즘 은 Now 목록과 Later 목록을 사용하기 때문에 많 은 메모리가 필요하다는 단점이 있다[7].

(4)

3. 휴리스틱 함수

휴리스틱 함수 h(n)은 임의의 노드 n에서 목표 노드까지 비용을 추정하는 함수로 A* 알고리즘에 서 f(n)이 최소인 노드를 먼저 검색한다. 좋은 휴 리스틱 함수를 선택하는 것이 중요하지만, 일반적 으로 좋은 휴리스틱 함수를 미리 알 수가 없다. 그 래서 임의의 노드에서 목표노드까지의 비용 h(n)를 추정하게 된다.

3.1 휴리스틱 추정치

A* 알고리즘에서 h(n)은 다음과 같은 의미가 있다. h(n)의 값이 실제 비용보다 작으면 A* 알고 리즘은 항상 최단경로를 찾을 수 있지만 수행속도 가 늦어지고, 반대로 h(n)의 값이 실제 비용보다 큰 경우에는 A* 알고리즘은 항상 최단 경로를 찾 을 수 있는 것은 아니지만 수행속도가 빨라진다 [2,14]. 그래서 최적의 경로를 찾기 위해서는 휴리 스틱 추정치가 실제 비용보다 크면 안 된다. 실제 비용보다 크지 않은 추정치를 구하는 일반적인 방 법은 주어진 노드로부터 목표까지의 맵에서 최단거 리에 단위 거리 당 통과하는데 필요한 최소 비용 을 곱하는 것이다[1].

게임에서 이러한 A* 알고리즘의 특성을 유용하 게 이용할 수 있다. 게임에서 많은 경우에 최단 경 로보다는 자연스럽게 보이는 경로를 빠르게 찾는 것을 선호할 수도 있기 때문이다[1,5]. 본 논문에서 는 h(n)을 직선보다 더 짧은 거리를 가진 경로는 없기 때문에 유크리드 거리를 사용한다.

3.2 제안하는 휴리스틱 함수

A* 알고리즘의 열린 목록은 우선순위 큐로 관 리하고 f값이 작은 노드들을 먼저 검색한다. 맵에 장애물이 없는 경우에는 직선거리가 최단 거리이기 때문에 현재 노드에서 목표노드 쪽으로 위치한 노 드의 f값이 제일 작기 때문에, 우선순위 큐에서 앞 에 위치하게 되고 따라서 먼저 검색하게 된다. 그

러나 장애물이 있는 경우에는 어느 방향으로 움직 이는 것이 좋을지 알 수가 없기 때문에 노드의 h 값을 어떻게 설정하여야 하는지를 알 수 없다.

본 논문에서는 경로 정보가 이미 있다고 가정한 다. 일반적으로 경로 정보는 기획자가 콘텐츠의 내 용에 따라서 툴을 이용하여 입력하거나, PC들이 어느 그리드를 많이 통과하는지 실시간에 시스템에 서 자동으로 수집한다고 가정한다[4]. 그러나 이 정보는 정확한 정보가 아닐 수 있기 때문에 경로 를 찾을 때 참고자료로 활용하고, 경로 정보가 잘 못 설정된 경우에는 그 정보를 무시할 수 있어야 한다.

본 논문에서는 휴리스틱 함수 h(n)을 아래 (eq.

1)과 같이 수정하여 새로운 휴리스틱 함수 h’(n)을 사용할 것을 제안한다.

h’(n) = h(n) - λ*w(n) (eq. 1)

(eq. 1)에서 w(n)은 노드의 경로 정보이다.

w(n)의 값이 크면 클수록 그 노드를 통과하여 이 동하는 것이 경로를 찾는데 도움이 될 가능성이 크다고 가정한다. λ을 0으로 설정하면 h’(n) = h(n)이기 때문에 기존 A* 알고리즘과 같고, λ이 0 이 아닐 경우에는 h(n)에서 λ*w(n)의 값을 빼게 되어 h’(n)이 h(n)보다 작아지게 된다.

w(n)이 크면 클수록 h’(n)의 값이 작아지게 되 고, f(n) = g(n) + h’(n)이기 때문에 f(n)의 값도 작아지게 되며 따라서 그 노드를 먼저 검색하게 된다. 그래서 경로 정보가 목표노드 방향으로 유도 하는 경우에는 노드의 검색을 크게 줄일 수 있다.

그러나 잘못 유도하는 경로 정보일지라도 이 정보 를 참고자료로 사용하기 때문에 그에 따른 희생(노 드 검색)이 크지 않다는 것을 4장 실험결과가 보여 준다.

λ는 스케일 상수이며, (eq. 1)의 목적은 w(n) 값이 큰 노드를 먼저 검색하도록 하는 것이 목적 이기 때문에 g값과 h값의 균형이 깨지지 않도록 λ 는 작은 값으로 설정하면 된다.

(5)

4. 실험 결과

4.1 실험 환경

A* 알고리즘은 루프를 반복할 때마다 노드를 검색하는데, 이 때 열린 목록에서 하나의 노드가 제거되어 닫힌 목록에 삽입된다. A* 알고리즘이 끝났을 때 닫힌 목록에 있는 노드는 열린 목록에 남아있는 노드보다 많은 처리시간이 소모되므로, 본 논문에서는 닫힌 목록에 있는 노드의 수, 즉 검 색한 노드의 수로 알고리즘의 성능을 판단한다.

실험에서 간단한 경우에는 32×20 그리드 맵, 복 잡한 경우에는 40×30 그리드 맵을 사용하였으며, λ의 값은 0.001로 설정하였고, w(n)의 값은 간단 히 1 또는 0으로 제한하여 설정하였다. 그리고 그 리드의 한 변의 길이는 1이라고 가정하여, 대각선 거리는 1.44가 된다.

실험결과에서 출발노드는 왼편에 캐릭터로 표시 되고, 목표노드는 오른편에 X로 표시되며, 출발노 드에서 목표노드 X까지 선분은 찾아낸 경로를 표 시한다. 검정색 사각형은 장애물을 표시하고, 회색 사각형은 w값이 1인 노드로 경로 찾기에 우선적으 로 검색되는 노드이다.

본 논문에서 제안하는 휴리스틱 함수 h’(n)을 사 용하는 A* 알고리즘을 PIA* (Path Information Based A*) 알고리즘이라고 부른다. 모든 노드의 w값이 0인 경우에 PIA* 알고리즘은 기존의 A*

알고리즘과 동일한 알고리즘이 된다.

4.2 실험 결과

4.2.1 막대형태의 장애물이 있는 맵

[Fig. 2](a), (b), (c)는 단순한 막대형태 장애물 이 출발노드와 목표노드 사이에 있는 맵(MAP1)에 서 A* 알고리즘과 PIA* 알고리즘이 찾아낸 경로 를 보여 준다.

[Table 1]에서 첫 번째 열은 알고리즘의 종류, 두 번째 열은 찾아낸 경로의 거리, 세 번째 열은

검색한 노드의 수, 네 번째 열은 PIA* 알고리즘이 찾아낸 경로의 거리를 A* 알고리즘이 찾아낸 경로 의 거리로 나눈 값으로 찾은 경로의 질을 의미하 며, 다섯 번째 열은 A* 알고리즘이 검색한 노드의 수를 PIA* 알고리즘이 검색한 노드의 수로 나눈 값으로 알고리즘의 성능을 의미한다.

[Table 1]은 A* 알고리즘과 PIA* 알고리즘의 성능을 보여준다. 테이블의 2번째와 3번째 줄은 [Fig. 2](b), (c)에서와 같이 경로 정보가 다른 경 우의 실험결과이다. PIA* 알고리즘이 찾은 경로의 질이 A* 알고리즘보다 13% 열등하지만, 수행시간 은 1.60∼2.64배 빠르다. [Fig. 2](c)는 위쪽과 아래 쪽에 대칭으로 경로 정보가 있어서 길찾기에 혼란 을 초래하기 때문에 [Fig. 2](b)보다 훨씬 많은 검 색을 하지만 A* 알고리즘보다는 좋은 성능을 보여 준다. 그러나 오른쪽 아래 부분에 추가되어 있는 경로 정보는 길찾기에 영향을 주지 않는다.

(a) Pathfinding of A* in MAP1

(b) Pathfinding of PIA* in MAP1 with Partial Path Information

(6)

(c) Pathfinding of PIA* in MAP1 with Confusing Path Information

[Fig. 2]

[Table 1] Performance Comparison in MAP1

Algorithm Path Length

No. of Search

Quality

of Path Performance

A* 26.28 182 1.00 1.00

PIA* (1) 29.64 69 1.13 2.64

PIA* (2) 29.64 114 1.13 1.60

4.2.2 오목한 형태의 장애물이 있는 맵

[Fig. 3](a), (b), (c)는 오목한 형태의 장애물이 출발노드와 목표노드 사이에 있는 맵(MAP2)에서 A* 알고리즘과 PIA* 알고리즘이 찾아낸 경로를 보여 준다. [Table 2]는 A* 알고리즘과 PIA* 알 고리즘의 성능을 보여준다.

PIA* 알고리즘이 찾은 경로의 질이 A* 알고리 즘보다 13%∼23% 열등하지만, 성능 즉 수행시간 은 1.55∼2.42배 빠르다는 것을 알 수 있다.

[Fig. 3](c)는 부분적인 정보를 사용하기 때문에 [Fig. 3](b) 보다 시간은 더 걸리지만 질이 더 좋 은 길을 찾는다는 것을 보여준다.

[Table 2] Performance Comparison in MAP2 Algorithm Path

Length

No. of Search

Quality

of Path Performance

A* 24.96 157 1.00 1.00

PIA* (1) 30.76 65 1.23 2.42

PIA* (2) 28.08 101 1.13 1.55

(b) Pathfinding of PIA* in MAP2 with Complete Path Information

(c) Pathfinding of PIA* in MAP2 with Partial Path Information

[Fig. 3]

4.2.3 돌연변이 4 형태의 장애물이 있는 맵

[Fig. 4](a), (b), (c)는 돌연변이 4 형태의 장애 물이 출발노드와 목표노드 사이에 있는 맵(MAP3) 에서 A* 알고리즘과 PIA* 알고리즘이 찾아낸 경 로를 보여준다.

(7)

[Table 3]은 PIA* 알고리즘이 찾은 경로의 질 이 A* 알고리즘보다 15% 열등하지만, 성능 즉 수 행시간은 0.99∼2.45배 빠르다는 것을 알 수 있다.

(c) Pathfinding of PIA* in MAP3 with Misleading Additional Path Information

[Fig. 4]

[Fig. 4](a)에서 A* 알고리즘은 목표노드가 출 발노드보다 아래쪽에 위치하여 처음에는 아래 방향 으로 검색을 진행하다가 나중에 위쪽으로 경로를

찾기 때문에 검색이 오래 걸린다. [Fig. 4](c)에서 는 아래쪽에 경로 정보가 있기 때문에 [Fig. 4](a) 보다 아래쪽으로 더 검색을 진행하기 때문에 PIA*

알고리즘이 A* 알고리즘보다 시간이 더 걸릴 수 있다는 것을 보여준다.

[Table 3] Performance Comparison in MAP3

Algorithm Path Length

No. of Search

Quality

of Path Performance

A* 26.72 272 1.00 1.00

PIA* (1) 30.64 111 1.15 2.45

PIA* (2) 30.64 274 1.15 0.99

4.2.4 회전된 F 형태의 장애물이 있는 맵

[Fig. 5] (a), (b), (c)는 회전된 F 형태의 장애 물이 출발노드와 목표노드 사이에 있는 맵(MAP4) 에서 A* 알고리즘과 PIA* 알고리즘이 찾아낸 경 로를 보여준다.

[Table 4]는 A* 알고리즘과 PIA* 알고리즘의 성능을 보여준다. PIA* 알고리즘이 찾은 경로의 질이 A* 알고리즘보다 23%∼30% 열등하지만, 성 능 즉 수행시간은 1.82∼3.75배 빠르다는 것을 알 수 있다.

[Fig. 5] (c)은 처음에 잘못된 경로 정보를 사용 하여 오른쪽으로 이동하다가 위쪽으로 이동하기 때 문에 [Fig. 5] (b)의 경우보다 찾은 경로의 질과 성능이 떨어진다.

(8)

(c) Pathfinding of PIA* in MAP4 with Incorrect Additional Path Information

[Fig. 5]

Length

No. of Search

Quality

of Path Performance

A* 21.72 135 1.00 1.00

PIA* (1) 26.76 36 1.23 3.75

PIA* (2) 28.20 74 1.30 1.82

4.2.5 실제적인 맵

[Fig. 6] (a), (b), (c)는 실제 상황에 가까운 40×30 게임 맵(MAP5)에서 A* 알고리즘과 PIA*

알고리즘이 찾아낸 경로를 보여준다. [Table 5]는 PIA* 알고리즘이 찾은 경로의 질이 A* 알고리즘 보다 1%∼7% 열등하지만, 성능 즉 수행시간은 6.06∼6.72배 빠르다는 것을 알 수 있다.

[Fig. 6] (c)는 위쪽에 제공된 경로 정보를 이용

하여 오른쪽으로 이동하다가 아래쪽으로 이동하기 때문에 [Fig. 6] (b)의 경우보다 찾은 경로의 질은 떨어지지만 성능은 더 좋다. [Fig. 6] (c)에 두 가 지 경로 정보가 같은 방향이기 때문에 성능이 개 선되었으나, [Fig. 2] (c), [Fig. 4] (c), [Fig. 5]

(c)에서는 경로 정보가 다른 방향으로 향하기 때문 에 수행시간과 경로의 질에 부정적인 영향이 있다.

(c) Pathfinding of PIA* in MAP5 with Additional Path Information

[Fig. 6]

(9)

Length

No. of Search

Quality

of Path Performance

A* 60.72 685 1.00 1.00

PIA* (1) 61.28 113 1.01 6.06

PIA* (2) 65.20 102 1.07 6.72

특히 A* 알고리즘은 685개의 노드를 검색한 후 에 경로를 찾아내기 때문에 실시간에 성능이 떨어 지는 자원에서 수행하기에는 부담이 될 수도 있을 것이다.

4.3 실험 결과 분석

[Table 1]∼[Table 5]의 실험 결과를 종합해 보 면 PIA* 알고리즘이 찾아낸 경로의 질은 A* 알고 리즘이 찾아낸 경로에 비교하여 13%∼30% 열등 하지만, 수행시간은 대부분의 경우에 A* 알고리즘 보다 2배 이상 빠르게 경로를 찾는다는 것을 알 수 있다.

특별히 MAP5에서 PIA* 알고리즘이 찾은 경로 의 질이 A* 알고리즘이 찾은 경로의 질과 비교하 여 1%∼7% 열등하지만 거의 A* 알고리즘과 대등 한 수준이고, 수행시간은 6배 이상 빠르다는 것을 알 수 있다.

그러나 경로 정보를 잘못 설정하면 [Table 3]에 서와 같이 PIA* 알고리즘이 질적인 면에서나 시간 적인 면에서 A* 알고리즘보다 열등한 결과를 가져 오기도 한다. 경로 정보의 질에 따라서 PIA* 알고 리즘의 성능이 좌우되기 때문에 양질의 경로 정보 를 설정하는 것이 중요하다.

5. 결 론

본 논문에서는 경로 정보를 활용하여 최적의 경 로는 아니지만 경로를 찾는 시간을 많이 개선할 수 있음을 보여주었다. 출발노드와 목표노드 사이 에 같은 방향으로 한 가지 이상의 경로 정보는 문

제가 되지 않는다. 그러나 다른 방향으로 인도하는 경로 정보가 있는 경우에 길찾기에 혼란이 생겨 성능이 떨어진다는 것을 알 수 있었다. 본 논문에 서는 w(n)의 값을 1 또는 0으로 제한하였기 때문 에, 경로 정보를 가진 모든 노드의 w(n)은 1이었 다. 그러나 w(n)의 값으로 임의의 정수를 허용하 고, 여러 방향의 경로 정보가 있을 때 한 방향으로 선호도를 부여할 수 있도록 그 방향으로 경로 정 보를 가진 노드들의 w(n) 값을 다른 방향의 노드 보다 크게 설정함으로써 혼란을 피할 수 있는지도 연구할 필요가 있다.

경로 정보가 설정된 노드는 그 노드를 통하여 목표노드로 이동하도록 당기는 역할을 하고 있다.

이 아이디어를 기반으로 당기는 힘과 밀어내는 힘 을 이용하여 NPC들이 오목한 장애물에 들어가지 못하게 하거나 갇히지 않도록 하는 방법과 주어진 게임 맵에서 기획자가 양질의 경로 정보를 입력하 는데 활용할 수 있는 가이드라인을 찾아내기 위한 연구도 추가로 필요하다.

ACKNOWLEDGMENT

This work was supported by 2010 Hongik University Research Fund.

REFERENCES

[1] Bryan Stout, “The Basics of A* for Path Planning”, Game Programming Gems, pp.

254-263, Charles River Media, 2000.

[2] P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Trans. Syst.

Sci. Cybernet, 4(2): pp. 100–107, 1968.

[3] Nils J. Nilsson, Artificial intelligence: A New Synthesis, Morgan Kafmann, 1998.

[4] S. J. Kang, Y. O. Kim, and C. H. Kim, “Live Path: Adaptive Agent Navigation in the

(10)

Interactive Virtual World”, The Visual Computer, Vol. 26, No. 6, pp. 467-476, 2010.

[5] Ron Penton, Data Structures for Game Programmers, Premier Press Game Development, pp. 715-767, 2002.

[6] R. Korf, “Depth-first Iterative Deepening: An Optimal Admissible Tree Search”, Artificial Intelligence, 27: pp. 97–109, 1985.

[7] Robert Kirk and DeLisle, “Beyond A*: IDA*

and Fringe Search”, Game Programming Gems 7, pp. 289-294, 2008.

[8] Marco Tombesi, “Improved Pathfinding with Minimum Replanning Cost: Dynamic A*(D*)”, Game Programming Gems 5, pp.

469-476, Information Publishing Group, 2006.

[9] A. Botea, M. Müller, and J. Schaeffer, “Near Optimal Hierarchical Path-finding”, J. of Game Develop. 1(1), pp. 7-28, 2004.

[10] A. Stentz, “Optimal and Efficient Path Planning for Unknown and Dynamic Environments”, International Journal of Robotics and Automation, Vol. 10, pp.

89-100, 1993.

[11] Oh-Ik Kwon and Teag-Keun Whangbo, “A Dynamic Pathfinding Method Avoiding Moving Obstacles in a 3D Game Environment”, Journal of Korea Game Society, Vol. 6, No. 3, pp. 3-12, 2006.

[12] Mario Grimani and Matthew Titelbaum,

“Beyond A* Algorithm”, Game Programming Gems 5, pp. 452-468, Information Publishing Group, 2006.

[13] Myun-Sub Lee, “A Study on Searching a Path of the Intelligent Character using Genetic Algorithm”, Journal of Korea Game Society, Vol. 9, No. 4, pp. 81-88, 2009.

[14] Amit J. Patel, Amit’s A* Pages, Amit’s Game Programming Information, http://theory.

stanford.edu/~amitp/GameProgramming/.

[15] Dan Higgins, “Fast A* Implementation”, AI Game Programming Wisdom, pp. 223-238, 2003.

[16] Steve Ravin, “A* Speed Optimizations”, Game programming Gems, pp. 363-381, Charles River Media, 2000.

조 성 현 (Cho, Sung Hyun)

1978년 서울대학교 계산통계학과 이학사 1980년 서울대학교 계산통계학과 이학석사 1995년 UCLA 컴퓨터과학과 이학박사 1996년-현재 홍익대학교 게임학부 교수 관심분야 : 게임프로그래밍, 게임인공지능