심예람, <프로젝트DH> AI 내비게이션 시스템, NDC2018

심예람, <프로젝트DH> AI 내비게이션 시스템, NDC2018

심예람, <프로젝트DH> AI 내비게이션 시스템, NDC2018 from devCAT Studio, NEXON

심예람, <프로젝트DH> AI 내비게이션 시스템, NDC2018

1. 넥슨 데브캣 스튜디오 프로젝트DH팀 심예람 (alleysark@nexon.co.kr) 자연스러운 용의 비행을 위한 공중 내비게이션 시스템 개발기 <프로젝트DH> AI 내비게이션 시스템

2. 심예람 / 앨리삵 / alleysark • 프로젝트DH 클라이언트 프로그래머 • 컴퓨터 그래픽스 전공 • 2년차 게임 개발자

3. 프로젝트DH 소개

4. 언리얼 엔진 4로 제작되고 있으며

5. 사실적인 애니메이션을 추구합니다

6. 잠깐, 용이라구요?

7. 용은 걸을 수도, 날 수도 있습니다

8. 그리고 굉장히 넓은 지역을 이동합니다

9. 이 세션에서는, “용의 자연스러운 공중 내비게이션을 위한 3차원 패스 파인딩 및 패스 팔로잉 시스템” 개발기를 소개합니다

10. 이와 함께 언리얼 엔진 4 환경에서 내비게이션 시스템을 어떻게 확장했는지 간단히 소개 드립니다

11. 문제 정의하기

12. 디렉터 요구 사항 • “공중 길 찾기 기능이 필요합니다” • “DH의 맵은 6km x 6km 정도 됩니다” • “필요한 경우 기획자의 의도대로 가이드 가능했으면 좋겠습니다”

13. “무엇보다, 용처럼 날게 해주세요!” • 도대체 용처럼 난다는 게 어떻게 난다는 거죠?

14. 일단... 용이 어떻게 나는지 공부해 보았습니다 …

15. 비행 방식에 따라 모션이 달라집니다 • 이륙, 착륙, 수직 상승, 활강, 뱅크턴, 급정지… Dragon silhouette images from kisspng.com

16. 지형 지물 혹은 상황에 따라 독특한 모션들을 보이기도 합니다 • 수직 강하 • 정지 비행 • 절벽을 따라 활강 • 독특한 착륙 • 스파이럴

17. 공중에서의 방향 전환은 일정한 선회 반경 및 선회율을 유지합니다 • 공중 정지와 후진 비행이 가능합니다 • 하지만 속도를 무시한 채 급선회 할 수 없습니다

18. DH에서 요구하는 공중 내비게이션 시스템 정리 • 3차원 패스 파인딩 기능이 되어야 함 • 용의 움직임에 맞는 부드러운 경로를 생성함 • 비행중인 경로의 유형에 맞게 애니메이션이 반응함 • 생성되는 경로에 기획자의 의도가 반영될 수 있었으면 좋겠음 • 내비게이션을 위한 데이터가 크지 않아야 함

19. 관련 연구 조사

20. Recast Navigation • UE4에서 사용하는 내비게이션 시스템 • 지상 전용 내비게이션 • 내비게이션 메시를 기반으로 길을 찾음 • NDC2017 자료 참고 • <구형맵에서는 어떻게 길을 찾아야 하나요? 기초부터 이해하는 Recast 내비게이션 메시> 하지훈 http://masagroup.github.io/recastdetour/

21. Path Follow UE4 Plugin 스플라인 패스 팔로잉 • 매우 심플한 디자인 • 만들어진 스플라인 패스를 따라가게 해 줌 • 패스 파인딩 기능은 없음 https://www.unrealengine.com/marketplace/path-follow?sessionInvalidated=true

22. DoN AI Navigation 복셀 기반 3D 내비게이션 • 오픈소스 (MIT License) • 일반적으로 생각하는 복셀 기반 내비게이션의 UE4 구현체 • 부드러운 곡선 경로 생성 불가 • 기획자의 의도를 반영하기 어려움 • 맵이 넓을 수록 복셀 데이터량 급증 http://www.drunkonnectar.com/3d-pathfinding-ue4/

