<div id="readability-page-1" class="page"><div>
 <a href="/m/category/Studies/Shader">Studies/Shader</a><h3>Shader Study 후기 - Flow Fields and Steering Behaviors [GDC 2022: AOE IV] (22/10/05)</h3>
 </div><cite>calci</cite>
 2022. 10. 5. 23:16
 <div>
 GDC 2022에서 발표된 에이지 오브 엠파이어 4 엔티티 네비게이션 AI를 위해 사용된 기법입니다.
자세한 내용은 셰이더 스터디 카페를 참고 부탁드립니다.
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<blockquote data-ke-style="style3">본 기록은 발표 내용을 개인적 이해와 함께 재구성한 것입니다. 발표자분의 의도와 다를 수 있으며, 잘못된 내용이 있을 수 있으니 양해 부탁드립니다.</blockquote>

<h3 data-ke-size="size23">발표 내용</h3>

에이지 오브 엠파이어는 많은 수의 엔티티가 실시간으로 동시에 길을 찾아 이동하고 전투를 수행해야 하는 RTS 게임입니다. 일반적으로 액터의 길찾기는 A* 알고리즘을 통상적으로 사용하는데요. 상호 작용이 가능한 동적 오브젝트를 고려하면 매 프레임 계산을 수행해야 하고, 길을 찾으려는 엔티티 수가 늘어날 수록 연산은 더 많아지고 비싸지게 됩니다. 더구나, 다른 오브젝트를 피하기 위해서 Steering을 수행하는데, 이 Steering을 통해서 수립된 새로운 경로가 항상 진행 가능하다는 법도 없어서 확실한 대안으로는 보기 어렵습니다.

이 세션에서는 Flow Field를 이용해서 군중의 길찾기 중복 계산 비용을 줄여보겠다는 아이디어에서 출발합니다.
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="1003" data-origin-height="565">
 
 <img src="https://blog.kakaocdn.net/dn/YivW3/btrN3LH13up/Ov8VrMJgjsyWCefABvIZkK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="1003" data-origin-height="565">
 
 
</figure>

그리드별로 코스트를 계산하고, 인접한 셀의 수치를 토대로 플로우 필드를 제작합니다.
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="948" data-origin-height="450">
 
 <img src="https://blog.kakaocdn.net/dn/oBZRV/btrN4aHot4k/EXR9qWAYpC7cJePZ5TRTnK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="948" data-origin-height="450">
 
 
</figure>


이렇게 플로우 필드를 이용하면, 모두 다른 위치에 존재하는 엔티티들을 한 지점으로 이동시키려고 할 때 하나의 플로우 필드를 이용해 경로를 결정할 수 있습니다. 이 플로우 필드를 제작하는 비용이 저렴한 것은 아니지만, 비용 대비 좋은 퀄리티를 내기 위해 여러가지 기법을 섞어 시도했다고 합니다.

<figure data-ke-mobilestyle="widthOrigin" data-origin-width="945" data-origin-height="453">
 
 <img src="https://blog.kakaocdn.net/dn/bJ8q2Z/btrN5Fl2wqh/gokysjW3QtsB5zk0KVqoZK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="945" data-origin-height="453">
 
 
</figure>
Hierarchiocal A* Pathfinding에 착안하여, 모든 그리드에 대해 단일 플로우 필드를 생성하는 것이 아닌, 일정 그리드 크기 별로 셀을 만들고 Line Of Sight 기준으로 포탈을 선정하여 Nav Mesh와 유사한 방식으로 노드를 구성합니다. 그리고, 셀과 셀을 이동하기 위해서는 포탈간 노드를 사용하고, 셀 내에서 포탈까지 이동하기 위해서는 플로우 필드를 사용하는 하이브리드 방식입니다.


<figure data-ke-mobilestyle="widthOrigin" data-origin-width="950" data-origin-height="491">
 
 <img src="https://blog.kakaocdn.net/dn/dUmxz1/btrN5wQfR7U/Ix7WAV4xgrQtaimWvHIwXK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="950" data-origin-height="491">
 
 
