프밍 고수님들께 질문

[익명(175.125)]

이동하는 물체와의 최단 경로를 추적해서 따라가는 알고리즘 같은 게 있음?

대충 추적 알고리즘이라고 해야 하나?

길찾기 알고리즘인 A*로도 실시간으로 계속 이동하는 물체와의 최단 경로를 딜레이 없이 빠른 시간 안에 찾을 수 있어요?

대충 맵은 1000*1000 내외일 것 같은데..

[AA(59.28)]

게임에 쓸꺼라면 A*는 안될듯, 스타 유닛 같은 이동은 훨씬 빠른 알고리즘을 사용할듯 물론 일정 복잡도가 넘으면 길을 못찾는게 함정

[익명(175.125)]

스타크래프트도 A*알고리즘을 사용한다고 들었는데 아니었나봄??

[AA(59.28)]

A* 는 기본적으로 가는길이 있다고 간주하고 알고리즘에 따라 가능성이 높은 경우부터 모든 길을 다 탐색함, 이런건 게임에서 쓸수 없져,,

[익명(175.125)]

그럼 게임에서 쓸 만한 알고리즘 뭐 없을까

[darth마교(59.25)]

스타가 뭔 A*을 쓰냐. 최소 쿼드트리로 멥 탐색해나가지.

[AA(59.28)]

글쎄 일단 A*에서 탐색 회수를 제한 하는 방법으로 구현 하는것도 고려 해 볼수 있을듯.. 또는 Asynchronous A* 라고
http://easystar.nodejitsu.com/demo.html
같은 거도 살펴볼만 할듯

[darth마교(59.25)]

ㄴ화아 정말 모든게 다 JS로 나오네

[익명(175.125)]

타겟이 실시간으로 움직여도 저게 가능하려나

[darth마교(59.25)]

실시간이라는게 프레임과 연산비용에 따라서는 정지상황이야.

[AA(59.28)]

스타처럼 실시간이 중요시 되는 경우엔 알려진 길찾기 알고리즘이 아니라 아마도 유닛에게 작은 인공지능을 부여 해서 순간순간 판단 하도록 만들었을꺼라고 추측됨, 즉 길을 찾는게 목적이 아니라 길을 가는게 목적임, 그래서 스타 유닛은 멍청하게도 길을 못찾고 왔다리 갔다리 하는경우를 보게 됨 ^^

[darth마교(59.25)]

ㄴ그러게. 길찾기가 최소 2가지로 예상되는데 화면 안에서의 길찾기와 화면 밖으로의 길찾기가 다르고, 근처 유닛간 길찾기 데이터 통신도 그룹으로 할거 같기도 하고.

[darth마교(59.25)]

재밌는건 유저가 명령내리고 나서 인터벌이 있어. 잠깐 멈칫 하는 텀이 있더라고. 20년전에 나온게임이니, 그런 방법으로 성능을 올리는등 다양한 편법?(길찾기 알고리즘만이 아닌 방법들) 이 많이 쓰여졌더라고.