팩맨 유령들의 AI

루리웹에서 예전에 올렸던 이 링크되었길래 봤는데, 팩맨 유령들은 다 이름이 있고 제각기 다른 전략으로 움직인다는 내용이다. 마침 작년에 이걸 제대로 설명한 Retro Game Mechanics Explained의 영상을 본 적이 있었기에 그 내용을 소개하고자 한다. 제목에서의 AI는 게임 상에서 등장하는 적이나 NPC 등의 액션 알고리즘을 뜻하고 일반적인 인공지능과는 좀 괴리가 있을 수 있지만 보통 게임에서 이 프로그래밍된 행동 원리를 AI로 표현하기에 여기서도 AI라고 칭하기로.

결론부터 이야기하자면, 팩맨에서 유령들의 움직임은 (일부 예외를 제외하면) 결정론적이다. 즉 그들의 움직임에는 랜덤 요소가 없고, 각자의 개성과 경과 시간, 팩맨의 위치 등에 따라 무조건 어디로 움직일지가 결정된다. 위 영상에서 그 움직임의 조건이 구체적으로 낱낱이 파헤쳐진다.

유령의 행동은 위와 같은 네 종류의 패턴이 있다. 팩맨을 쫓아오는 추격(chase) 모드, 팩맨에게서 달아나는 해산(scatter) 모드, 팩맨이 아이템을 먹었을 때의 굼뜨는 공포(frightened) 모드, 그리고 그 팩맨에게 잡혔을 때의 포획(eaten) 모드. 이 네 모드 사이에서 다음과 같이 상태가 바뀌게 된다. 여기서 시계 그림은 상태의 변화 요인이 시간 경과인 경우.

대부분의 상태 변환은 게임을 플레이하다보면 자연스럽게 체득할 수 있는데, 잘 보면 추격 모드와 해산 모드 사이에 이 시간 경과에 따른 상태 변환이 있다는 것을 알 수 있다. 실은 유령들은 늘 팩맨을 쫓아오는 것은 아니고, 한 스테이지에 총 네 번 해산 모드로 변환된다. 구체적으로 각각의 모드의 인터벌이 어떻게 되는지는 다음과 같다. 예컨대 레벨 3의 경우 해산 7초, 추격 20초, 해산 7초, 추격 20초, 해산 5초, 추격 17분 13초 14, 해산 0초 01, 그리고 이후 계속 추격. 사실상 레벨 1만 4번의 해산 모드가 있고 그 이후로는 3번의 해산 모드가 주어지는 셈이다. 이 타이머는 레벨을 클리어하거나 팩맨이 죽으면 리셋된다.

참고로 빨강 유령 블링키의 경우, 팩맨이 먹어야할 도트 개수가 얼마 남지 않으면 해산 모드임에도 혼자 추격 모드를 지속한다. 이 때문에 팩맨을 계속 플레이하다보면 자꾸 빨강 유령이 집요하게 쫓아오는 느낌이 드는 것. 블링키가 계속 추격 모드를 유지시키는 남은 도트 개수의 역치는 다음과 같다.

그러면 구체적으로 유령들은 어떻게 움직이는가? 네 마리의 유령은 각자의 전략과 모드에 따라 리얼타임으로 목표 지점(target)이 주어진다. (후술하겠지만 이 목표 지점이 팩맨의 위치와 일치하지는 않다) 이 때 그들의 행동 강령은 다음과 같다.

1. 현재 향하고 있는 방향을 ‘앞’이라고 하면, 다음으로 움직일 방향은 ‘앞’, ‘왼쪽’, ‘오른쪽’ 셋 중에서 결정되며 ‘뒤’로 180도 이동하지는 않는다. (위 예시의 경우 빨간 색으로 칠해진 화살표 방향들) 단 모드 변환시에는 예외적으로 ‘뒤’로 방향 전환하기도 한다.
2. 벽으로 막히는 방향을 제외하고 남은 선택지들 중에서, 다음으로 움직였을 때의 위치가 목표 지점과의 거리(유클리드 거리)가 가장 가까운 방향을 택한다. (위 예시의 경우 →)
3. 만약 두 방향에 대해 그 거리가 일치한다면 ↑ ← ↓ → 순서로 우선하여 선택한다. (위 예시의 경우 ↑)

이 행동 원리를 통해서 유령들은 지속적으로 목표 지점을 향해 움직인다. 그러면 그 목표 지점이 어디로 정해지느냐가 문제인데, 먼저 비교적 설명이 간단한 해산 모드의 경우 네 유령의 목표 지점은 다음과 같이 설정된다.

그래서 만약 해산 모드가 계속 지속되면 네 유령은 아래와 같은 루프를 계속 돌게 된다. (물론 실제로는 앞서 본 바와 같이 7초 이내로 짧기 때문에 계속 돌고만 있지는 않다)

공포 모드의 경우 패닉 상태에 대한 비유인 듯이 딱히 목표 지점은 없고 분기가 나올 때마다 랜덤으로 선택한다. 그리고 포획 모드의 경우 아래 그림과 같은 위치로 목표 지점이 설정되어 고스트 룸으로 돌아가게 된다.