</figure>
그런데, 한계가 존재합니다. 싱글 셀을 기준으로 계산을 하면 포탈의 위치에 따라 어색하게 이동하는 듯 한 부분을 확인 할 수 있습니다. 이를 보완하기 위해 인접한 셀까지는 함께 계산하여, 비용을 조금 투자하되 경로가 보다 합리적으로 보이도록 보정 효과를 도모했습니다.



<figure data-ke-mobilestyle="widthOrigin" data-origin-width="945" data-origin-height="487">
 
 <img src="https://blog.kakaocdn.net/dn/bKe6Zt/btrN33aCYYR/dXR5PcmhR62fISuefU4nxK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="945" data-origin-height="487">
 
 
</figure>
그리드 기반인 만큼, 다양한 크기의 유닛에 대해서는 처리할 수단이 필요한데요, 빨간 유닛은 3 x 3으로, 2 그리드 크기의 공간을 통과할 수 없습니다. 그런데 녹색 유닛은 통과할 수 있습니다. RTS 에서는 다수의 다른 유닛을 한 번에 선택하여 단일 지점으로 이동시키는데요, 이런 예외가 관리되지 않는다면 두 종류의 유닛이 다른 길로 이동하게 될 것입니다. 비용상으로는 합리적인 선택이지만 플레이어가 기대하는 동작은 아닐 것입니다.


<figure data-ke-mobilestyle="widthOrigin" data-origin-width="944" data-origin-height="450">
 
 <img src="https://blog.kakaocdn.net/dn/brluty/btrN3rJUk22/92TRRhJvIhpvdPMwwN4Kvk/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="944" data-origin-height="450">
 
 
</figure>
이런 경우, 선택된 유닛 중 가장 큰 사이즈 유닛을 기준으로 Flow Field를 생성하고 이동하도록 지정하여 위와 같은 이슈를 어느정도 해소할 수 있습니다.


<figure data-ke-mobilestyle="widthOrigin" data-origin-width="951" data-origin-height="473">
 
 <img src="https://blog.kakaocdn.net/dn/uet22/btrN3n8Tx2W/jnWVVhHd4LKHuemjvOk6I0/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="951" data-origin-height="473">
 
 
</figure>
엔티티가 1개, 10개, 200개 일 때 수치 비교를 해 둔 그래프입니다. 다른 기법과 비교한 그래프는 아니고, 엔티티 개수가 늘어나는 만큼 선형적으로 비용이 커지지 않는다는 부분을 어필하기 위해 작성된 비교입니다. 200개 엔티티인데도 1개일 때 보다 200배로 코스트가 늘어나지 않았으므로, 군중 유닛의 이동을 주로 사용하는 RTS 장르에서는 선택하기 좋은 솔루션으로 보입니다.


<h3 data-ke-size="size23">경험 및 후기</h3>
작년에 유니티 엔진에서 데디를 연동한 오토 배틀러 게임에서의 네비게이션을 작업해야 할 일이 있었습니다. 개인적 연구 용도였는데요, 해당 프로젝트에서 가장 골머리를 썩었던 부분이 데디서버의 엔티티 네비게이션을 각 클라이언트에 동기화 시키는 부분이었습니다.

유니티에 내장된 네비 메쉬 방식의 길찾기 솔루션은, 서버간 데이터 동기화에 필요한 일부 수치들을 유니티 코어에서만 소유하고 있고, C# 레이어로 노출시키지 않아 사용이 불가능한 수준이었는데요. 엔티티간 충돌에 따른 스티어링 처리에 대한 동기화가 불가능했기 때문입니다. Waypoint에 대해서는 동기화가 가능하지만, 데디서버에서는 해당 포인트대로 이동하지 않고 실시간 스티어링이 발생했고, 동적 엔티티로 인해 진입할 수 없는 위치에 대한 처리도 되어 있지 않아 어려움이 있었습니다.

어쩔 수 없이 그리드 방식의 A*를 직접 구현하여 서버-클라이언트 동기화에 사용하였고, 그리드에 맞게 캐릭터 래디어스를 지정해 동적 엔티티간 스티어링은 발생하지 않도록 처리해버렸던 경험이 떠오르네요. 시스템상 플로우 필드를 썼다고 해도, 그렇게 큰 효과를 보지 못했겠으나 당시에는 열심히 서치했음에도 플로우 필드 방식에 대한 정보를 전혀 얻지 못했어서 약간의 신기함과 아쉬움을 느꼈습니다.