23. Mike Roberts and Pat Hanrahan. 2016. Generating Dynamically Feasible Trajectories for Quadrotor Cameras. ACM Trans. Graph. 35, 4, (SIGGRAPH 2016) 드론 비행 경로 최적화 기법 • 드론의 물리적 비행 능력과 환경 요소를 고려한 경로 생성 어시스트 • 스플라인 기반의 경로 생성 • 실시간 경로 생성 기법은 아님

24. 리뷰 • 기존의 지상 내비게이션을 공중 전용으로 확장하기는 어렵다 • 복셀 기반의 내비게이션은 생명체의 움직임을 표현하기엔 부적절하다 • 복셀 기반의 내비게이션 방식으로 어찌 표현한다 해도, 맵의 크기 때문에 복셀 데이터량 감당하기 어렵겠다 • 물리적 타당성에 너무 몰두하지는 말자 • 스플라인이 부드러운 경로를 표현하는 데 딱인데 다루기 까다롭다

25. 스플라인 기반의 하늘 길 시스템

26. 용을 위한 실크로드! ‘길’을 중심으로 자유롭게 비행 가능한 영역 정의 • 하늘 길이라 이름 붙였습니다

27. 하늘 길을 기반으로 용의 실제 이동 경로를 생성 • 안전이 보장된 길을 중심으로 이동 경로를 구합니다

28. 생성된 이동 경로를 선행하는 프로브 프로브를 쫓아가는 용 • 유연한 패스 팔로잉을 위해 완충장치를 두었습니다

29. url: demo_short

30. 구성요소: 웨이포인트 • 하늘 길 고속도로의 IC역할 • 안전 반경을 기록 • 연결된 하늘 길 목록을 관리

31. 구성요소: 하늘 길 도로 • 스플라인으로 제작 • 일정 간격마다 안전 반경을 기록 • 웨이포인트에 연결

32. 구성요소: 프로브 • 최종 경로를 따라 가는 객체 • 전체 경로에 대한 분석 결과를 기록해 둬 용이 언제 어떻게 날아야 할 지를 결정함 • 용의 비행을 직접적으로 제어

33. 이어서 • 하늘 길 시스템의 핵심 요소인 스플라인 • 하늘 길 시스템의 패스 파인딩 절차 • 하늘 길 시스템의 프로브 패스 팔로잉 절차 • UE4 내비게이션 시스템 확장

34. 하늘 길 시스템의 핵심 요소: 스플라인 커브 • 복잡한 것 없이 핵심만 설명합니다!

35. Cubic Bézier Curve • 부드러운 곡선을 표현하는 수단 • 연쇄적인 보간을 통해 시간 t에서의 위치를 결정 • Parametric curve 시간 t에서의 위치는 언제나 동일

36. Cubic Hermite Spline • 2개의 점과 기울기로 곡선 조각을 표현 곡선 조각 = cubic hermite curve • 점과 탄젠트의 시퀀스로 스플라인 곡선을 표현 • 각 점 𝑷에서 C1 연속 • 각 세그먼트를 cubic bézier curve로 변환 가능 𝑷 𝒏, 𝑷 𝒏 + 𝟏 𝟑 𝑻 𝒏, 𝑷 𝒏+𝟏 − 𝟏 𝟑 𝑻 𝒏+𝟏, 𝑷 𝒏+𝟏

37. 연속성(continuity) • 해석학에서 함수의 부드러운 정도(smoothness)를 설명하는 방법 • Parametric continuity / Geometric continuity • 커브(곡선 혹은 곡면)의 부드러운 정도를 설명하는 방법 • 연속성의 수준(order)에 따라 매개변수적 혹은 기하학적 특징이 달라짐

38. 연속성(continuity) • Parametric continuity • 𝑪−𝟏 : 커브가 끊어져 있음 • 𝑪 𝟎 : 커브가 연결되어 있음 • 𝑪 𝟏 : 1차 미분 가능, 보간 속도가 동일 • 𝑪 𝟐 : 2차 미분 가능, 보간 가속도가 동일 • 𝑪 𝒌 : k차 미분 가능 • Geometric continuity • 𝑮 𝟎 : 커브가 점에서 만남 • 𝑮 𝟏 : 동일한 탄젠트를 공유함 • 𝑮 𝟐 : 동일한 곡률의 중점을 공유함 𝐶1 연속, 𝐺1 연속 𝐶1 연속 아님, 𝐺1 연속 느림 빠름