이제 가장 중요한 추격 모드. 여기에서 네 유령들의 서로 다른 전략에 따라 목표 지점이 달라지고, 각 유령의 개성이 나타나게 된다.

빨강 유령 블링키(Blinky)는 가장 단순한 AI로, 그냥 팩맨의 위치가 곧 목표 지점이다.
분홍 유령 핑키(Pinky)는 팩맨의 네 칸 앞이 목표 지점이다.
청록 유령 잉키(Inky)는 팩맨의 두 칸 앞을 중심으로 블링키의 위치를 대칭시킨 곳이 목표 지점이다. 위 그림의 경우 두 칸 앞이 아니라 약간 왼쪽으로 치우쳐진 곳이 대칭 중심으로 표시되어 있는데, 이에 대해서는 후술.
클라이드(Clyde)는 팩맨과 8칸 이상 떨어져 있으면 블링키처럼 팩맨의 위치가 목표 지점이지만
거리가 8칸 이하로 좁혀지면 해산 모드가 된다. 이름도 셋과 좀 다르고 멀리서 다가오려고 하지만 막상 가까워지면 도망가고 2차 창작 욕구 불러일으키는 캐릭터

그래서 블링키는 일반적으로 팩맨을 뒤쫓는다. 핑키의 경우 목표 지점과 팩맨 사이에 벽이 있다든지 하면 위협이 되지는 않지만, 팩맨의 앞에서 마주치는 경우가 나타날 수 있다.

잉키의 경우 블링키의 위치에 따라 이상한 곳에서 놀고 있는 경우도 많지만, 아래 그림처럼 블링키와 협공하게 되는 경우도 나타날 수 있다.

참고로, 아래 그림에서 표시된 위치에서는 유령이 중간에 방향을 바꾸는 것이 불가능하게 추가적으로 설정되어 있다. 즉 유령이 저 구역에 들어서면 위로 방향을 전환하는 것이 불가능하므로, 팩맨이 아래 그림과 같은 위치에 있으면 유령에게 장시간 잡히지 않을 가능성이 높다.

실제로 이 위치에서 위를 향하고 있으면 핑키, 잉키, 클라이드는 거의 대부분의 경우 계속 루프를 돌게 되고 블링키도 루프를 도는 경우가 절반은 되기 때문에 어느 정도 안전을 보장받을 확률이 높다고.

이렇게 각 유령들의 행선지가 결정되기 때문에 (공포 모드일 때는 랜덤 요소가 있지만 위협이 되지 않으므로 제외) 이를 이용하면 순간적으로 방향 설정을 통해 유령들의 진행 방향을 어긋나게 해 위기 상황을 벗어나는 플레이도 가능하다.

사족으로, 핑키는 원래 팩맨의 네 칸 앞을 목표 지점으로 삼아야 해서 팩맨이 왼쪽을 향하고 있으면 왼쪽으로 네 칸 나아간 지점, 오른쪽을 향하고 있으면 오른쪽으로 네 칸 나아간 지점 등이 되어야 한다. 그런데 예외적으로, 팩맨이 위쪽을 향하고 있으면 팩맨에게서 위쪽으로 네 칸 나아간 후 왼쪽으로 다시 세 칸 나아간 지점이 목표 지점으로 설정된다.

사실 이것은 일종의 버그이다. 다만 게임 플레이에 큰 영향을 끼치지는 않기 때문에 그리 크리티컬하지는 않을 뿐. 이번에도 팩맨 킬스크린처럼 어셈블리어에서 그 버그가 어떻게 나타나는지 설명할 수 있다.

배경 지식으로, 각 캐릭터들의 위치는 x 좌표와 y 좌표로 나타낼 수 있고, 그 좌표는 위 그림과 같이 주어져 있다. 여기서 캐릭터가 움직이는 것은 상하좌우 방향으로 1만큼 움직이는 벡터를 더하는 것과 같다.

여기서 각각의 좌표는 8비트 unsigned int로 00(=0)에서 FF(=255)까지의 16진수로 표현되며, 1을 빼는 것은 그 보수인 FF를 더하는 것으로 생각한다. (이는 가장 큰 자리에서의 받아올림을 무시하기 때문에 가능하다.) 더 나아가서, 4칸만큼 움직인 곳의 좌표를 구하기 위해서 이 방향벡터들에 4를 곱하여 변위 벡터를 구한 후 이걸 위치 벡터에 더한다. 예컨대 주어진 위치에서 오른쪽으로 네 칸 나아간 곳을 나타내기 위해서는 오른쪽을 표현하는 벡터 FF 00에 4를 곱한 3FC 00을 더해야 한다. 여기서 가장 큰 자리에서의 받아올림에 해당하는 3은 무시되어 FC 00을 더하는 것이 되며 이는 제대로 작동한다.

그런데 위로 4칸 움직일 때의 변위 벡터를 구할 때, 00 FF에서 4를 곱하는 과정에서 03 FC처럼 받아올림 3이 버려지지 않고 x 좌표에 영향을 주게 되어버린 것. 앞서 잉키의 목표 지점을 설명할 때 팩맨의 두 칸 앞을 표시해야 하는데 왼쪽으로 치우쳐져 있던 경우도 이와 같은 이유로 나타난 버그이다.

트윗 타래를 정리. (2019/07/14)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중