Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-4540(Print)
ISSN : 2287-8211(Online)
Journal of Korea Game Society Vol.13 No.1 pp.31-40
DOI : https://doi.org/10.7583/JKGS.2013.13.1.31

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

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

초록

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

A Pathfinding Algorithm Using Path Information

Sung Hyun Cho
School of Games, Hongik University
Received: Jan. 14, 2013, Accepted: Jan. 29, 2013

Abstract

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

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].

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].

[Fig. 1] Pseudo A* Algorithm

2.2 A* 알고리즘의 최적화

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

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

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값의 균형이 깨지지 않도록 λ는 작은 값으로 설정하면 된다. 

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* 알고리즘이 찾아낸 경로를 보여 준다. 

[Fig. 2]

[Table 1]에서 첫 번째 열은 알고리즘의 종류, 두 번째 열은 찾아낸 경로의 거리, 세 번째 열은 검색한 노드의 수, 네 번째 열은 PIA* 알고리즘이 찾아낸 경로의 거리를 A* 알고리즘이 찾아낸 경로의 거리로 나눈 값으로 찾은 경로의 질을 의미하며, 다섯 번째 열은 A* 알고리즘이 검색한 노드의 수를 PIA* 알고리즘이 검색한 노드의 수로 나눈 값으로 알고리즘의 성능을 의미한다. 

[Table 1] Performance Comparison in MAP1

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

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

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

[Fig. 3]

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

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

[Table 2] Performance Comparison in MAP2

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

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

[Fig. 4]

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

[Table 3] Performance Comparison in MAP3

[Fig. 4](a)에서 A* 알고리즘은 목표노드가 출발노드보다 아래쪽에 위치하여 처음에는 아래 방향으로 검색을 진행하다가 나중에 위쪽으로 경로를 찾기 때문에 검색이 오래 걸린다. [Fig. 4](c)에서는 아래쪽에 경로 정보가 있기 때문에 [Fig. 4](a)보다 아래쪽으로 더 검색을 진행하기 때문에 PIA*알고리즘이 A* 알고리즘보다 시간이 더 걸릴 수 있다는 것을 보여준다.

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

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

[Fig. 5]

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

[Table 4] Performance Comparison in MAP4

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

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]

[Fig. 6] (c)는 위쪽에 제공된 경로 정보를 이용하여 오른쪽으로 이동하다가 아래쪽으로 이동하기때문에 [Fig. 6] (b)의 경우보다 찾은 경로의 질은 떨어지지만 성능은 더 좋다. [Fig. 6] (c)에 두 가지 경로 정보가 같은 방향이기 때문에 성능이 개선되었으나, [Fig. 2] (c), [Fig. 4] (c), [Fig. 5] (c)에서는 경로 정보가 다른 방향으로 향하기 때문에 수행시간과 경로의 질에 부정적인 영향이 있다.

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

4.3 실험 결과 분석

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

[Table 5] Performance Comparison in MAP5

특별히 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. 

Reference

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 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.