이제 검색해보니 유니티 에셋 스토어에도 플로우 필드 기반의 네비게이션 에셋이 판매되고 있네요. 나중에 구매해서 살펴보고 디벨롭 해 볼 예정입니다.



참고 자료
<a href="https://www.gdcvault.com/play/1027659/Pathing-in-Age-of-Empires" target="_blank" rel="noopener">https://www.gdcvault.com/play/1027659/Pathing-in-Age-of-Empires</a>
<a href="https://howtorts.github.io/2014/01/04/basic-flow-fields.html" target="_blank" rel="noopener">https://howtorts.github.io/2014/01/04/basic-flow-fields.html</a>
<a href="https://www.youtube.com/watch?v=tSe6ZqDKB0Y">https://www.youtube.com/watch?v=tSe6ZqDKB0Y</a>&nbsp;
<a href="https://www.reddit.com/r/Unity3D/comments/p22zup/i_created_a_flowfield_utility_for_pathfinding/" target="_blank" rel="noopener">https://www.reddit.com/r/Unity3D/comments/p22zup/i_created_a_flowfield_utility_for_pathfinding/</a>
<a href="http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf" target="_blank" rel="noopener">http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf</a>
<a href="http://www.numerical-tours.com/matlab/fastmarching_0_implementing/" target="_blank" rel="noopener">http://www.numerical-tours.com/matlab/fastmarching_0_implementing/</a>
 
 
 </div></div>

Fireplace

samueljeon

GDC 2022에서 발표된 에이지 오브 엠파이어 4 엔티티 네비게이션 AI를 위해 사용된 기법입니다.
자세한 내용은 셰이더 스터디 카페를 참고 부탁드립니다.
본 기록은 발표 내용을 개인적 이해와 함께 재구성한 것입니다. 
발표자분의 의도와 다를 수 있으며, 잘못된 내용이 있을 수 있으니 양해 부탁드립니다.
 
발표 내용
 
에이지 오브 엠파이어는 많은 수의 엔티티가 실시간으로 동시에 길을 찾아 이동하고 전투를 수행해야 하는 RTS 게임입니다. 일반적으로 액터의 길찾기는 A* 알고리즘을 통상적으로 사용하는데요. 상호 작용이 가능한 동적 오브젝트를 고려하면 매 프레임 계산을 수행해야 하고, 길을 찾으려는 엔티티 수가 늘어날 수록 연산은 더 많아지고 비싸지게 됩니다. 더구나, 다른 오브젝트를 피하기 위해서 Steering을 수행하는데, 이 Steering을 통해서 수립된 새로운 경로가 항상 진행 가능하다는 법도 없어서 확실한 대안으로는 보기 어렵습니다.
 
이 세션에서는 Flow Field를 이용해서 군중의 길찾기 중복 계산 비용을 줄여보겠다는 아이디어에서 출발합니다.
 
그리드별로 코스트를 계산하고, 인접한 셀의 수치를 토대로 플로우 필드를 제작합니다.
 
 
이렇게 플로우 필드를 이용하면, 모두 다른 위치에 존재하는 엔티티들을 한 지점으로 이동시키려고 할 때 하나의 플로우 필드를 이용해 경로를 결정할 수 있습니다. 이 플로우 필드를 제작하는 비용이 저렴한 것은 아니지만, 비용 대비 좋은 퀄리티를 내기 위해 여러가지 기법을 섞어 시도했다고 합니다.
 
Hierarchiocal A* Pathfinding에 착안하여, 모든 그리드에 대해 단일 플로우 필드를 생성하는 것이 아닌, 일정 그리드 크기 별로 셀을 만들고 Line Of Sight 기준으로 포탈을 선정하여 Nav Mesh와 유사한 방식으로 노드를 구성합니다. 그리고, 셀과 셀을 이동하기 위해서는 포탈간 노드를 사용하고, 셀 내에서 포탈까지 이동하기 위해서는 플로우 필드를 사용하는 하이브리드 방식입니다.
 
 
그런데, 한계가 존재합니다. 싱글 셀을 기준으로 계산을 하면 포탈의 위치에 따라 어색하게 이동하는 듯 한 부분을 확인 할 수 있습니다. 이를 보완하기 위해 인접한 셀까지는 함께 계산하여, 비용을 조금 투자하되 경로가 보다 합리적으로 보이도록 보정 효과를 도모했습니다.
 
 
 
