안녕하세요, 안영기님...
오늘도 당혹스러운 질문을 들고 왔습니다.
지난번의 스택 큐 이야기는 그냥...
접어두는 게 나을 듯 싶습니다... ^^;
AVEJ같은 식의 이동 방식을 사용하는 게임에서 NPC를 특정 위치에서 특정 위치로 이동시키려고 합니다.
문제는 이 [특정 위치 1]와 [특정 위치 2]가 난수적으로 결정되고, 장애물들이 난수적으로 발생하기 때문에 매회 이동시 특정 위치 1에서 특정 위치 2까지의 최단경로를 검색해 줄 필요가 있으리라고 봅니다.
생각같아서는 Dijkstra법으로 그냥 메모리 쫘악 쫘악 낭비하면서 구현해버릴까 아니면 그냥 BFS탐색으로 Flood Fill을 돌릴까 생각하고 있지만 역시... 게임 맵이다 보니 그런 건 무리일 듯 싶습니다.
어떻게 묘책이 없을런지요...? 맵의 규모는 AVEJ에서 사람 하나를 표현하기 위해 사용된 칸을 한 칸이라고 가정할 때 가로로 1천칸, 세로로 1천칸 가량 되는 자그마한 규모입니다.
| #106-1. 안영기 |
2005/03/02 (Wed) |
가장 기본적인 길찾기인 A+ 또는 A* 알고리즘은 '대변 파이터 외전' 소스에 나와 있으니 그것을 참고 하시고 위와 같이 1000*1000에 동시에 길을 찾아야 하는 캐릭터가 많이 있다면 위의 알고리즘으로는 속도가 나지 않아서 많이 힘들 것입니다. 보통 이것에 관해서는 많은 토론이 있었고 인터넷에도 자료가 많습니다. 아마도 스타크래프트가 뜨게 되면서 '왜 저글링은 한 줄로 달려갈까?'라는 의문을 한 번에 풀어주는 것들이 많습니다. (기본적으로는 길찾기는 한 놈만 하고 그 뒤의 나머지는 자기 앞의 놈을 따라가도록 한다는 규칙입니다. 그런데 항상 문제는 중간에 맵에 변형이 생길 때인데 이때는 변화를 감지한 놈부터 다시 계산을 해주고 그 놈 뒤의 놈들은 다시 그 놈을 따르게 하는 것이 아닌가 생각되는군요.)
사실 A* 알고리즘은 미로 찾기나 좁은 공간에 대한 길찾기에는 높은 성능을 보이나 넓은 지형에 장애물이 별로 없는 곳에서는 성능적인 면이나 결과적인 면이나 모두 만족스럽지 못한 결과를 나타내게 됩니다. 그래서 그것을 보완하기 위한 것이 맵 로딩 시(또는 미리 만들어진) 각각의 복잡도에 따라 단위 구역을 나누고 그 구역끼리에 대한 최단거리를 미리 설정합니다. (이때는 각 구역에 대해서 Dijkstra 알고리즘을 적용할 수도 있습니다) 데자뷰에서는 원래 가고자 했던 길에 방해물이 생기면 그길을 회피한 후에 다시 최단거리로 돌아 오도록 했는데 이때 회피 방법은 각각의 경우에 대해 간단하게 판단 조건을 추가 했던 것 같습니다. 아마도 회피 방법은 게임의 방식이나 맵의 구조에 따라 새로 구성되어야 할 것 같네요. (정말 못빠져 나올 것 같으면 현재부터 다음 중간 경로까지 A*를 적용하는 것도 한 방법..)
그런데 가장 중요한 것은 만드시려는 게임에 맞게 새로운 알고리즘을 만드는 것이 가장 중요하다고 생각되어지는군요. 그 게임이, 루카스의 어드벤쳐 게임처럼 그래프형 길찾기가 될 수도 있고, 데자뷰 수준의 단순 길찾기도 있고, 소코반 형식의 A*가 어울리는 길찾기도 있을 것이고, 스타크래프트같은 다수의 객체가 한 위치로 이동하기 위한 길찾기도 있기 때문에 만드시려는 것에 가장 적합하도록 기존의 제너릭 알고리즘을 변형할 수 있어야 할 것 같네요.
추천도서는 Strategy Game Programming 어쩌고 하는 책(이후에 번역본도 나왔음)입니다 그리고 Game developer인가 하는 잡지(역시 번역본 있음)에서도 비교적 넓은 지형에서 간단하게 길찾는 얼고리즘이 소개되었던 것 같네요.
|
| #106-2. 그네고치기 |
2005/03/02 (Wed) |
조금 너무하는 질문인 듯 싶습니다만 하나 더...
우선 Strategy Game Programming 어쩌고 하는 책을 사러 가 봐야 겠습니다. ~_~;
방금 구글신의 도움을 빌어 A* 알고리즘에 대한 간략한 소개가 되어 있는 PDF파일을 찾았습니다.
... 끄응...;
여기 나와 있던 설명만 듣고 보니...
도대체 Priority Queue를 간단하게 적용한 BFS와의 차이를 느끼기가 힘들군요... ㅠ.ㅠ
G+H를 구하는 것이 단지 Queue에 들어가 있는 노드들의 우선순위를 지정해 주는 것 이상의 역할을 한다는 느낌이... 어째 잘 들지가 않습니다...
제가 받아들인 것이... 그나마 완전히 틀린 것은 아닌지... 혹은... 그럭저럭 제대로 찾아가고 있는 건지... 혹 알려 주실 수 있으신지요?
|
| #106-3. 안영기 |
2005/03/05 (Sat) |
A*는 Best-first search의 한 종류라서 그렇게 느껴질 겁니다. 그리고 실제로 8 방향의 그래프를 가지는 Breadth-first search입니다. (A+라면 4방향이겠죠. '*'와 '+'는 방향에 따른 모양이 형상화된 것입니다) A*는 간단한 알고리즘에 속합니다.
|
|