39. UE4 USplineComponent • Cubic hermite curve 세그먼트로 이루어짐 • Arriving / Leaving Tangent • 커브 연결점에서 전 후 탄젠트가 다를 수 있음 • C1 연속이 아닐 수 있음 • 보간 속도의 일관성을 보장하기 위해 reparameterization table을 만들어 둠 • 하늘 길은 USplineComponent의 코어인 FInterpCurve<> 템플릿 자료구조로 제작함

40. 하늘 길 시스템 – 패스 파인딩 하늘 길 시스템 – 패스 팔로잉 언리얼 엔진 AI 시스템과 융합

41. 패스 파인딩 절차 1. 출발/도착 지점에서 하늘 길로 임시 경로 연결 2. 그래프 최단 경로 탐색 수행 3. 들어오고 나가는 경로를 생성 4. 스무딩 및 최종 경로 스플라인 생성

42. 출발 도착 출발/도착 지점에서 하늘 길 연결 • 출발/도착 지점은 하늘 길 밖에 있음

43. 출발 도착 출발/도착 지점에서 하늘 길 연결 • 출발/도착 지점은 하늘 길 밖에 있음 • 이 위치에서 ‘보이는’ 하늘 길로의 임시 링크를 생성

44. 출발 도착 하늘 길 그래프 최단 경로 탐색 • 임시 링크를 포함하여 그래프 탐색: A* search

45. 출발 도착 하늘 길 그래프 최단 경로 탐색 • 임시 링크를 포함하여 그래프 탐색: A* search • 하늘 길의 가중치를 달리 할 수 있음

46. 들어오는 길, 나가는 길 생성 • 출발/도착 지점에서 하늘 길로의 연결은 ‘길’로써의 사용하기엔 미흡함 • 출발/도착 지점 속도와 진입/탈출 지점 속도를 고려한 길 생성 절차가 필요함 • 어떻게? 다시 길 찾기 문제?! • 짧은 거리의 두 지점을 부드럽게 잇는 간단한 방법을 고안

47. 두 지점 사이를 잇는 ‘합리적인’ 경로 생성 • 각 지점의 탄젠트 위치를 이은 선분을 후보 공간 축으로 사용

48. 두 지점 사이를 잇는 ‘합리적인’ 경로 생성 • 각 지점의 탄젠트 위치를 이은 선분을 후보 공간 축으로 사용 • 후보 공간 축의 가운데 지점을 지나는 평면이 후보 공간 평면

49. 두 지점 사이를 잇는 ‘합리적인’ 경로 생성 • 각 지점의 탄젠트 위치를 이은 선분을 후보 공간 축으로 사용 • 후보 공간 축의 가운데 지점을 지나는 평면이 후보 공간 평면 • 극좌표상 일정 위치를 후보 지점으로 하고

50. 두 지점 사이를 잇는 ‘합리적인’ 경로 생성 • 각 지점의 탄젠트 위치를 이은 선분을 후보 공간 축으로 사용 • 후보 공간 축의 가운데 지점을 지나는 평면이 후보 공간 평면 • 극좌표상 일정 위치를 후보 지점으로 하고 • 각 후보 지점의 선호도를 계산

51. 두 지점 사이를 잇는 ‘합리적인’ 경로 생성 • 각 지점의 탄젠트 위치를 이은 선분을 후보 공간 축으로 사용 • 후보 공간 축의 가운데 지점을 지나는 평면이 후보 공간 평면 • 극좌표상 일정 위치를 후보 지점으로 하고 • 각 후보 지점의 선호도를 계산 • 높은 우선순위의 후보 지점부터 경로 유효성 검증 • 두 지점과 선택된 후보 지점을 거치는 스플라인 생성

52. 들어오는 길, 나가는 길 생성 • 출발 지점 속도(용의 초기 속도), 진입점 탄젠트, 탈출점 탄젠트, 도착 지점 속도(목표 방향) 출발 도착

