유니티에서 NavMesh의 기능의 장,단점이 궁금합니다.

Question

유니티로 포트폴리오 제작중인데 틈틈이 자료구조랑 알고리즘도 조금씩 공부했습니다.

c++로 A* 알고리즘을 직접 다 구현했는데 이걸 포트폴리오 프로젝트에 적용하고 싶은데

유니티는 네브매쉬라는 으마으마하게 편리한 기능이 있어서...

네브매쉬 안쓰고 a*를 적용한 포트폴리오를 만들었다 쳤을 때 나중에 면접관님이

"유니티에는 네브매쉬기능이 있는데 왜 굳이 a*를 썼느냐?" 하면 뭔가 딱히 할 말이 없을 것 같습니다.

 

 그래서 제가 고수님들께 질문드리고 싶은건 유니티에서 NavMesh대신 a*를 써야할 상황은 어떤 상황인가? 입니다.

 즉 NavMesh의 단점을 물어보는 질문이기도 하고 유니티에서의 a*의 장점을 물어보는 질문이기도 합니다.

 혹시 이러한 문제에 대해서 좋은 말씀 남겨주시면 감사하겠습니다.

Answer 1

Deterministic 문제 때문에 a* 를 썼다.

가 어떨까하네요.

Comments

정말 죄송하지만 좀 더 풀어서 설명해주시면 안될까요?? 따로 알아봐도 감이 잘 안오네요 ;;;

---

그렇군요...

Navimesh 도 a* 알고리즘을 사용하긴 하는데 기본적으로 유니티 엔진 연산으로는 결정론적(Deterministic) 코드가 되지 않습니다.  유니티라서 그런건 아니고 정확히는 부동소수점 오차의 문제인데.

그렇다면 왜 결정론적일 필요가 있어야 하는가라면..

스타크래프트 같은 RTS 게임에서는 1플레이어가 제어하는 유닛이 100~200에 이르게 됩니다.  이 많은 오브젝트의 상태를 동기화 하기란 쉽지 않지요.  그래서 전통적으로 락스텝(인풋 동기화)을 이용하는데 이 것의 핵심은 '동일한 입력을 넣었을 때 동일한 계산이 보장된다' 입니다.

즉.. 개발을 쉽게하려고 유니티 엔진을 이용하는거지만, 이러한 상황 때문에 결국 고정소수점(Fixed Floating point)를 구현(혹은 라이브러리 사용)과 함께 직접 a* 이용하여 계산하는 상황이 생깁니다.

---

다시 좀더 쉽게 요약해보면..

클래시로얄의 프로토타입을 구현해보려하는데 서버 연산 비용과 통신 트래픽을 절약하기 위해
락스텝을 활용(Input만 동기화)하기로 결정했습니다.

그렇다면 플레이어 1과 2는 조작 내용만 서로에게 전달하고 연산은 각각 알아서 해야합니다.
(즉 Deterministic해야합니다)

아래 상황에서 플레이어1 이 유닛1개를 특정 지점으로 이동했을 때

'이동하라는 명령'만 전송을 해도 플레이어1과 2의 결과 화면은 항상 같아야 합니다.

 

이때, Navimesh을 이용한다면 50번 스텝만 넘어도 오차가 발생할 것입니다.

하지만 부동소수점과 a*를 직접 활용하여 계산하면 수백만번 반복해도 항상 같은 결과가 나올 것입니다.

---

면접을 준비하기 위해 질문을 하셨는데 불친절한 답변을 드린 점 사과드립니다...

원하시는 곳에 합격하시길 기원합니다.

---

너무나도 큰 도움이 되는 답변이였습니다.

이런 귀한 지식을 알려주셔서 정말 감사합니다.

세상은 아직 살만하군요 ㅎㅎ

Answer 2

유니티의 navmesh도 a* 알고리즘을 사용합니다.;;;

지형의 폴리곤을 raw 데이터로 하여 네비게이션용 데이터를 따로 생성하고 이 데이터를 이용해서 A* 를 돌려서 최적의 경로를

찾고 이 경로대로 이동시키는 방식입니다.