A* Path Finding Algorithm

안녕하세요 대학생 개발자입니다.

 

정말 오랜만에 블로그에 글을 남기는 것 같은데요...

 

이번 글에서는 길 찾기 알고리즘에 대해서 얘기를 해보려고 합니다.

 

길찾기 알고리즘은 길을 찾는 알고리즘이죠 말그대로

대신 시작점과 끝점이 주어졌을 때 가장 최단거리를 찾아주는 알고리즘이 되겠습니다.

게임을 플레이할때  분명히 벽넘어를 클릭했는데 벽을 피해서(우회해서) 목적지에 도착하는(+최단거리로) 그런 경우를 많이 보셨을 겁니다.

이런경우에는 길찾기 알고리즘에 의한 행동으로 보시면 될 것 같습니다.

 

그러면 바로 알고리즘에 대한 얘기를 해보겠습니다

먼저 이번글에서 소개할 녀석은 바로 A*입니다.

대부분 게임에서 에이스타를 많이 사용합니다( 물론 지금은 많이 느리기때문에 에이스타보다 더 좋은 길찾기 알고리즘으로 넘어갔습니다)

 

에이스타 알고리즘의 경우에는 생각보다 난이도가 꽤 있는 알고리즘입니다.

길찾기 알고리즘의 시작을 에이스타부터 하기 때문에 에이스타를 하기 전에 다익스트라 같은 알고리즘을 따로 공부를 하고 보셔야 이해가 쉬울 것 같습니다. 에이스타를 처음 보시는 분들이라면 자료구조 책을 정독하시고 그래프 직접 구현 가능 + 다익스트라 구현가능 정도까지 공부하신뒤 다시 이글을 보시면 좋을 듯합니다.

 

그럼 여기서 뒤로가기를 누르지 않으신 분들은 다익스트라 까지는 완벽하게 알고있다는 가정하에 시작하겠습니다.

 

우선 다익스트라의 경우에는  노드와 노드 사이의 간선의 가중치만을 이용해서 목적지를 찾아가는 알고리즘입니다.

물론 그렇게 되다 보니 모든 방향으로 퍼져 나가게 되고 모든 방향으로 나아가는 만큼 당연히 빠르게 찾아지지는 않습니다.

하지만 다익스트라와 A*의경우 상당히 비슷한 로직으로 되어있습니다. 특정 어떤 값이 가장 작은 노드를 꺼내서 그 노드를 기준으로 주변을 탐색한다는 점입니다.

다익스트라의 경우에는 시작점과의 거리가 되기 때문에 시작점과 멀어질수록 가중치가 커지게 되고 그렇기 때문에 가까운 곳부터 가게 되어서 모든 방향으로 퍼져나가는 모양이 된다는 점이 단점입니다.

에이스타는 이점을 약간 보안했다고 보시면 될 것 같습니다.

우선 거리에 대한 가중치의 설정은 동일합니다.

 

추가되는 점은 휴리스틱 추정 값이라는 내가 도착해야할 노드와의 거리 즉 도착지와의 거리를 기존 가중치와 더불어 같이 판단하는 요소가 되기 때문에 도착지에서 멀어진다면 가중치가 떨어지게 될것이고 우선적으로 탐색에서 배제되게 될 것입니다.

물론 휴리스틱이 들어간다고 길찾기 알고리즘이 아주 빨라지거나 그런것은 아닙니다. 어차피 최악의 경우에는 에이스타와 다익스트라는 다를바 없고 그렇기 때문에 노드 생성이 획기적으로 줄어드는 JPS나 그 외 다른 알고리즘을 사용하기도 합니다.

 

원리는 단순합니다.

기존의 다익스트라의 경우에는 가중치의 누적의 합이 가장 적은 노드를 선택하는 방향으로 갔었습니다. 그 값을 g(x)라고 부르겠습니다.

A*의 경우에는 다익스트라에서 사용되는 g(x)값에 추가로 아까 말씀드렸던 휴리스틱 추정값(h(x))를 통해서 값을 도출하며 이를 f(x)라고 부르겠습니다.

 

이를 f(x)가 작은 값이 먼저 나오게 되는 우선순위 큐에 넣게 되면 이때까지 삽입했던 가장 작은 f(x) 값이 튀어나오게 될 거고 그러면 그 방향으로 쭉 따라가게 되면 됩니다.

g(x)값은 노드가 멀어짐에 따라 비슷하게 증가하지만 h값은 방향성을 지니고 있기 때문에 어떤 노드를 고를때 방향이 정해지게 되므로 성능이 빨라지는 거죠!

 

음... A*알고리즘에 대한 이론적인 설명을 간략하게 하고 넘어가겠습니다.

휴리스틱을 구하는 방법은 여러가지가 있습니다.

 

먼저 멘헤탄 거리측정 방법이있구요. 이건 제가 쓴 방법이기도 하고 사람들이 실제로 가장 많이 쓰는 것 같습니다.

h = abs(dx) + abs(dy);

 