53. 들어오는 길, 나가는 길 생성 • 출발 지점 속도(용의 초기 속도), 진입점 탄젠트, 탈출점 탄젠트, 도착 지점 속도(목표 방향) • 임시로 연결한 직선 경로를 부드러운 경로로 대체 출발 도착

54. 비포장 도로는 싫어요! 연결된 패스 스무딩하기 • 결과 경로 시퀀스에는 꺾인 지점들이 많음 출발 도착

55. 비포장 도로는 싫어요! 연결된 패스 스무딩하기 • 결과 경로 시퀀스에는 꺾인 지점들이 많음 • 하늘 길의 안전 반경을 벗어나지 않는 선에서 전체적인 경로를 부드럽게 만들어야 함 출발 도착

56. 비포장 도로는 싫어요! 연결된 패스 스무딩하기 • 결과 경로 시퀀스에는 꺾인 지점들이 많음 • 하늘 길의 안전 반경을 벗어나지 않는 선에서 전체적인 경로를 부드럽게 만들어야 함 • 용의 크기를 고려하여 스무딩 된 패스가 안전 반경을 벗어나지 않아야 함 출발 도착

57. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점

58. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점 • 꺾인 지점의 인접 세그먼트 위의 일정 거리상 위치를 샘플링

59. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점 • 꺾인 지점의 인접 세그먼트 위의 일정 거리상 위치를 샘플링 • 각 지점 사이가 이어져도 안전반경 내에서 안전한지를 검사

60. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점 • 꺾인 지점의 인접 세그먼트 위의 일정 거리상 위치를 샘플링 • 각 지점 사이가 이어져도 안전반경 내에서 안전한지를 검사 • 용의 크기를 고려할 때 이어도 안전한 가장 바깥쪽 두 샘플 포인트를 선정

61. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점 • 꺾인 지점의 인접 세그먼트 위의 일정 거리상 위치를 샘플링 • 각 지점 사이가 이어져도 안전반경 내에서 안전한지를 검사 • 용의 크기를 고려할 때 이어도 안전한 가장 바깥쪽 두 샘플 포인트를 선정

62. 패스 스무딩 과정 • 웨이포인트 였던 위치가 꺾이는 지점 • 꺾인 지점의 인접 세그먼트 위의 일정 거리상 위치를 샘플링 • 각 지점 사이가 이어져도 안전반경 내에서 안전한지를 검사 • 용의 크기를 고려할 때 이어도 안전한 가장 바깥쪽 두 샘플 포인트를 선정 • 두 지점 사이에 부드러운 곡선을 생성하여 연결

63. 패스 스무딩: 두 지점의 탄젠트 조정 • 두 지점의 탄젠트를 그대로 쓰면 스플라인이 꼬일 수 있음

64. 패스 스무딩: 두 지점의 탄젠트 조정 • 두 지점의 탄젠트를 그대로 쓰면 스플라인이 꼬일 수 있음 • 탄젠트 세그먼트들의 Closest point를 구하고

65. 패스 스무딩: 두 지점의 탄젠트 조정 • 두 지점의 탄젠트를 그대로 쓰면 스플라인이 꼬일 수 있음 • 탄젠트 세그먼트들의 Closest point를 구하고 • 해당 지점 까지 탄젠트를 클램프

66. 패스 스무딩: 두 지점의 탄젠트 조정 • 두 지점의 탄젠트를 그대로 쓰면 스플라인이 꼬일 수 있음 • 탄젠트 세그먼트들의 Closest point를 구하고 • 해당 지점 까지 탄젠트를 클램프 • 물론.. 단순 클램핑으로 해결되지 않는 케이스들도 많음

67. 하늘 길 시스템 – 패스 파인딩 하늘 길 시스템 – 패스 팔로잉 언리얼 엔진 AI 시스템과 융합

68. 스플라인 시간 t의 위치로 용 위치 갱신…? • 스플라인을 단순히 따라가게 하면 용의 움직임이 단조로움 • Reparameterization 정밀도가 낮으면 일정한 속력으로 이동하지 못함 • 외력에 의한 경로 이탈을 제어하기 힘듦 • 공격받았을 때, 장애물(다이내믹 오브젝트)에 부딪쳤을 때…

