[리뉴얼] 6- AI의 길찾기(A*)

 

개요

 

AI는 클라이언트가 아닌 Server에서 가지고 있는 지형 정보와 여러 Data(위치, 상태)등을 가지고 길 찾기를 실행한다.

 

A*

 

A*는 대표적인 길 찾기 알고리즘으로 1968년에 만들어진 알고리즘이다. A* 알고리즘은 아직 조사하지 않은 상태들(Open List)와 이미 조사한 상태들을 담은(Closed List)를 가지며 시작 지점으로부터 현재 상태에 이르는 가장 싼 비용 g(x)와 현재 상태로부터 가장 싼 비용 h(x) 이 둘을 더해서 가장 싼 추정 비용을 가지는 상태를 찾아서 이동하는 과정을 반복함으로 써 가장 싼 비용의 최종 경로를 찾는다.  또한 A*는 현명하게 사용하지 않으면 상당한 메모리와 상당히 많은(실시간 게임에서는 허용할 수 없을 정도의) CPU 시간을 잡아먹게 된다.

 

이러한 방법을 막기 위해 내가 생각하는 해결할 수 있는 방법은 다음과 같다.

1. A* 자체의 오버헤드는 막을 수 없기 때문에 A*를 실행할지 말지를 판단하게 한다.

2. 직선에 있는 목표에 대해서는 A*를 실행하지 않고 이동을 처리한다.

3. Navigation Mesh(맵 데이터)가 크면 많은 시간이 걸리기 때문에 탐색의 깊이를 조절한다.

 

 InPutComponent

 

Server에 존재하는 모든 Monster들은 InputComponent의 인스텐스를 가진다. 이 Component는 디자인 패턴 중에 하나이다.(아래 링크 첨부)

 

주요 변수와 함수들의 설명은 다음과 같다.

이름	설명
MonsterState	현재 Monster의 상태(FSM)를 가지는 Enum class형태의 변수이다.
CAstar*	길 찾기를 하는 AStar의 Handle 이다.
AtomicBool	길 찾기에서 발생하는 Data Race를 해결하기 위한 Flag 변수이다. 길찾기를 실행하고 있다면 다른 스레드가 들어가지 못하게 한다.( 이 변수는 바뀔 여지가 있다.)
StartPathFind()	현재 Monster의 상태에 따른 A*를 실행하는 함수이다.

 

* 여기에 있는 변수와 함수들은 계속 Update를 진행하기 때문에 추가 삭제가 있을 수 있다. 앞으로 설명할 코드들도 동일하다

 

 A*

 

A*를 직접 실행하는 Class의 변수와 함수들이다. 전체는 아니고 일부분 자른 모습이다. 

 

주요 변수와 함수들의 설명은 다음과 같다.

이름	설명
AStar::OpenList	AStar의 아직 탐색하지 않은 리스트들을 가지는 변수이다.
AStar::CloseList	AStar의 탐색을 진행한 리스트들을 가지는 변수이다.
GetHeuristice()	사전에 정의한 여러 휴리스틱 중에서 하나를 계산하고 그 값을 리턴해주는 함수이다. 여기서는 맨해튼 방식만 이용한다.

 

 

* 좀 더 자세한 설명은 예전에 진행했던 쥐의 치즈 찾기 프로젝트에 자세한 설명이 있다.(아래 링크 첨부)

 

 

 Navigation Data(지형 데이터)

 

지형 데이터를 가지는 Navigation 소스코드이다. 지형 데이터는 Cell 형식이며 각 Cell 마다 Type, Weight를 가진다.

 

지형 데이터는 이러한 형식으로 삽입을 하고 있는데 나중에 JSON으로 바꿀 예정이다.

 

 

 실행 화면

 

벽 장애물을 피해서 플레이어에게 다가가는 것을 확인할 수 있다.

 위 몬스터는 봤을 때 최단거리가 아닌 것처럼 보이지만 계산해보면 최단거리를 이동하는 것을 볼 수 있다. 하지만 몬스터가 마치 술 취해서 움직이는 듯한 움직임을 보여주기 때문에 보완이 필요해 보인다. 이러한 보완을 A*의 미시적 관점이라고 한다. 이 기법은 AI가 좀 더 자연스럽게 이동하도록 하는 기법이다.

 

다른 클라이언트에서 도 동일하게 A*를 실행하는 모습을 확인할 수 있다.

 

 

후기

 

A*를 Server에 돌려서 Monster의 이동을 확인해 보았다. AI는 내용이 길어질 거 같아서 두 개로 나눴다 하나는 현재 작성한 길 찾기 부분이고 다른 하나는 FSM 부분으로 나눠서 올릴 예정이다.

 

마지막에 몬스터 텍스쳐 방향이 조금 느리다는 버그 등 자잘한 버그들도 있고 아무래도 A*자체가 많은 자원을 소모하기 때문에 추후에 문제가 발생한다면 최적화를 진행할 예정이다. 각 구역마다 A*를 나눴기 때문에 큰 문제는 없을 거 같다.

 

 

A* 관련 및 디자인 패턴 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 알고리즘

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-PathFinding

[프로그래밍/디자인패턴] - [디자인패턴] 컴포넌트 패턴(Component Patterns)

 

리뉴얼 관련 글

--서버--

[portfolio] - [리뉴얼] 4- AcceptEx 및 이동 동기화

--클라이언트--

[portfolio] - [리뉴얼] 3- 공간 분할을 이용한 Sector Class

[portfolio] - [리뉴얼] 2- 경량 패턴을 이용한 World Class

[portfolio] - [리뉴얼] 1- 중재자 패턴을 이용한 Network Class

[portfolio] - [리뉴얼] 개요 및 목표(20.11.02 수정)

--리뉴얼 작업 전 포트폴리오

2019/12/16 - [portfolio] - DirectX & IOCP

 

 

* 리소스는 알피지 만들기 툴 리소스를 사용했으며 영리 목적으로 사용하지 않을 것입니다.