두번째로 유클리드 거리측정을 쓰는 방법이 있습니다. 유클리가 가장 아마 대각선에 대한 휴리스틱을 구할때 가장 정확할 겁니다.

하지만 단점으로는 소수가 나오기 때문에 버려지는 문제도 생길 수 있고 대각선과 직선사이의 값차이가 크게 나지 않기 때문에 가끔 더 빠른 길을 놓칠경우도 존재하구요... 아주 사소한 값차이로 인해서 제대로 못찾을때가 생각보다 많았던 것 같아요.

h = sqrt(dx*dx + dy*dy);

 

여기서부터는 구체적으로 무슨 의도로 만든 알고리즘인지 잘 모릅니다 허허 세번째로 옥타일 방법입니다. 옥타일은 대각선이나 90도이동을 선호한다고 하는데 제가 안해봐서 잘모르겠습니다 허허...

 

그리고 마지막으로 체비셰프 입니다 얘는 좀 간단하죠? 둘중에 큰값을 넣어버리네요 그냥

제 추측상 한방향으로 부채꼴모양으로 넓어지는 형태로 탐색하는것 같은데... 전방에 긴 벽이있다면 효율적일거 같아보여요 느낌에 뭐 이것말고도 다른 이유가 있겠죠? 째뜬 얘는 이렇습니다.

max(dx, dy)

 

저는 멘헤탄 휴리스틱을 사용했구요.

상하좌우로 움직일땐 G += 10

대각선일 경우에는 G += 14

이렇게 증가시켜 가면서 합니다. 뭐 나름 정확하게 나옵니다 2제곱이 1.414 이니까... 0.014 이하 자리수는 버린거에요

 

A*알고리즘에 대한 이론적 설명은 간략하게 하겠습니다.

상하좌우 -> G값 += 10

대각선 -> G값 += 14입니다.

AStar::PathNode* AStar::FindPath(int beginXPoint, int endXPoint, int beginYPoint, int endYPoint)
{
  	while(오픈리스트가 빌때까지)
	{
      	오픈리스트에서 가장 F값 작은거 뽑기
      	목적지인지 확인후 리턴
        
      	오픈리스트에서 제거하고 클로즈 리스트로 옮기기.
      	방금 꺼낸 사각형 주위 8방향 탐색
          	-> 갈수 없거나 클로즈 리스트에 있는거라면 하지않음
          	-> 오픈리스트에 없으면 넣음
              	-> 부모를 방금 꺼낸 노드로 지정
            -> 만약 오픈리스트에 있는거라면 G값을 계산해서 더 나은 경로인지 확인
              	-> 만약 더나은 경로라면 새로운 G값을 통해서 F값 계산
	}
}

네... 뭐 큰 로직 덩어리는 대충 이런 것 같습니다.

 

음... 이거 알고리즘에 대해서 모두 설명하는것은... 구글에 더 자세히 적혀있기 때문에 제가 한번더 정리하는것은 시간소모라고 생각합니다... 그래서 적지 않고 넘어가겠습니다. 

대신 소스코드를 깃허브에 업로드 해뒀습니다. 아마... 함수 하나에 8방향에 대한 로직처리 + 그외 G값 재설정 등 모든 로직을 다 때려박아놔서 엄청 코드가 길어질겁니다... 찾아서 보시는건 좋습니다만 맛없는 스파게티를 보고 놀라시면 안됩니다.

 

후... 요새 글을 올릴 시간이 너무 없습니다 ㅠㅠ ... 과제도 과제도 하는일이 요새 매우 바빠졌기 때문입니다...

그래서 이번 글이 많이 성의가 없었습니다... 물론 제가 보려고 만든거긴 하지만 같이 공유하는 글이기 때문에 신경을 써야되는데 그러지 못했어요 앞으로는 더 좋은 글을 쓰도록 하겠습니다.

 

다음번에는 더 좋은 정보를 가지고 찾아오도록 하겠습니다(Jump Point Search를 들고올것같습니다)

아마... 점프포인트 서치에서는 좀 논의해봐야 할 부분이 많을 것 같습니다. 왜냐하면 에이스타의 구린부분을 어떻게 잡아낼 것이냐? 에 대한 얘기를 해봐야 하기 때문인데요... 점프포인트 서치의 경우에는 어떻게 해야지 좀 더 효율적이 될 수 있는가에 대한 큰 논의가 있어야 하기 때문에 다음글에서 다루도록 하겠습니다.

 

원래라면 길찾기를 한번에 소개하려고 했으나... 에이스타만해도 좀 내용이 길어졌기때문에 뇌용량 오버플로를 위해서라도 혹은 제 스스로 정리할 시간을 얻기 위해서라도 여기서 마무리 하는것이 좋을 것 같습니다 허허...

그러면 다음기회에 더 좋은 글로 찾아뵙도록 하겠습니다 그리고 밑에는 에이스타 알고리즘으로 길찾기 프로그램 만든것인데...

 

급하게 만드느라 더블버퍼링같은거 신경안쓰고 만들었습니다. 조금 눈아플수도 있지만 양해부탁드립니다.