69. 용보다 앞서 움직이는 프로브, 프로브를 따라가는 용 • 프로브는 스플라인 위를 정직하게 이동 • 용은 프로브를 향해서 날아감 • 프로브는 용이 뒤쳐지거나 앞서지 않도록 속도를 제어함 • 프로브는 용의 패스 팔로잉 로직의 완충 장치 http://www.damentrading.com/en/buy-a-ship/06920-tugboat

70. 프로브를 따라 나는 용… 어떻게? • ‘어떻게’ 비행하는가에 대한 의문은 여전히 남음 • 용의 비행 유형은 선형 속도와 회전 속도의 변화로 결정됨

71. 프로브를 따라 나는 용… 어떻게? • ‘어떻게’ 비행하는가에 대한 의문은 여전히 남음 • 용의 비행 유형은 선형 속도와 회전 속도의 변화로 결정됨 • 전체 패스를 분석하여 일정한 기준으로 구간을 나눔

72. 프로브를 따라 나는 용… 어떻게? • ‘어떻게’ 비행하는가에 대한 의문은 여전히 남음 • 용의 비행 유형은 선형 속도와 회전 속도의 변화로 결정됨 • 전체 패스를 분석하여 일정한 기준으로 구간을 나눔 • 각 구간의 최대/최소 속력, 선회 속력, 롤링 등을 분석

73. 프로브를 따라 나는 용… 어떻게? • ‘어떻게’ 비행하는가에 대한 의문은 여전히 남음 • 용의 비행 유형은 선형 속도와 회전 속도의 변화로 결정됨 • 전체 패스를 분석하여 일정한 기준으로 구간을 나눔 • 각 구간의 최대/최소 속력, 선회 속력, 롤링 등을 분석 • 구간 별 모션 유형을 결정

74. 패스 분석: 선형 속도 변화 • 경로의 Z성분 극점을 기준으로 선형 속도에 유의미한 변화가 발생함 • 1차 도함수 극점: 기울기 - → + 혹은 + → - • 2차 도함수 극점: 기울기 변화량, 즉 변곡점(inflection point)

75. A B C A B C A B C 패스 분석: 선형 속도 변화 • 하강하다 다시 상승하는 구간으로 예를 들면, • A → B 구간 점진적으로 속력 줄어듦 • B → C 구간은 속력이 더 이상 줄 수 없어 고도 상승을 위한 날갯짓 시작 • 물리적으로 타당한 것은 아니지만 결과가 나쁘지는 않다

76. 패스 분석: 극점(extremity) 계산 • Cubic Hermite curve: 3차 다항식 𝑪𝒖𝒓𝒗𝒆 𝒙 = 𝟐𝑷 𝟎 + 𝑻 𝟎 + 𝑻 𝟏 − 𝟐𝑷 𝟏 𝒙 𝟑 + −𝟑𝑷 𝟎 − 𝟐𝑻 𝟎 − 𝑻 𝟏 + 𝟑𝑷 𝟏 𝒙 𝟐 + 𝑻 𝟎 𝒙 + 𝑷 𝟎 𝑪𝒖𝒓𝒗𝒆′ 𝒙 = 𝟔𝑷 𝟎 + 𝟑𝑻 𝟎 + 𝟑𝑻 𝟏 − 𝟔𝑷 𝟏 𝒙 𝟐 + −𝟔𝑷 𝟎 − 𝟒𝑻 𝟎 − 𝟐𝑻 𝟏 + 𝟔𝑷 𝟏 𝒙 + 𝑻 𝟎 𝑪𝒖𝒓𝒗𝒆′′ 𝒙 = 𝟏𝟐𝑷 𝟎 + 𝟔𝑻 𝟎 + 𝟔𝑻 𝟏 − 𝟏𝟐𝑷 𝟏 𝒙 + −𝟔𝑷 𝟎 − 𝟒𝑻 𝟎 − 𝟐𝑻 𝟏 + 𝟔𝑷 𝟏 • 3차원 벡터의 수직 성분에 대해서만 계산 𝑪𝒖𝒓𝒗𝒆′ 𝒙 = 𝟎 𝒘𝒉𝒆𝒏 𝒙 = −𝒃 ± 𝒃 𝟐 − 𝟒𝒂𝒄 𝟐𝒂 𝑪𝒖𝒓𝒗𝒆′′ 𝒙 = 𝟎 𝒘𝒉𝒆𝒏 𝒙 = −𝒃 𝒂

