로그라이크 게임 구현 - Context based steering algorithm을 활용한 움직임 구현

https://kidscancode.org/godot_recipes/ai/context_map/

이번 알고리즘을 구현하는데 40시간 이상은 걸린거같다.

Context based steering algorithm은 장애물을 피하게끔 이동하는 탐색 기법이다.

위 알고리즘을 한국어로 번역하면 "배열에 기반한 움직임 알고리즘"이다.

알고리즘의 이름처럼 움직임을 배열로 선언하고, 장애물을 피하게끔 코드를 짜면 된다.

그러나 해당 알고리즘은 전문적인 게임 툴을 사용하고 있다는 전제 하에 작성된 알고리즘이였다.

때문에 이를 게임 개발 툴이 아닌 WinAPI에 적용 시키는 것은 꽤 힘들었다.

 

 

 

context-based steering algorithm을 활용한 몬스터 움직임

먼저 위 알고리즘에 대해 설명하겠다.

가장 먼저 작성해야할 코드는 움직임을 만드는 것이다.

몬스터의 프레임당 이동하는 좌표의 양을 3으로 잡고 몬스터의 움직임을 8방향으로 나누었다.

 

움직임을 나눈 모습

 

 상 하 좌 우 움직임은 좌표를 방향에 맞게끔 3만큼 이동시켰고,

대각선 움직임은 방향에 맞게끔 좌표를 (2,2)만큼 이동시켰다.

아래의 코드를 보면 이해하기 쉽다.

POINT monsterMovePos[8] = { { 0,-3 }, { 2,-2 }, { 3,0 }, { 2,2 }, { 0,3 } , {-2,2} , {-3,0} , {-2,-2} };

 

움직임을 설정한 이유는 움직임을 벡터처럼 활용하기 위해서이다.

8가지 방향의 벡터를 설정했다면, 이제 이 벡터들의 우선순위를 정해야한다.

우선순위는 목적지로 가장 빠르게 이동하는 벡터가 1순위이다.

그 다음 순위는 목적지를 향해 그나마 빠르게 가는 벡터를 선택한다.

마지막으로 목적지와 정 반대의 방향으로 이동하는 벡터가 8순위 즉 마지막 순위이다.

나는 이 우선순위를 몬스터의 좌표와 목적지의 좌표 (캐릭터의 좌표이다.)의 Cos값을 구하여 설정했다.

 

몬스터의 벡터의 Cos값

 

몬스터의 좌표를 영점으로 잡고, 캐릭터의 좌표의 Cos값을 구한다

그리고 구한 Cos값과 가장 가까운 몬스터의 벡터가 1순위가 된다.

 

M = 몬스터 P = 캐릭터 (목적지). 목적지를 향해 가장 빨리 가는 벡터가 1순위가 된다.

이런식으로 우선순위를 설정하면, 몬스터는 매 프레임마다 가장 빠른 벡터로 이동하여,

목적지로 향하는 최적의 루트를 따라간다.

그러나 이 알고리즘은 목적지를 향해 빠르게 가기 위해 존재하는 것이 아니다.

이 알고리즘은 장애물을 회피 할 수 있게 만든다.

 

만약 1순위의 벡터로 가는데 그 앞에 장애물이 있어 가지 못한다면, 그 벡터는 차단된다. (그 벡터로는 절대 이동하지 않는다.) 

이후 그 다음으로 높은 순위의 벡터로 이동한다.

만약 장애물에 둘러싸여 모든 벡터가 차단되었다면, 가장 후순위의 벡터로 이동한다.

위 케이스에서 몬스터는 1순위의 벡터로 이동하지 않고 2순위의 벡터로 이동한다.

 

 Vampire Survivors 게임에선 몬스터들이 서로 겹치지 않는다.

즉 몬스터들이 서로 거리를 띄우게 코드를 작성하면 된다.

위 알고리즘에서 몬스터들을 장애물로 설정하면, 몬스터들은 절대 겹치지 않게된다. 

 

위 내용에 근거하여 내가 작성해야할 코드는 네가지이다.

1. 몬스터 기준 플레이어와의 Cos값을 구하는 함수

2. 구한 Cos값을 바탕으로 벡터의 우선순위를 설정하는 함수

3. 우선순위가 높은 벡터로 이동하게 하는 함수

4. 장애물을 정의하고, 벡터의 방향에 장애물이 있다면 해당 벡터를 차단하게 하는 함수

 

아래는 구현한 함수이다.

 

1. 수정된 MonsterMoveFun

2. Cos 값을 바탕으로 1순위의 벡터를 설정하는 함수

3. 1순위의 벡터를 바탕으로 8순위까지의 벡터를 설정하는 함수

4. 몬스터끼리의 충돌을  감지하는 함수

위 코드를 보면 자료구조 큐를 사용한 흔적이 눈에 띌 것이다.

몬스터 구조체에 큐를 선언했다.

큐를 선언한 이유는 벡터의 우선순위를 큐에 넣고, 차단된 벡터가 있으면 그 벡터를 큐에서 POP하기 위해서이다.

 

몬스터와의 충돌을 감지하는 함수에서는 Contetxt based steering algorithm을 내가 변형시켰다.

위 알고리즘은 앞서 말했듯이 장애물이 있다면 그 벡터로 절대 이동하지 않는다.

4번 코드에서 나는 이동하기 전 몬스터와의 거리 (distance)와 이동한 후 몬스터와의 거리 (afterdistance)를 구했다.

몬스터들끼리 충돌했을 때 서로가 똑같은 방향을 향하고 있다면 벡터를 차단하지 않게 코드를 짰다.

위와 같이 코드를 짜니 몬스터들이 군중을 이루며 쫓아오게 됐다.