게임 적용을 위한 Dynamic Programming 알고리즘 길찾기 = Dynamic Programming Algorithm Path-finding for Applying Game

국문 초록 (Abstract)

게임 맵에서 NPC들이 목표 위치로 이동하기 위하여 A* 알고리즘을 비롯한 다양한 알고리즘들을 이용하여 탐색해 왔다. 그 중 가장 많이 사용하는 알고리즘은 탐색속도가 빠른 A*이다. 그러나 A*에는 다음과 같은 문제점들을 가지고 있다. 첫 번째는 무작위로 변화하는 맵에서는 변할 때마다 모든 계산을 다시 해야하며 잘못될 경우에는 목표를 찾지 못할 경우도 있다. 두 번째는 장애물 같이 NPC에 피해를 입히는 위험요소들이 위치하는 곳을 피하여 이동하기가 힘이 든다. 물론 위험 요소들에게 가중치를 부여하여 가중치가 높은 곳은 이동하지 않게도 할 수 있지만 위험 요소들의 근처에 이동하는 경우에는 제어하기 힘이 든다.<br/>
이러한 문제점을 해결하기 위하여 본 논문에서는 Dynamic Programming을 이용하여 길찾기 알고리즘에 적용하였다. 적용한 결과 무작위로 변화하는 맵 상의 변화에 잘 적응하였으며, NPC들이 자신의 위험 요소들을 멀리 피해가는 모습을 볼 수 있었다. 또한 A*와 비교에서도 좋은 결과가 나왔다.

다국어 초록 (Multilingual Abstract)

In order to move NPC's to target location at game maps, various algorithm including A* has been used. The most frequently used algorithm among them is A* with fast finding speed. But A* has the following problems. The first problem is that at randomly changing map, it is necessary to calculate all things again whenever there are any changes. And when calculation is wrong, it is not possible to search for target. The second problem is that it is difficult to move avoiding dangerous locations damaging NPC such as an obstruction. Although it is possible to avoid moving to locations with high weight by giving weight to dangerous factors, it is difficult to control in case NPC moves nearby dangerous factors. <br/>
In order to solve such problems, in this thesis, the researcher applied Dynamic Programming to path-finding algorithm. As the result of its application, the researcher could confirm that the programming was suitable for changes at the map with random change and NPC's avoided the factors being dangerous to them far away. In addition, when compared to A*, there were good results.

목차 (Table of Contents)

• 요약
  
• Abstract
  
• Ⅰ. 서론
  
• Ⅱ. 관련연구
  
• Ⅲ. 최적의 길찾기에 Dynamic Programming 알고리즘 적용
  
• Ⅳ. 실험 및 결과
  
• Ⅴ. 결론
  
• 참고문헌
  
• 저자소개

참고문헌 (Reference)

1 "퍼지 플로킹 기반의 보이드 행동 모델링" 퍼지 및 지능시스템학회 2004

2 "패턴인식 개론" 한빛미디어 438-453, 2005

3 "타일맵에서 A* 알고리즘을 이용한 유닛들의 길찾기 방법 제안" 한국컴퓨터정보학회 71-77, 2004

4 "게임 인공지능의 형태와 앞으로의 발전 방향" 한국게임학회 2002

5 "“Putting AI In Entertainment An AI Authoring Tool for Simulation and Games”" 2002

6 "www.policyalmanac.org/games"

7 "http://www.ics.uci.edu/~eppstein/161/960215.html" 161960215-,

8 "The Art and Theory of Dynamic Programming" Academic Press 1977

9 "Neuro-Dynamic Programming" Athena Scientific 1996

10 "Introduce to Algorithms second editon" 한빛미디어 343-393,

11 "Game Programming" 175-178, 2001

12 "Empty space BSP트리를 이용한 3D 게임 렌더링 엔진 설계" 학국컴퓨터정보학회 10 : 345-352, 2005

13 "Dynamic Programming and Optimal Control: Second Edition" 2001

14 "Computer Games With Intelligence" IEEE International Fuzzy Systems Conference 2001