77. 잠깐! 2차 미분이라뇨, Hermite Spline은 C2 연속이 아닌걸요?! • 연결 지점의 Arrive/Leave 탄젠트를 맞췄다 해도 C2 연속을 보장할 수 없음 • 심지어 패스 스무딩 등의 과정을 거치며 C1 연속이 아닐 수도 있음 • 그래서 커브의 연결 지점은 패스 구분을 위한 포인트로 강제함 • CAD 툴을 만드는 게 아니니 적당히 넘어가도 괜찮습니다 ㅎㅎ.. C1 연속인 연결점 C2 연속인 연결점

78. 패스 분석: 선회 속도 변화 • 선회란 항공기가 곡선을 그리듯 진로를 바꾸는 것 • 빠른 선회를 위해 양력이 선회 반경의 중심 쪽을 향할 수 있도록 몸을 틀어줘야 함 • 뱅크 턴(bank turn)이라고 부르는 공중 기동 기법 • 속력이 일정할 때 선회 반경이 작아지면 선회율 상승 • 선회 반경은 수평 곡률에 반비례 • 즉, 수평 곡률 상승 → Bank Angle 상승 https://www.quora.com/What-is-the-relationship-between-turn-rate-and-g-force-when-an-aircraft-turns

79. 패스 분석: 수평 곡률(curvature) 계산 • 곡률은 굽은 정도를 표현하는 수치: 𝑪 𝒕 = (𝒙 𝒕 , 𝒚 𝒕 ), 𝜿 = 𝟏 𝒓 = 𝒙′ 𝒚′′−𝒚′ 𝒙′′ 𝒙′𝟐+𝒚′𝟐 𝟑/𝟐 • 수직 성분인 XY 컴포넌트에 대해 계산 • 패스의 곡률이 큰 지점일 수록 선회 반경이 작음 • 수평 곡률에 따라 bank angle에 해당되는 롤(roll) 회전 요소 계산 𝒓

80. 패스 팔로잉: 프로브 제어 • 프로브는 용과 적정 거리를 유지하며 스플라인 위를 움직여야 함 • 일정 속력을 유지하되 용과의 거리가 가까워지면 속력을 높이고, 거리가 멀어지면 속력을 늦춤

81. 패스 팔로잉: 용 움직임 제어 • 프로브의 현재 구간 유형을 확인 • 현재 위치의 기울기로 가속력, 속력 계산 • 프로브로의 방향으로 속력 만큼 이동 거리 𝚫𝐩 계산

82. 패스 팔로잉: 용 움직임 제어 • 프로브의 현재 구간 유형을 확인 • 현재 위치의 기울기로 가속력, 속력 계산 • 프로브로의 방향으로 속력 만큼 이동 거리 𝚫𝐩 계산 • 용을 프로브로의 방향으로 정렬하기 위한 회전 속력 계산 • 현재 위치의 롤(roll) 회전 요소를 누적 • 최종 회전 속력 만큼 회전 값 𝚫𝐑 계산

83. 패스 팔로잉: 용 움직임 제어 • 프로브의 현재 구간 유형을 확인 • 현재 위치의 기울기로 가속력, 속력 계산 • 프로브로의 방향으로 속력 만큼 이동 거리 𝚫𝐩 계산 • 용을 프로브로의 방향으로 정렬하기 위한 회전 속력 계산 • 현재 위치의 롤(roll) 회전 요소를 누적 • 최종 회전 속력 만큼 회전 값 𝚫𝐑 계산 • 용 객체의 위치 / 회전 갱신

84. 패스 팔로잉: 용 움직임 제어 • 패스 유형이 바뀌는 시점을 용 객체에게 통지 • 용 객체는 실버바인 모션 엔진을 통해 적절한 로코모션 재생 • 비행 로코모션 연구는 WIP!!

