[💬] 길찾기 알고리즘 질문있음

[청작(qingque)]

이산구조를 띄는 격자맵에서 길찾기 알고리즘은 대충 shortest path 문제 푸는 알고리즘으로 알고 있는데

와우나 스타크래프트 같이 맵이 격자구조를 띄지 않는 게임에도 격자맵에서와 똑같은 길찾기 알고리즘을 적용하는지가 궁금함

아니면 모니터 액정이 격자구조로 보이지 않지만 격자구조인것처럼

플레이환경에서만 격자구조로 보이지 않을뿐이고, 실제 개발환경에서는 격자구조로 되어있는거야?

게임개발하는 놈은 아니라서 잘 알거같은 여기에 질문함

[익명(usnned)]

Navigation Mesh

[청작(qingque)]

ㄱㅅㄱㅅ

[소닉쫄따구테일즈(dcz3xv7zgu14)]

스타1은 타일맵길찾기. 스타2는 타일맵+내비메시 혼합

[ㅇㅇ 1(118.235)]

흔히말해 길찾기 알고리즘들은 경로가 주어질경우 최단,최적의 경로 알고리즘 이고 질문자가 궁금해하는건 노드(경로)목록을 만드는이슈인듯.. 다른사람들이 말한거지만 네비메쉬를 그래서 쓰는거구

[ㅇㅇ 1(118.235)]

일반적인 타일기반에서는 타일하나를 중점을두고 인접타일의 거리 비용등을설정해두고 경로를두고, 네비메쉬는 convexhull 같은 알고리즘으로 메쉬를 블록화 해서 하나의타일로 만듬 나머지는 비슷

[ㅇㅇ 1(118.235)]

convexhull 검색해서 이미지만봐도 대충 어떤건지 알꺼임

[ㅇㅇ 2(14.32)]

그래프만 구성할 수 있으면 뭐든간에 알고리즘 적용 가능함. 어떻게 그래프를 구성할까의 문제임.. 스타1 같은 경우는 성능이슈 때문에 쿼드맵 같은거 구성한걸로 알고있음

[ㅇㅇ 2(14.32)]

쿼드맵 아니고 쿼드트리

[리슬링?(lucid74)]

스타 길찾기 구현은 A* 기반으로 했긴함
https://m.clien.net/service/board/park/14602883

[리슬링?(lucid74)]

region으로도 나누는데 스타도 결국 격자 기반으로 나누는거임