이 예제는 A*(에이스타) 알고리즘으로 구현한 길찾기입니다. 원래대로라면 맵 가로 사이즈 * 세로 사이즈 만큼의 변수가 필요하나, 길을 찾을 가능성을 줄이는 대신 변수 25개와 스위치 2개만으로 구현하였습니다(변수는 중복해서 쓰면 20개 이하 가능).

 

 

 

알고리즘 설명

 

 

 

원래대로라면 이런 길찾기 류의 알고리즘은 맵의 X, Y 좌표가 0,0 인 곳 부터 시작해서 맵의 제일 오른쪽 아래까지 하나하나 번호를 부여한 뒤 그 번호에 해당하는 변수에 검사를 했는지 아니면 장애물은 있는지 등등의 값을 저장하여야 합니다. 그런데, 맵은 최소 20 * 15 사이즈이므로 최소 300개의 변수가 필요하다는 말이 되고, 그렇다면 아무리 커야 70 * 70 정도 맵 밖에 만들 수 없을텐데(변수는 최대 5000개 사용 가능), 그 말은 즉 게임에 길 찾는 기능밖에 못 넣는다는 말이 됩니다. 그렇기 때문에 이 알고리즘은 길을 찾을 수 있는 가능성을 어느정도 줄인 대신, 주인공의 사방에 있는 8개의 칸, 즉 왼쪽 위, 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래 만을 사용하여 연산합니다. 이 방법을 사용하면, 맵이 길 찾기가 어느정도 쉬울 경우, 또는 매우 복잡하지만 외길인 경우에 밖에 찾아낼 수 없기는 하지만, 맵의 크기에 전혀 구애받지 않으며, 변수의 사용이 지극히 적다는 장점이 있습니다. 또한, 약간 개조하면 움직이는 목표에 대해서도 적용할 수가 있습니다.

 

먼저 루프를 돌립니다. 그 후 주인공의 왼쪽 위, 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래의 순으로 지형 ID를 구합니다. 지형 ID가 11(데이터베이스에서 장애물 지형을 따로 만들어줍니다. 참고로 좌표 바깥의 ID는 바다의 아이디라서...바다가 장애물이면 좀 난감해집니다..길을 잘 못찾음..그러니 바다가 장애물일 경우 바다도 지형 아이디를 바꾸어주세요)일 경우 장애물로 인식하고 65535 값을 줍니다(어느정도 큰 값을 주면 됨). 장애물로써 처리하고 싶은 지형은 ID로 식별하면 되고 이벤트를 장애물로 처리하고 싶으면 이벤트 ID로 식별하면 될 것입니다. 만약 상층 칩에 있는 것을 장애물로 하고 싶으면 상층칩의 오브젝트 위에 이벤트를 올려놓으면 될 것입니다.

 

만약 장애물이 아닌 경우, 먼저 목표물과의 X축 거리를 구한 뒤 Y축 거리를 거기에 더하고, 대각선인 경우 1.4(√2의 근사값), 대각선이 아닌 경우 1을 더합니다. 그런데 소수점이 지원이 안되므로, (목표물과의 X축 차이 + 목표물과의 Y축 차이) * 10 + (대각선인 경우 14, 아닌 경우 10) 의 값을 갖게 합니다. 대각선이라는 말은, 주인공이 이동할 경우에 대각선이 되는 위치, 즉 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 뜻합니다.

 

이 알고리즘은 자신이 어디서 왔는지는 알 방법이 없으므로, 이전에 이동한 방향을 기억해서 그것을 알아내는데, 가령 자신이 방금 오른쪽으로 이동했다면, 왼쪽에서 왔을 것입니다. 자신이 있었던 곳을 기억하는 이유는 물론 왔던 곳으로 다시 돌아가지 않게 하기 위해서죠.

 

그 후 만약 주인공의 위에 장애물이 있는데 주인공이 왼쪽 또는 오른쪽으로 가고 있었고, 진행 방향에 장애물이 없다면 그대로 가게 합니다. 관성이라고 표현하겠습니다. 즉, 벽을 따라가게 하는거죠. 훨씬 길을 잘 찾게 됩니다.

 

그 다음으로는, 대각선 이동을 하게 될 경우 만약 왼쪽 위로 이동하는데 위와 왼쪽에 장애물이 있으면 이동을 못합니다. 대각선 이동의 경우를 설정해줍니다.

 

아까 주인공 주위 8칸에 저런 숫자들의 값을 넣었는데 그 이유는 가장 작은 값을 가지는 쪽으로 가기 위해서입니다. 그리고 있었던 곳을 기억하는 이유는 저 식대로라면 자신이 왔던 곳이 더 작은 값을 가지는 경우가 빈번하기 때문입니다.

 

 

 

 

이 알고리즘은, 정확성(최단 거리가 아닌 최단거리에 가까운 거리를 찾을 가능성이 있습니다)과 가능성(길을 못찾고 뱅뱅 돌 수도 있습니다)이 약간 낮지만, 대신 사용하는 변수가 극히 적어서, 어느 게임에서나 사용할 수 있습니다. 그렇다면 이걸 어디다 쓰느냐? 제 생각에는 액션 알피지를 구현할 때 몬스터 또는 동료가 길을 찾는데 쓰면 좋을 것 같습니다. 이 알고리즘대로 써도 움직이는 목표를 따라갑니다. 그런데 약간 수정이 필요할 것이라고 말한 이유는, 만약 자신의 오른쪽에 몬스터가 있어서 오른쪽으로 갔는데, 몬스터가 순간이동을 해서 왼쪽으로 갔다면, 이 알고리즘은 방금 지나온 곳은 한칸을 더 가기 전에는 지나지 않으므로 약간 우회하게 됩니다. 그러나 몬스터의 이동속도가 그다지 빠르지 않고 순간이동 같은 것도 하지 않는다면, 이대로 써도 괜찮을 것입니다. 보통 액션 알피지에서 이동 루트를 주인공에게 다가감으로 설정할 경우, 장애물에 걸쳐서 못 오는 바보 몬스터를 보게 됩니다. 하지만 이 알고리즘을 사용한다면 조금 덜 바보를 보게 되겠지요.

 

 

예제 다운로드 : https://www.acoc.co.kr/bbs/data/acoc_board_ideatip/Pathfinder.zip

처음 맵은 직접 미로를 만들 수 있습니다. 첫번째 맵에서 목표에 도달하면 두번째 맵으로 가는데, 두번째 맵에서는 주인공을 다른 캐릭터가 쫓아옵니다.