85. 경로 재탐색 전략: Pruning & Grafting • AI 내비게이션 대상은 움직이는 물체인 경우가 많음 • 타겟이 이동한 경우 패스의 갱신이 필요함

86. 경로 재탐색 전략: Pruning & Grafting • AI 내비게이션 대상은 움직이는 물체인 경우가 많음 • 타겟이 이동한 경우 패스의 갱신이 필요함 • 패스의 적당한 지점을 찾아 잘라 냄 (pruning)

87. 경로 재탐색 전략: Pruning & Grafting • AI 내비게이션 대상은 움직이는 물체인 경우가 많음 • 타겟이 이동한 경우 패스의 갱신이 필요함 • 패스의 적당한 지점을 찾아 잘라 냄 (pruning) • 해당 지점의 위치와 탄젠트를 유지한 채 타겟 위치로 패스 파인딩 • 새 경로를 기존 경로에 접붙이기 (grafting)

88. 요약 • 패스 파인딩 • 출발/도착 지점에서 하늘길로 임시 경로 연결 • 그래프 탐색 • 부드럽게 들어오는 길, 나가는 길을 생성 • 전체 경로 스무딩 • 패스 팔로잉 • 비행 유형별로 구간을 나눔 • 프로브의 위치를 갱신 • 용의 위치 및 회전, 그리고 모션을 갱신 • 필요한 경우 경로 재탐색

89. 하늘 길 시스템 – 패스 파인딩 하늘 길 시스템 – 패스 팔로잉 언리얼 엔진 AI 시스템과 융합

90. UE4 내비게이션 흐름 AIController MoveTo NavigationSystem FindPathSync NavigationData (RecastNavMesh) FindPath PathFollowingComponent RequestMove NavPathSharedPtr 패스 파인딩 패스 팔로잉 UpdatePathSegment FollowPathSegment

91. AIController 확장 • AI 에이전트 관리 주체 • MoveTo 기능과 유사하게 FlyingMoveTo 요청 구현 • 하늘 길 시스템을 통해 실질적인 공중 패스 파인딩 수행 • Path Following Component 교체

92. PathFollowingComponent 확장 • UE4가 제공하는 AI 에이전트 패스 세그먼트 팔로우 제어 컴포넌트 • 지상 이동은 기존대로 동작 • 공중 이동 요청의 경우 프로브의 Update / Follow 로직으로 대체

93. 공중 내비게이션 흐름 DhAIController FlyingMoveTo FlightPathSystem FindPathSync FlightPathData DhPathFollowingComponent RequestFlyingMove FlightPathProbePtr UpdateFlightPathProbe FollowFlightPathProbe

94. 결과

95. 데모 영상 – 용 시점 url: demo_dragon_view

96. 데모 영상 – 하늘 뷰 url: demo_sky_view

97. 데모 영상 – 경로 재탐색 url: demo_repath

98. 하늘 길 에디터 툴 • 언리얼 엔진 에디터에서 사용 • 스플라인으로 경로를 쉽게 변형 가능 • 안전 반경을 재계산해줌 • 설치까지 자동화 한다면 좋겠지만…

99. 비용? • 자세한 프로파일링과 최적화 작업 전 • 그렇지만, 게임 플레이에 영향 주지 않는 수준의 퍼포먼스 • 비싼 부분 • 스플라인의 잦은 생성과 파괴 • 레이 트레이스, 캡슐 오버랩 테스트 • 최적화 대상!!

100. 미 구현 사항 및 향후 계획 • 용의 날갯짓에 맞게 용 움직임 제어 • 물리 법칙에 맞게 용 움직임 제어 • 스플라인 오프세팅(offsetting) • 비동기 패스 파인딩 • 복셀 기반 패스 파인딩 하이브리드?

101. 개발하며 • 연구와 실전 개발은 많이 다르구나 • 설계 시 고려하지 못한 코너 케이스들의 향연 • 역사가 깊은 AI 내비게이션, 아직까지 실버 불릿은 없는 것인가.. • 더 잘 만들고픈 욕심과 현실적 한계 사이에서 균형 잡기

102. 감사합니다

103. Q & A