2004년도에 홈페이지(오군닷컴) 에 올렸다가, 홈페이지 관리가 너무 힘겨워(^^) 거의 잊고 지냈는데,

요즘 회사에서 또 A*를 하다보니 문득 생각나, 블로그로 옮겨 봅니다.

============================================================================================

- 길찾기 알고리즘 - A* 알고리즘

지금도 A* 알고리즘의 정확한 의미를 잘 모르겠습니다.

몇권의 책과 인터넷 사이트를 뒤져보았지만, 무슨말인지 하나도 모르겠더군요.

분명 설명은 자세하게 나와있는데 말이죠. (뭔가 추상적이고~ 형이상학적인...)

그래서 저는 A* 알고리즘을 풀어서 설명하기 보다는, 이 알고리즘을 이용해서

길찾기 프로그래밍을 할 때 어떠한 방법으로 해 나가는 것인지에 대해서 설명 하겠습니다.

순수하게 코딩을 하는 방법에 대해서만..

사실 그 밖의 다른 부분에 대해서는 저도 잘 모르겠어요.ㅡ,.ㅡa

일단 A* 의 간단한 정의와 짧은 설명(정말짧은)일 먼저 한 후 시작하겟습니다.

A* 라는건요.

시작지점부터 목표지점까지 인접한 위치들을 검색해서 가장 효율적인 길을 찾는방식입니다.

여기서 효율이라는것은 상황마다 틀릴테지만, 타일의 갯수라고 보면 되겠죠?

시작지점부터 인접한 타일들을 검사해서 가장 목표지점에 가까이 있는 타일들을 하나씩

밟아 나간다고 보면 됩니다. 징검다리처럼요.

뭐 장애물도 없고 직선거리로 무조건 움직이는 것이라면, 화면상에서 제일 가까운

타일이 되겠지만(주로 비행유닛이 그렇죠?), 장애물이 있다면 예기가 달라지죠?

어떤게 제일가까운 건지 어떻게 알겟습니까?

그래서 다음과 같은 방법을 사용합니다.

일단 화면에 7 X 7 의 타일들일 쫙~ 깔려있다고 가정하고,

파란점을 시작지점, 빨간 점을 도착지점이라고 합시다.

유닛이 파란데 서있고, 마우스로 빨간데 눌렀다고 생각하면 되겠죠?

주변 타일들의 검사는 목표 지점에서 부터 시작지점으로 거꾸로 해 올라옵니다.

일단 빨간점에 0 이라는 번호를 부여하고, 빨간점의 주변 8개 타일을 검사해서,

 

주변 타일들은 그보다 1 큰 숫자를 부여합니다. 다음은 주변 타일들위주로, 각각의 주변을

또 검사합니다. 

이렇게 계속 검사 하게되면, 결국 끝가지 갑니다.

뭐 중간에 시작지점을 만난다면 더이상 할 필요가 없겠지만, 아무튼 끝까지 합니다.

물론 장애물 부분은 검사할 필요가 없겠죠?

이렇게 하면 타일마다 숫자가 새겨지게 되니다. 파란점에 있는 유닛은 이 검사를

마치게 되면 그냥 작은숫자만 따라서 이동하면 되지요.(노란 숫자)

타일 전체를 검색해서 목표지점부터 시작지점까지를 숫자의 연관성으로 이어

이 숫자를 따라간다.

라고 하면 정의가 될까요? 아무튼 기본 원리는 이렇게 됩니다.

이걸 액션 스크립트에서 어떻게 적용 시키는가 하는 것이 문제인데요.

제가 참고했던 책 ISOMETRIC GAME PROGRAMMING WITH DIRECTX 에서는

각각의 타일에 다음과 같은 변수를 두고,


x,y = 타일의 좌표 (integer)

mark = 검사여부 (Boolean) 기본은 false 이다.

num = 위의 검사시 사용하는 숫자 (integer) 기본은 -1



전체 타일을 검색 -> 시작타일 num 에 0 값을 부여, mark 는 true ->

전체 타일을 검색 -> 0주변의 타일의 mark에 true를 표시 ->

전체 타일을 검색 -> mark 가 true 인것을 기준으로 주변 검색 ->

주변 타일의 num 값 부여, mark 를 true로 바꾼고 현재타일의 mark 는 false로 변경 ->

계속 반복.


대랸 이러한 과정을 전체 블럭이 모두 검사될때 까지 반복합니다..

위와 같이 작업을 한 후, 타일수를 20 X 20 늘렸더니, 한번 클릭해서 유닛이 길을 찾는데

거의 1초 가깝게 걸리더군요. 아무래도 이걸 가지고는 어디 써먹을 수가 없어서,

한동안 골머릴 써가며 다음과 같이 바꿨습니다.

타일의 멤버 변수는 다음과 같이 하고,


x,y = 타일의 좌표 (integer)

num = 위의 검사시 사용하는 숫자 (integer) 기본은 -1


글로번 변수로 배열을 하나 준비합니다.


checks = 검사 가능한 타일을 배열로 저장한다.


그리고 스크립트를 다음과 같이 수정합니다.


전체 타일을 검색 -> 시작타일 num 에 0 값을 부여, 주변타일을 검사해서 checks 에 push->

checks 에 들어있는 타일갯수만큼 반복 -> 주변의 타일을 검사해서 checks2 에 넣는다 ->

checks 검사가 끝나면 checks2 를 checks 에 복사

checks 에 데이터가 없을때까지 계속 반복



전체 타일검사를 단 한번으로 줄였습니다.

나름 대로 뿌듯해서 실행을 해보니, 그래도 좀 느리더군요^^a

속도 개선을 위한 노력은 계속 해야되겠습니다.

일단 실행하기 불편한 정도는 아니니 그냥 가려고 하는데요.

아무래도 그냥 쓰기에는 좀 부족함이 있거든요.

더 좋은 방법아시면 추천좀 해주세요~