표제지
목차
제1장. 서론 8
1.1 연구 배경 8
1.2 논문의 구성 10
제2장. 기존 게임에서의 path-finding 방법 12
2.1 균일 격자(Regular grids) 12
2.2 모서리 그래프(Corner graphs) 13
2.3 웨이포인트 그래프(Waypoint graphs) 14
2.4 네비게이션 메쉬(Navi gation meshes, NavMesh) 15
2.5 가시성 그래프(Visibility graphs, Vgraph) 16
제3장. 기존 path-fi finding 방법의 확장 18
3.1 일반화 가시성 그래프에 의한 탐색공간 표현 20
3.1.1 C-공간으로의 확장 20
3.1.2 일반화 가시성 그래프(Generalized Visibility Graph, GVgraph) 24
3.2 회전 Sweep-line(RSL)을 적용한 경로 계획 29
3.3 A* 알고리즘 37
제4장. 경로 이동의 실행(Execution) 39
4.1 기본적 이동 방법 39
4.1.1 직선 경로의 이동 40
4.1.2 원 경로의 이동 41
4.1.3 도착하기 42
4.2 선택적 조타행동 43
4.2.1 의사결정나무(Decision tree) 44
4.2.2 장애물 피하기(Obstacle avoidance) 45
제5장. path-finder 시뮬레이션 48
5.1 경로 계획 구현 50
5.2 경로 이동의 실행 구현 53
5.3 시뮬레이션 결과 56
제6장. 결론 58
참고문헌 60
국문요약 63
Abstract 65
감사의 글 67
그림 1 . 게임 엔진에서의 path-finder 시스템 11
그림 2. 사각형 격자 모델로 경로 계획하기 13
그림 3 . 모서리그래프에서 경로 계획하기 14
그림 4. 웨이포인트 그래프에서 경로 계획하기 15
그림 5. 삼각형 기반 NavMesh에서 경로 계획하기 16
그림 6. Vgraph를 이용한 경로 계획하기 17
그림 7. 경로 계획과정 19
그림 8. C-공간 문제로의 변환 21
그림 9. 솔리드 오프세팅 22
그림 10. 두 다각형을 합집합 하는 알고리즘 24
그림 11. 가상 점이 생기는 경우 25
그림 12. 확장된 장애물에 대한 GVgraph와 추가된 링크 27
그림 13. RSL 알고리즘의 초기상태와 이진탐색트리에 저장된 교차선분 31
그림 14. 지역적 비 볼록 일반화 다각형에 대한 RSL 알고리즘의 적용 33
그림 15. 지역적 비 볼록 일반화 다각형에 대한 RSL 알고리즘의 적용 과정 35
그림 16. 벡터 계산하기 41
그림 17. 원의 방정식의 단점 42
그림 18. 장애물에 대한 의사결정 나무 45
그림 19. 장애물 피하기의 A, B, C단계 46
그림 20. 16*16 도트의 타일들 48
그림 21. 맵-에디터의 구성 49
그림 22. 시뮬레이션 예제 맵 50
그림 23. 경로 계획의 단계별 진행 51
그림 24. 경로 계획 결과 최적 경로 52
그림 25. 방해 NPC에 의한 이동경로 방해 54
그림 26. 시나리오에 따른 선택적 장애물 피하기 실행 결과 56