[DT광장] 게임 속 수학 'A* 알고리즘' 아시나요

백진언 국가수리과학연구소 연구원

백진언 국가수리과학연구소 연구원

오늘날 게임은 단순 오락을 넘어, 몰입감 높은 스토리와 화려한 그래픽, 고도화된 기술력을 바탕으로 대표 문화 콘텐츠로 자리 잡고 있다. 놀라운 것은, 이렇게 다양한 콘텐츠들을 보여주는 게임이 사칙연산과 몇 가지 명령어로만 이뤄진 컴퓨터 위에서 돌아간다는 것이다. 이렇게 다양한 콘텐츠를 제한된 계산으로 구현하기 위해 게임에서는 기초 학문의 다양한 지식을 쓰는데 특히 숫자를 직접적으로 다루는 '수학'에 많이 의존한다.

게임의 수학적 요소를 좀 더 자세히 들여다보면, 사칙연산, 방정식, 함수, 확률, 통계, 기하학 등 다양한 알고리즘이 적용됨을 확인할 수 있다. 알고리즘이란 일반적으로 주어진 문제를 해결하기 위해 사용하는 절차, 방법, 명령어를 의미한다. 즉, 컴퓨터가 시키는 대로 일을 하는 일꾼이라면, 알고리즘은 그 일꾼이 해야 할 일이 적힌 설명서인 것이다. 우리가 어떤 프로그램을 실행할 때 컴퓨터가 실행하는 것은 그 프로그램에 적힌 알고리즘이다. 예를 들면 리니지 클라이언트를 더블 클릭할 때, 컴퓨터는 어떻게 리니지 게임에 접속할 수 있는지에 대한 알고리즘을 실행한다.

현재 우리가 접할 수 있는 게임에는 컴퓨터 그래픽스에 쓰이는 기하학 알고리즘, 퍼즐에 쓰이는 이산수학 알고리즘, 물체의 움직임을 계산할 때 쓰이는 방정식의 해를 계산하는 알고리즘 등 다양한 알고리즘들이 쓰인다. 그 중에서도 'A*(에이스타) 알고리즘'은 캐릭터의 최단 이동 거리를 찾을 수 있도록 돕는 기초적인 알고리즘으로, 이용자가 몬스터, 장애물을 거쳐 보다 신속하고 효율적인 방법으로 출발 지점에서 목표 지점까지 도달할 수 있도록 설계한다.

에이스타 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라팰이 처음 기술한 알고리즘으로 출발 꼭지점으로부터 목표 꼭지점까지의 최적 경로 탐색을 목표로 한다. 그 당시 인공지능(AI) 로봇 개발을 위해 만들었다.

'스타크래프트'를 적용 예로 들면, 스타크래프트와 같이 이용자가 영웅을 조정할 수 있는 게임인 경우 그 영웅을 어떻게 하면 가장 빠르게 움직일 수 있을지 계산해야 한다. 이용자가 유닛(개체)의 출발 지점과 도착 지점을 지정하면 유닛은 가장 신속한 방법으로 도착 지점까지 도착해야 하는 것이다. 이때 유닛이 어떤 경로를 거칠 지 이용자가 일일이 지정해줄 수 없다. 대신 컴퓨터는 개발자가 설계해 놓은 에이스타 알고리즘 명령을 내려 유닛의 경로를 미리 계산하고, 이용자 대신 유닛을 최단 경로로 이동시킬 수 있다. 이를 통해 이용자의 효율적 게임 플레이가 가능해진다.

에이스타 알고리즘이 게임뿐만 아니라 로봇 청소기 등 로봇을 만드는 데에도, 차 내비게이션이 최단 경로를 찾고자 할 때도 적용 가능하다. 다만, 범용적으로 적용할 수 있는 알고리즘을 우리 눈으로 직접 확인할 수 있는 예시가 바로 게임인 것이다.

이처럼 게임은 수학과 긴밀한 연결고리를 갖는다. 게임 기획, 개발, 서비스 전 단계에 이르기까지 표면적으로 드러나지 않으나 수학적 계산과 논리가 곳곳에 담겨 있기 때문이다. 게임이 지닌 재미 요소와 차별화된 콘텐츠 뿐만 아니라, 게임에 숨겨진 수학적 특성들을 하나씩 알아갈 때 우리는 게임에 대한 흥미와 이해도를 더욱 높일 수 있을 것이다.