그리드 기반인 만큼, 다양한 크기의 유닛에 대해서는 처리할 수단이 필요한데요, 빨간 유닛은 3 x 3으로, 2 그리드 크기의 공간을 통과할 수 없습니다. 그런데 녹색 유닛은 통과할 수 있습니다. RTS 에서는 다수의 다른 유닛을 한 번에 선택하여 단일 지점으로 이동시키는데요, 이런 예외가 관리되지 않는다면 두 종류의 유닛이 다른 길로 이동하게 될 것입니다. 비용상으로는 합리적인 선택이지만 플레이어가 기대하는 동작은 아닐 것입니다.
 
 
이런 경우, 선택된 유닛 중 가장 큰 사이즈 유닛을 기준으로 Flow Field를 생성하고 이동하도록 지정하여 위와 같은 이슈를 어느정도 해소할 수 있습니다.
 
 
엔티티가 1개, 10개, 200개 일 때 수치 비교를 해 둔 그래프입니다. 다른 기법과 비교한 그래프는 아니고, 엔티티 개수가 늘어나는 만큼 선형적으로 비용이 커지지 않는다는 부분을 어필하기 위해 작성된 비교입니다. 200개 엔티티인데도 1개일 때 보다 200배로 코스트가 늘어나지 않았으므로, 군중 유닛의 이동을 주로 사용하는 RTS 장르에서는 선택하기 좋은 솔루션으로 보입니다.
 
 
경험 및 후기
작년에 유니티 엔진에서 데디를 연동한 오토 배틀러 게임에서의 네비게이션을 작업해야 할 일이 있었습니다. 개인적 연구 용도였는데요, 해당 프로젝트에서 가장 골머리를 썩었던 부분이 데디서버의 엔티티 네비게이션을 각 클라이언트에 동기화 시키는 부분이었습니다.
 
유니티에 내장된 네비 메쉬 방식의 길찾기 솔루션은, 서버간 데이터 동기화에 필요한 일부 수치들을 유니티 코어에서만 소유하고 있고, C# 레이어로 노출시키지 않아 사용이 불가능한 수준이었는데요. 엔티티간 충돌에 따른 스티어링 처리에 대한 동기화가 불가능했기 때문입니다. Waypoint에 대해서는 동기화가 가능하지만, 데디서버에서는 해당 포인트대로 이동하지 않고 실시간 스티어링이 발생했고, 동적 엔티티로 인해 진입할 수 없는 위치에 대한 처리도 되어 있지 않아 어려움이 있었습니다.
 
어쩔 수 없이 그리드 방식의 A*를 직접 구현하여 서버-클라이언트 동기화에 사용하였고, 그리드에 맞게 캐릭터 래디어스를 지정해 동적 엔티티간 스티어링은 발생하지 않도록 처리해버렸던 경험이 떠오르네요. 시스템상 플로우 필드를 썼다고 해도, 그렇게 큰 효과를 보지 못했겠으나 당시에는 열심히 서치했음에도 플로우 필드 방식에 대한 정보를 전혀 얻지 못했어서 약간의 신기함과 아쉬움을 느꼈습니다.
 
이제 검색해보니 유니티 에셋 스토어에도 플로우 필드 기반의 네비게이션 에셋이 판매되고 있네요. 나중에 구매해서 살펴보고 디벨롭 해 볼 예정입니다.
 
 
 
참고 자료
https://www.gdcvault.com/play/1027659/Pathing-in-Age-of-Empires
https://howtorts.github.io/2014/01/04/basic-flow-fields.html
https://www.youtube.com/watch?v=tSe6ZqDKB0Y 
https://www.reddit.com/r/Unity3D/comments/p22zup/i_created_a_flowfield_utility_for_pathfinding/
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf
http://www.numerical-tours.com/matlab/fastmarching_0_implementing/

Shader Study 후기 - Flow Fields and Steering Behaviors [GDC 2022: AOE IV] (22/10/05)

댓글