▲ 이재환 교수

[인벤게임컨퍼런스(IGC) 발표자 소개]이재환 교수는 시작하세요! Cocos2d-x 3.0 프로그래밍 및 핵심강좌! 유니티5의 저자로 현재 경일직업능력개발원에서 후학 양성에 힘쓰고 있다.


보통 알고리즘이라고 하면 우리는 복잡하고 어렵다는 생각을 먼저 하게 되며, 실제로도 그렇다. 개념 설명부터 이런저런 전문 용어가 튀어나오고, 깊이 들어가면 더 복잡한 수식과 코드가 날뛴다.

IGC 강연에서 알고리즘을 주제로 삼은 이재환 교수는 시작에 앞서 일반인들도 쉽게 이해할 수 있는 강연을 진행하겠다고 전했다. 그런 이유로 세부 주제로 다양한 알고리즘 중 가장 기초가 되는 A*(AStar) 알고리즘을 선택했다고. 알고리즘이란 대체 무엇이고, A* 알고리즘은 어떤 과정으로 진행되는지, 이재환 교수의 설명을 들어보자.


※ 내용 전달 및 편집의 용이성을 위해 이재환 교수의 시점에서 서술합니다.


■ 강연주제 : 시작하는 게임 프로그래머를 위한 알고리즘, 그리고 첫걸음 AStar

⊙ 알고리즘이란?


알고리즘의 정의를 찾아보면 복잡하고 어렵다. 하지만, 오늘 강연에서는 알고리즘이 그다지 어렵지 않다는 것을 이야기하고 싶다. 알고리즘을 쉽게 이야기하면, 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이다. 정답이 있는 알고리즘이 있고 정답이 없는 알고리즘이 있는데, 정답이 없는 알고리즘은 어떤 가치를 우선시하는가가 중요해진다. 병법과 바둑의 정석도 알고리즘의 한 예다.

기초 알고리즘에는 크게 정렬 알고리즘과 길찾기 알고리즘이 있다. 오늘 강연에서는 길찾기 알고리즘, 그중에서도 A*(AStar)에 대해 이야기하겠다. 왜 A* 알고리즘이냐. 일단, 가장 쉽다. 그리고 만능 양념장 같은 느낌이어서 A* 알고리즘 하나만 알고 있어도 프로그램을 짜는 데 엄청나게 큰 도움이 된다.

⊙ A* 알고리즘


사전이나 책에서 설명하는 A* 알고리즘의 정의 역시 어렵다. 때문에 오늘은 A* 알고리즘에 쉽게 접근하기 위해 실용적인 방법에 초점을 맞춰 설명하도록 하겠다. A* 알고리즘은 출발 지점에서 목표 지점까지 가장 비용이 낮은 경로를 찾고, f = g + h라는 계산값을 사용해 다음으로 이동할 경로를 결정한다. 각각 goal(목표), heuristic(휴리스틱), fitness(적합도)다.


목표는 시작 노드부터 이 노드까지 오는데 드는 누적비용이다. 어렸을 때 배운 피타고라스의 정리를 인용해 각 비용의 값을 정할 수 있다. 휴리스틱은 경험에 기초한 추측을 뜻한다. 그러므로 이 비용은 노드에서 목표까지 가는데 드는 '추정된' 비용이다. 여러 방법이 있는데, 오늘은 맨하탄 방식을 사용한다. 맨하탄 방식에서는 중간에 장애물이 없고 직선으로만 간다고 가정한다.

피트니스는 g와 h의 합이기 때문에 결국 추정치다. g와 h 두 개를 더한 f 값이 낮을수록 가장 빠른 경로일 가능성이 크다. 즉, 피트니스는 현재 위치에서 다음의 어떤 노드로 이동할 것인가를 결정하는 방법이다. 현재 위치에 연결된 다음 노드가 여러 개일 경우, 연결된 모든 노드의 f 값을 계산하여 가장 작은 노드를 선택해 탐색을 수행하고, 목표 노드에 도착하면 탐색을 종료한다.


A* 알고리즘에 대한 공부를 시작할 때 가장 흔히 나오는 구조다. 시작지점에서 출발해 장애물에 닿지 않고 목표지점까지 가야 한다. A*에서는 오픈과 클로즈로 좌표의 목록을 나누는데, 이미 한 번 다녀와 더 이상 갈 필요가 없는 곳은 클로즈, 앞으로 확인해야 할 것들은 오픈 목록에 넣어준다.


타일을 보면 우측 상단에 이름을 적었다. 시작지점 A(1, 3)로부터 드는 비용은 좌측 하단에 적고, 맨하탄 방식으로 추정된 휴리스틱 값을 우측 하단에 표시한다. 두 개를 더한 피트니스 값은 좌측 상단에 있다. 그리고 이 수치들이 어디서 출발한 값인지를 확인하기 위해 그 시작점을 가운데에 적는다.

이 상태에서 가장 작은 값인 (2, 3)을 먼저 움직인다. 이때, (2, 3)은 오픈에서 지워지고, 클로즈로 넘어가며 B라는 이름을 갖게 된다. 이 과정을 반복해 목표지점(5, 3)까지 도달하게 되는데, 그렇게 되면 목표지점에서부터의 클로즈 리스트를 거꾸로 되짚어 시작지점으로 향하는 길을 만든다. 이 결과를 뒤집으면 찾고자 했던 결과가 나오는 것이다.


위의 과정을 이해했으면 이와 같은 슈도코드(pseudocode)를 만들 수 있다. 일단, 반복(loop)을 한다는 전제하에서 오픈 리스트에서 제일 싼 값을 current에 넣어준다. 그 다음 오픈 리스트에서 그 값을 지우고, current를 클로즈 리스트에 추가한다. 그리고 current가 목표지점이면 결과를 찾은 거고, 목표지점이 아니면 다시 돌아간다. 이후 내 주변을 탐색해 가지 못하면 건너뛰고(skip), 갈 수 있다면 그 가격을 구한다. 이를 반복하게 되면 코드가 나온다.

슈도코드를 보여드린 이유는 여러분 각자가 사용하는 언어가 다 다를 것이기 때문이다. 이 슈도코드를 보고 자기의 언어에 맞춰 직접 코드를 만들 수 있어야 한다. 알고리즘은 이미 슈도코드에 들어 있기에, 표현 능력만 갖추고 있으면 된다.

여기까지 보면 A*라는 게 그렇게 어려운 알고리즘은 아니라는 것을 알 수 있다. 지금까지 설명한 것은 최단 거리를 찾는 로직이었는데, 더 나아가 미로 찾기나 AI의 움직임 설정 등에도 A*를 적용할 수 있다.