마로의 꿈 8방향 길찾기 알고리즘 확장하기

마로의 꿈 책을 보고나서 카페에 올린글

윈도우,유닉스를 넘나들며 c,vc++만 십수년 해왔지만,
올해 이나이에 플래시 as3.0은 처음 이라서,, 특히 게임은... 질문을 하지 않을수 없었다.
그렇지만 이럴다 할 답은 얻지 못하였고 결국 본인 스스로 해결할 수 밖에..^^

질문의 원문 

현재 마로의 꿈(도서명) 의 길찾기는 A+ (4방향), 따라서 무조건 빙 돌아가는 형태로 작동되는 듯합니다.(적색부분)

(즉,현재 시작좌표에서 목표좌표의 Y값이 일치할때 까지 내려오다 일치하면 X방향으로 일치할때 걷는 형태)

물론 장애물 유닛을 타일어느곳에 까냐에 따라 유연하게 작동하겠고,,

각자의 게임성향이 다르므로 어떻게 변형,적용하냐의 문제이지 길찾기 알고리즘 하나만 놓고 그 자체로 맞다 틀리다

의 논리는 순전히 알고리즘 자체 갖고서는 아니라고 생각합니다..

 

따라서 마로의 꿈에서 제시한 부분은 마로의 꿈에서는 맞는것이고 이를 좀더 확장하여 자신의 게임에 적용하고자 할때,

저처럼 이것을 만약 최단 노선으로 이동을 원한다면,아마도 대각선 방향까지 추가하여 처리해야 겠습니다..

 

대각선 뱡향(화면상에서는 정 동서남북방향) 4곳을 추가하여 총

8방향 A*로 하려면 (4방향 + 에 대각방향 x 를 추가하여 표기상 * 가 된듯?ㅎㅎ 전산용어 star형 개념이겠지만)

먼저,좌표타일 값으로 계산한 goal을 휴리스틱 계산부분처럼 그래픽 직선거리로 변경해야 할겁니다.

 

그다음에,기존의 휴리스틱값과 + 하여 적합도를 찾고 그러면, goal 값이 대각방향노선거리인 ⓑ가 더 적으므로,

(교재 p 211쪽 35.77708 이 바로 이 대각선 노드길이) 우선 탐색이 되고, 노란색 예상이동 경로와 같이 접근할듯 합니다.

ⓐ 값은 직사각형(32by16) 대각선 길이 공식에 (32제곱+16제곱)의 루트 에 의해 35.77708 이 나오고 ⓑ값은 직선거리이므로,

그리드크기*2인 32가 나옵니다. 따라서 ⓑ가 goal값이 더 작게 나오게 되므로..

 

* 이값은 타일크기 10일 경우,22.360679774997896964091736687313 가 나옵니다..

 

그리고 ,walkHandler()에서 방향 조정해주시고,, 예를 들어 아랫쪽 대각방향은 그래픽 좌표인 operationXSign은 불변이므로 0,

p199 쪽 changeDirection() 에 각각 추가 정의한 AVATAR_TOP,AVATAR_BOTTOM,AVATAR_RIGHT,AVATAR_LEFT 처리 해주시고,,,,

p204 쪽 linkUpImages() 에서 추가된 방향에 적합한 이미지 연결해주시고 등등...

 

실제 코드를 테스트 전이지만, 연구(?) 결과 이렇게 가야 할 듯하네요..

그리고 게임방식이 빙돌아가거나 그런 유닛이동을 원한다면 마로의 꿈 방식대로 4방향 그대로 가거나

총 8방향으로 추가하면서 대각방향 goal 계산을 타일 좌표단위로 하여 우선권에서 배제시키는 마로의 꿈 방식으로 갈수 있겠네요..

즉,8방향 추가없이는 기존의 4방향으로만 단지 PathFinder.as 의 calculateGoalBetweenNodes()에서의 goal값만 그래픽좌표 길이로 변경계산한다 해도 4방향인 이상 타일좌표 쓰는것과 동일한 결과가 될겁니다..

마찬가지로 8방향 추가하였는데 goal값을 타일좌표로 계산해도 안되구요...

같은 고민하시는 분께 도움이 되길...

^^

P.S: 좀더 찾아보니 휴리스틱 구하는 부분은,
대각선 직선거리 대신 http://www.policyalmanac.org/games/aStarTutorial.htm 에서 제시하는 맨하탄 방식으로 해야,

isometric나 아래 그림 처럼 일반 정사각형 타일에서 모두 적용되는군요..

*추가설명:

[그림에서 좌측은 G비용 우측은 맨하탄식 H비용을 뜻함]

H 비용 구할 때,직선거리 대신에 맨하탄방식(Manhattan method) 으로 해야 할 듯하다.
즉, 대각노선을 제외한 가로와 세로로만 이동할수 있는 칸수 X 타일간의 이동거리인(여기서는 ISOmetric 이므로 유닛그리드가 10 이면 즉,유닛타일의 크기가 40x20 을 의미하면, ISOMetric에서의 정방향 타일은 각 정방향 타일사이의 이동거리는 22.360679774997896964091736687313 가 되므로, 대략 22로 치자면 (22 x 앞으로 갈 타일수)로 계산이 가능하다.
또,ISOMetric의 특성상 각 타일의 G 비용 역시 22가 되고, 대각방향(화면상에서는 상하좌우방향)의 타일은 20이 된다.