게임 적용을 위한 Dynamic Programming 알고리즘 길찾기

다국어 초록 (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.

참고문헌 (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