A Study on the Partial Path Generation in the A* Path Search

컴퓨터 게임에서 목표 위치로 이동할 때, NPC(non-player character)는 그 위치까지의 경로 탐색을 수행한다. 경로 탐색이 수행되는 동안, NPC는 실제 이동을 시작하기 전에 그 탐색 결과를 기다려야한다. 이것은 수백 개의 에이전트나 커다란 그래프를 갖는 게임에서는 한정된 CPU 자원으로 전체 경로 탐색 요청을 처리하는데 소요되는 시간이 길어져서 이러한 접근법이 게임 진행을 더디게 만든다. 경로 탐색에 할당되는 CPU 자원을 한정하여 전체 게임진행은 원활하게 할 수 있지만, 제한된 경로탐색 시간을 다수의 NPC가 나누어 사용해야 한다. 제한된 검색 시간으로 지연이 너무 길어지면, NPC는 막연하게 기다리거나 벽이나 다른 장애물로 목적 없이 진행하게 된다. 이런 경우 해결 방법 중의 하나는 완성된 경로를 기다리기 전에 NPC가 목표 위치까지의 부분 경로를 조기에 결정하는 것이다. 즉, 사용자가 정의한 수의 검색 사이클이나 검색 깊이가 도달된 후에는 목표에 가장 가까운 노드에 이르는 경로를 반환하도록 A* 알고리즘을 변경하는 것이다. 그러면 NPC는 완전한 경로가 만들어질 때까지 이 부분경로를 따라가고 그 사이에 도착하는 전체 경로를 반영하여 최종 목적지에 도착할 수 있다. 실험을 통해 부분 경로를 생성했을 때, 실시간 게임에서 훨씬 더 사실감을 증대시키는 효과가 있음을 확인하였다.

When moving to a target position in a computer game, the NPC( non-player character ) performs a path search to that position. While the path search is running, NPC has to wait for the search results before starting the actual movement. This increases the amount of time it takes to process all the path search requests with limited CPU resources in games with hundreds of agents or large graphs, making this approach slow to play. Although overall game play can be facilitated by limiting the CPU resource allocated to path search, the allocated path search time should be shared by many NPCs. If the delay becomes too long with limited search time, NPC will either wait vaguely or proceed aimlessly into walls or other obstacles. In this case, one solution is for the NPC to determine the partial path to the target position early before waiting for the completed path. This means changing the A* algorithm to return a path to the node closest to the target after a user-defined number of search cycles or search depth has been reached. The NPC can then follow this sub-path until a complete path is generated and arrived in between and arrive at the final destination reflecting the entire path. Experiments have shown that when partial path is generated, real-time game has a much more realistic effect.