**
육각형 타일에서 Astar 알고리즘으로 길찾기!( PathFinding with A* in HexTile !)
서론
안녕하세요. 인디 게임을 개발하는 심리학도 라메드 입니다. 간만에 인사드립니다.
어쩌다보니 이번에는 SRPG에 TowerDefence가 결합된 형태의 게임을 혼자 만들어보려고 합니다. 물론 아트도 걱정이 되지만, 가장 걱정이되는 것은 SRPG에서 사용하는 다양한 알고리즘을 공부하는 일입니다. 그래서 일기를 쓰듯이, 또 스티미언 여러분들과 정보를 공유하는 차원에서, 배우고 구현에 성공한 알고리즘과 개념들을 나누고자 합니다.
알고리즘이 뭐야?
알고리즘(algorithm)은 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것입니다. 넓게는 사람 손으로 해결하는 것, 컴퓨터로 해결하는 것, 수학적인 것, 비수학적인 것을 모두 포함한답니다.
(출처 : 알고리즘 )
금방 이해가 안되실 수도 있어요!
사실 저도 문과출신으로 좀 낯선 개념이었습니다. 알고리즘이라고는 수능에서 본 이상한 도식들 밖에 구경하지 못했으니까요.
위의 정의를 자세히 봅시다.
" 주어진 문제를 해결하기 위해서 "
저의 경우에, A* 알고리즘이 필요한 문제 상황은 다음과 같습니다.
적 몬스터의 AI의 경우, 플레이어를 쫓거나 피하거나 움직여야 하는데, 이 때 매번 다른 장애물과 플레이어를 피해서 자동으로 최적의 길을 찾아야 합니다.
기존의 제가 알고 있던 것들로는 해결할 수 없는 문제에 가까웠습니다.
A* 알고리즘은 이러한 상황에 대해서 해결책을 제시하는데 , 저는 이 친구 덕에 몬스터를 구현할 수 있게 되었습니다. (아직은 안했지만요 .. )
그래서 A* 알고리즘이 뭔데?
A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 알고리즘 중 하나이다.
(출처 : A*알고리즘 )
한마디로, 최단 경로를 찾아주는 알고리즘입니다.
알고리즘은 문제 해결의 방법이지 어떠한 프로그래밍 언어나 개발에 국한된 것은 아니기에, 프로그래밍을 모르셔도 곰곰히 아래 내용을 살펴보시면 이해하실 수 있으실 겁니다!
A* 알고리즘의 순서입니다.
- 시작 지점을 "열린" 목록에 넣는다.
( 이 알고리즘에서는 열린 목록과 닫힌 목록이 존재합니다. (단순히 지점들을 묶어서 저장하는 것입니다. ) - 열린 목록에 있는 지점을 하나 빼서 , 여덟 방향 주변 지점을 탐색합니다.
( 이때, 평가를 하는 기준이 되는 함수는 F = G + H 인데, G는 시작 지점에서 현재 지점까지의 최단 경로의 값이고, H는 현재 지점에서 목표 지점 까지의 최단 경로의 값 입니다. 합하면 총 최단경로의 값이 되겠죠? ) - 2단계에서 제외한 지점은 닫힌 목록에 넣는다.
- 2단계에서 탐색한 지점을 열린 목록에 넣는다.
- 열린 목록 중 가장 앞의 지점 ( 가장 작은 값이 앞에 오도록 미리 정렬합니다. ) 을 빼서, 닫힌 목록에 넣는다.
- 5단계에서 뺀 지점의 여덟방향의 주요 지점을 탐색한다.
( 장애물과 닫힌 목록을 제외하고 ,목표 지점이 있는지 조사합니다. )
( 열린 목록이 비어있다면 , 길이 없는 것입니다. )
( 목표 지점이 있다면 , 경로를 찾은 것입니다. ) - 열린 목록에 존재하지 않는 지점은 열린 목록에 추가하고 , 중복 되는 지점은 G값을 비교하여 더 작은 열린 목록으로 교체한다.
- 5번 부터 반복한다.
(참고 출처 : https://blog.naver.com/dowaari/58709472 )
음....
여기까지 읽고 이해가 안되신다면, 무척 정상이십니다.
왜냐면 저도 그랬거든요..
하지만 코드를 읽다보면 이해되게 됩니다!
다음시간에는 코드를 들고 찾아오겠습니다. 감사합니다.
( 성공한 모습 )