꿈돌이의 컴공수련: 고교 수학 수준 컴퓨터 게임 인공 지능 길 찾기

인공 지능 하면 인공신경망(대규모 회귀분석), 퍼지논리(애매모호 논리), 유전 알고리즘(진화론 = 시행착오) 등 나올 것 같지만 컴퓨터 게임에선 이런 것 사용하지 않는다. 너무 느리고 어떻게 그렇게 되었는지 파악하기 힘들다. 컴퓨터 게임에서 볼 수 있는 지능은 그냥 따라 하면 되는 알고리즘이다. 간단하게 조건 반응이지.

상대 인식(거리 측정)
조건에 따른 반응(튜링머신 = 컴퓨터 = 상태변화도/표)
길 찾기(path finding) 등

이런 건 반응이 빠르고 왜 그렇게 행동했는지 명확하게 이해할 수 있다.

블로그 날리니 기억이 가물가물하다. 씨발. 참고 했던 글의 링크가 끊어졌다.

그래서 위키 백과 글을 링크해 두는데 이걸 읽고 이해할 정도면 머리 좋은 거다. ㅋㅋㅋ

컴퓨터는 1/30초 또는 1/60초(순간/찰나) 동안 다음과 같은 동작을 반복한다.

사용자 명령 (키보드, 마우스) 입력
물리, 지능 시뮬레이션
화면 그리기 (배경, 애니메이션)

인공 지능 시뮬레이션은 다음과 같은 순서이다. 지능 시뮬레이션은 물리 시뮬레이션이나 그림 그리기처럼 단순 반복 작업이 아니기 때문에 단계를 나누어 여러 사이클에 걸쳐 계산할 수도 있다. 즉 한 사이클에는 한 단계의 작업만 하는 것이다.

감지 : 주로 거리 계산
판단 : 상태 변화 검색, 길 찾기 알고리즘 실행(소모 시간이 가변적)
행동 : 간단

물리 시뮬레이션은 그림 그리기보다 더 짧은 빈도로 계산할 수도 있다. 단순 반복 계산이기 때문에 소모 시간이 동일하다. 물리 시뮬레이션이 끝나면 위치 변화가 나타나고 화면에 표시를 해야 한다.

힘 변화 → 가속도 변화
가속도 변화 → 속도 변화
속도 변화 → 위치 변화
위치 변화 → 충돌 확인
충돌 계산 → 속도 변화

A. 거리 측정

상대가 근처에 왔는지 확인해야 하겠지? 여러 게임을 보면 정지한 유닛은 거리 계산을 하지 않는다. 스타크래프트 같은 경우를 보면 그렇다. 움직이는 놈이 항상 주변 유닛과의 거리 계산을 한다. 문제는 100개의 유닛이 있을 때 모든 유닛의 거리를 계산하려면 100*100/2 + 100/2 = 5050번의 계산을 해야 하는 것이다. 이 문제 피하기 위해서 지도를 격자로 나누어 거리 계산이 필요한 유닛 주변 3*3 격자 속의 유닛과 거리만 계산한다. 지도를 영역으로 나눠서 같은 영역에 속하는 것들만 거리 계산을 한다는 것이다.

총 계산 양 = N*N/2 + N/2 = (N + 1)*N/2

근처에 있는 것을 대충 선택하여 거리 측정을 하고 그 중에서 너무 근접한 것에 대해서 충돌 검사를 하는 것이다. 거리 계산은 피타고라스 정리를 사용한다. 옛날 게임 중엔 단순히 정사각형 안에 들어오면 같은 거리로 취급한 것도 있다. 블리자드에서 만든 워크래프트 같은 것이 그렇다. 대각선 방향을 따지지 않는 것은 도시에서 거리 계산과 비슷하다. 도로를 따라 이동해야 하니 동서남북으로만 이동한다.

B. 조건 반응

상태변화도/표란 어떤 상태에서 외부 조건이 뭔가 더해져서 다음 상태로 변하는 것을 도표로 나타낸 것을 말한다. 상태변화도는 마치 지도를 그린 것과 같다. 예를 들어 지금 A교차로에 있는데 왔던 길을 제외하고 새로운 길이 3개 있어 교차로 B, C, D로 간다고 하면, 외부 조건(주사위 던지기나 신호등)에 따라 각 교차로로 이동하는 식이다. 수식으로 나타내면 다음과 같다.

다음 상태 = 대응함수/검색표(현재 상태, 외부 조건 A, B, C...)

이 때 다음 상태로 바뀌면서 거기에 따라 뭔가 행동을 하는 것이다. 예를 들면 다음과 같은 식으로 만들 수 있다.

if 현재 상태 = 정지 and 외부 조건 = 적 출현 then 다음 상태 = 적에게 이동
if 현재 상태 = 이동 and 외부 조건 = 적 접촉 then 다음 상태 = 적을 공격
if 현재 상태 = 공격 and 외부 조건 = 적 사망 then 다음 상태 = 정지
기타 기존 상태 유지

그냥 행동 규칙을 나열한 것과 같다. 조건문으로 못 만드는 것은 없다. 이 중에서 가장 구현이 어려운 행동이 이동이다. 길을 찾아야 하기 때문이다. 공격은 대충 뭔가 쏘거나 때리는 시늉만 하면 된다. 외부 환경 인식과 길을 찾는 것이 더 어렵다.

주변의 아군과 적의 비율을 보고 자신이 포위 된 상태인지 판단할 수도 있다. 주변의 적의 수를 비교해야 한다. 장애물을 피해 목표까지 가는 길을 찾는 것은 더 지능적이고 많은 시간이 소모 된다. 분신술을 써서 미리 모든 길을 다녀 봐야 한다.

미사일 요격 게임을 만들 때는 수학이 필요할 것이다. 미사일의 궤적을 예측하여 미리 쏘아야 하기 때문이다. 수학으로 해결 되는 문제는 수학으로 해결하는 것이 깔끔하다.

C. 길 찾기(A* path finding)

A*, A star 알고리즘 간단하게 소개한다. 나도 누군가 알려 줘서 알았다. 유튜브 동영상을 보면 여러 알고리즘이 있다는 걸 알 거다. 여러 갈래 길이 있을 때 어디로 갈 것인지 선택할 때 이 방법을 사용한다. 갈 길을 선택하는 알고리즘과 갈 수 있는 길을 찾는 건 다르다. 갈 수 있는 길이 몇 개 있는지, 여기로 도착하는 길이 몇 개 있는지 확인하는 것이 탐색이고, 그 길 중에서 어떤 길을 먼저 검토할지 결정하는 것이 선택이다.

게임에선 지도를 바둑판처럼 격자로 나누거나 6각형 형태로 나눈다. 이런 것을 타일 맵이라고 한다. 워크래프트가 이 바둑판 스타일이다. 입체감을 주려고 45도 회전한 것도 사용한다. 에이지 오브 엠파이어가 이 스타일이다. 마름모 형태로 된 격자는 레드 얼럿, 스타크래프트 스타일이다. 6각형 형태는 턴 방식 게임인 삼국지, 문명에서 볼 수 있다.

바둑판 형태로 나눈 경우는 한 격자에서 8방향의 길이 있다. 6각형 형태로 나누면 한 방에서 6방향의 길이 있다. 각 방의 좌표를 결정하는 방법은 위의 그림과 같다. 바둑판 형태가 아니면 홀수와 짝수에 따라 엇갈리게 된다. 상세 계산법은 알아서 구할 것. 만약 길 표시가 있는 지도라면 탐색 문제는 더 쉬울 것이다. 길만 따라 가면 되고 교차로에서 길 선택 문제만 있으니까. 자동차 네비게이터가 그러하다. 각 교차로는 연결된 다른 교차로 정보를 가지고 있어야 한다.

마이크로 마우스(로봇)가 미로를 통과하는 경기가 있다. 무조건 빨리 도달하는 게 목표인 게임이다. 여러 차례 도전하기 때문에 길을 암기 할 수도 있고, 카메라를 이용해서 벽 넘어 길을 볼 수도 있다. 날아 가거나 벽을 타 넘지만 않으면 된다. 거기 알고리즘도 매우 비슷하다. 거기서 사용하는 알고리즘은 이렇다.

좌수법/우수법(벽타기) : 벽에 손을 접촉하고 따라가면 미로를 탈출한다. (최초 우승)
깊이 우선 탐색 : 분기점에서 아무 길이나 정하면 무조건 깊게 들어가는 방법
넓이 우선 탐색 : 출발점에 가까운 곳부터 넓게 탐색하는 방법 (그러다 목표에 도달)
전체 지도 탐색 : 모든 길을 다 돌아 다니기 때문에 최적 길을 찾기는 하지만 꼴찌다.
물 채우기 : 분기점에서 목표에 가장 가까운 방향의 길을 선택하는 깊이 우선 탐색.
직진 우선 탐색 : 지도를 알고 있을 때 방향 바꾸는 회수가 가장 적은 길을 선택한다.

여기서 A*는 깊이 우선과 넓이 우선을 조합한 방법이고 물 채우기와 매우 비슷하다. 겉으로 보면 먼저 깊이 우선 탐색을 하다가, 장애물에 막히면 그 때 넓이 우선 탐색을 하는 것처럼 보인다. 가야 할 길을 선택할 때는 물 채우기(glood fill)와 비슷하게 평가 점수가 가장 낮은 쪽 길(목표까지 직선 거리가 가까우며, 출발점에서 거리가 가장 짧은 길)을 선택한다. 마치 물이 중력에 의해 낮은 곳으로 흘러 가는 것처럼. 차이가 있다면 마이크로 마우스는 몸이 있기 때문에 한 번 길을 정하여 갔다가 막히면 다시 원래 분기점으로 돌아 와야 한다. 소프트웨어 길 찾기는 분신술을 써서 동시에 여러 지점에서 탐색한다는 것이다. 순간 점프가 가능하기 때문이다.

여기서 최적의 길은 지도 전체를 탐색했을 때만 얻을 수 있다. 나머지 방법은 최적의 길이 아니다. 지도의 정보가 부족한 상태에서 가장 빨리 도달하는 방법들이다. 만약 벽을 따라 돌았을 때 최적이라 하더라도 전체 지도를 모르면 이를 알 수 없다. 그런 경우 눈에 보이는 정보만 가지고 지도를 대각으로 가로지르면서 복잡하게 이러 저리 돌아서 오히려 시간이 더 소모 될 수도 있다. 컴퓨터 게임에선 시간이 부족하기 때문에 전체 지도 탐색은 할 수 없다. 마이크로 마우스와 비슷한 상황인 것이다. 단지 분신술을 쓰기 때문에 좀 더 최적의 길을 선택한다는 것이다.

마이크로 마우스는 지금 지점에서 다른 지점으로 점프할 수 없다. 그러나 소프트웨어로는 A, B, C 3개 지점에서 동시 탐색이 가능하다. 그래서 여러 갈래의 길을 동시 탐색하다가 가장 먼저 목표 지점에 도달한 길을 선택하는 것이라서, 마이크로 마우스보다는 좀 더 최적의 길을 선택하게 된다. 마이크로 마우스는 물이 흘러 들어갈 거 같은 곳으로 이동하지만, 길 찾기 알고리즘은 진짜 물이 흘러 들어가는 여러 길을 동시에 찾는다. 이 분신술을 멀티태스킹이라고 부른다. A 지점에서 조금 탐색, B 지점에서 조금 탐색, C 지점에서 조금 탐색, 이런 식으로 왔다 갔다 하면서 탐색하기 때문이다.

길 찾기는 대략 다음과 같은 것들이 있다. 깊이 우선 탐색이란 무조건 목표 지점까지 깊게 들어가는 것을 말한다. 최적의 길을 찾는 것보다 길의 유무를 빨리 판단할 때 도움이 된다. 넓이 우선 탐색이란 물결이 퍼지듯이, 점점 부식 되는 것처럼 사방으로 탐색을 하는 것을 말한다. 매우 느리지만 어느 정도 최적의 길을 찾아 준다. 양방향이란 양쪽에서 접근해서 중간에 만나 탐색 시간을 줄이는 방식이다.

넓이 우선 탐색 vs 깊이 우선 탐색
단방향 탐색 vs 양방향 탐색

물결이 퍼지는 것 같은 넓이 우선 탐색 방법은 도형의 내부를 칠할 때도 유용하다. 중심에서 거리가 같은 곳까지 거품처럼 둥글게 커지는데 이 물결의 경계선까지는 직선 이동이 보장 된다. 장애물을 만나면 마치 물결이 장애물을 돌아가듯이 (회절 현상) 그 모퉁이를 다시 중심 삼아 퍼지게 된다. 이 방식에선 물결의 경계, 거품의 표면에 해당하는 방(교차로)들의 목록을 기억하고 있어야 한다. 그리고 그 목록 중에서 출발점과 목표점으로부터 거리가 가장 짧은 곳을 선택해서 그 지점에서 탐색을 해야 하기 때문에 최소값 고르기를 항상 한다는 것이다. 최소값 결정은 시간이 많이 소모된다.

더 단순한 방법으로는 정사각형을 계속 넓히며 탐색하는 방법이 있다. 8방향 타일에선 바깥 경계선은 항상 정사각형이기 때문에 따로 경계선까지 거리를 비교할 필요가 없다. 경계선 중에 무엇을 먼저 검토할지 결정하기 위해 최소값 결정도 할 필요가 없다. 경계선의 모든 점을 기계적으로 검토할 것이니까. 원형 물결이 아니라 정사각형 물결이란 점이 다르고 결국은 같은 결론에 도달한다. 6각 타일에선 자동으로 원형 물결처럼 된다. 이 방법은 넓이 우선 탐색에 해당한다. 목표를 향해 깊게 돌격하는 게 없다.

다른 방법으로는 벽 타기를 해서 틈을 발견하는 방법이 있다. 최적은 아니지만 길이 있는지 여부는 빨리 판단한다. 벽에서 떨어져야 할 때를 판단해야 한다. 목표 방향으로 장애물이 없다면 벽에서 떨어진다. 만약 장애물이 있다면 자신이 온 길을 기억하고 있어야 하고 벽에 붙어 있어야 한다.

또 다른 방법으로는 돌출 코너만 찾아 직선으로 연결하는 방법이다. 최단 거리는 직선이기 때문이다. 이 방법으로 값 싸게 최적 경로를 구할 수 있다. 여기서 최적이란 지도를 이미 알고 있을 때이고, 지도가 다 밝혀진 게 아니라면 열린 지도 영역에서만 최적이란 의미다.

출발 지점에서 물결이 퍼지고, 도착 지점에서 동시에 물결이 퍼지면 중간 어디에서 만나게 되는데 그 지점이 바로 최적 경로가 된다. 양방향 탐색과 넓이 우선 탐색을 결합하면 적당히 짧은 시간에 최적의 경로를 얻게 된다. 탐색 면적은 탐색 반경의 제곱으로 늘어나기 때문에 양쪽에서 탐색하는 것이 시간 절약이 된다. 그러면서 모든 길을 탐색했기 때문에 가장 최적의 길을 찾게 되는 것이다. 그러나 시간이 너무 많이 소모되어 시간 부족에 시달리는 게임엔 부적합하다. 에이지 오브 엠파이어 게임에선 가장 가까운 나무를 자동으로 찾는 기능이 있는데 이렇게 사방으로 탐색하지 않으면 못 찾는다.

위의 그림이 실제 A* 알고리즘을 적용한 것이다. 내가 만든 건 아니다. 누군가 알려준 글을 통해 얻은 것이다. 녹색은 탐색할 경계, 파랑은 탐색이 끝난 내부, 노랑 사각형은 찾은 길이다. 최적 경로가 아님을 알 수 있을 것이다. 최적 경로는 직선 경로다. 사각형의 좌측 하단엔 실제 이동 거리, 우측 하단엔 목표까지 직선 거리, 좌측 상단엔 평가 점수가 적혀 있다. 화살표는 자신이 어디서 왔는지 나타내는 것이다. 우측 상단이 비었는데 검토한 순서를 적어 놓으면 좋았을 것이다.

다익스트라 방식 = 넓이 우선 탐색 + 출발점에 가장 가까운 곳부터 탐색
A* 알고리즘 = 넓이/깊이 우선 절충 + 목표까지 직선 거리가 가장 짧은 곳(추가)

A*는 깊이 우선 탐색과 넓이 우선 탐색을 결합한 경우이다. 8방향, 6방향 A* 벌판 탐색 방법에 따르면 장애물이 없을 때는 목표까지 계속 직진한다. 장애물을 만나면 그 지점에서 넓게 탐색을 한다. 그러다 틈이 발견 되면 그 쪽으로 빠져나간다. 그림에서 보면 최적의 경로를 찾은 것은 아니다. 품질과 시간 사이에 절충이 있다. A*는 절충 방법이다. 길이 막히면 넓이 우선 탐색(다익스트라 방식처럼)으로 바뀐다. 8방향, 6방향 탐색 A*는 다음 순서로 동작한다.

8방향, 6방향 탐색을 해서 새로운 탐색할 경계 지점을 등록한다.
각 경계 지점에 최소 시간으로 도달할 수 있는 부모 위치를 선택한다. (다익스트라)
각 경계 지점까지 실적 거리와 목표까지 예상 거리(직선)를 구해서 더한다. A*
경계 중에서 가장 좋은 평가 점수인 지점을 하나 선택(최소 최대 구하기)한다. A*
처음으로 돌아가서 반복한다.

어떤 길을 선택할지 평가 하는 기준은 아래와 같다.

F(평가 기준) = G(출발에서 실적 거리) + H(목표까지 예상 (직선) 거리)
F가 가장 작은 방향을 선택하여 그 쪽으로 뻗는다. (마치 중력에 끌린 물처럼)
예상 거리는 직선/가로/세로/대각 거리 등 지도 형태에 따라 결정 한다.

지도 격자의 각 방은 다음과 같은 정보를 기억해야 한다.

부모 위치 (X, Y) : 어디서 왔는지 기억한다.
소모 비용 G : 출발점에서 지금까지 온 거리
예상 비용 H : 목표까지 직선/가로/세로/대각 거리 계산
평가 점수 F = G + H
자기 상태 (경계 = 열림 = 검토할 표면, 내부 = 닫힘 = 검토 끝)

8방향 탐색이란 경계 부분의 사각형이 자기 주변 8개 방을 검사해서 내부에 해당하는 것을 찾아 거기서 자기로 오는 경로 중에 가장 짧은 쪽을 선택하는 것이다. 그러니까 누구를 부모로 선택할 건지 결정하는 문제다. 그리고 자신은 주변 8개 방 중에 자식(경계)을 만든다. 경계는 열린 곳인데 아직 자신의 부모가 완전히 정해진 곳은 아니다. 내부/경계는 닫힌 곳인데 자신의 부모가 정해진 곳이다.

8방향, 6방향 탐색에선 임의의 각도로 진행할 수가 없다. 8방향에선 수직, 수평, 대각으로만 진행한다. 그러니까 45도 각도로만 움직인다. 고로 어떤 위치에 있는 목표물에 가더라도 최적의 길은 수직/수평/대각 조합으로만 구해진다. 그 목표까지 평행사변형을 그리면 그게 최적의 길이다. 직선을 쭉 그어서 이동하면 되는데 그렇게는 안 된다. 직선은 오직 수평, 수직, 대각에 있을 때만 가능하다. 6방향 탐색에선 60도 각도로만 움직인다. 여기서도 직선 이동이 가능한 경우는 3축을 따라 이동하는 것뿐이다. 나머지 위치는 톱니처럼 구불구불하게 이동하게 된다.

보면 알겠지만 아주 단순한 장애물을 넘어갈 때는 이 방법이 낭비가 많다. 그냥 벽 타기를 하는 것이 더 경제적이다. 미로에서도 벽 타기를 하면 출구에 도착은 할 수 있다. 왼쪽 또는 오른쪽 벽만 타고 가면 된다. 미로에 넓은 방이 있고 그 속에 목표물이 있을 경우는 벽 타기만으로 힘들다. 벽에서 떨어져야 하기 때문이다. 미로와 같은 복잡한 지형에선 자연스럽게 깊이 우선 탐색에 벽타기가 된다. 미로에선 교차로 지점만 기억하면 된다. 미로는 장애물이 많아서 깊이 우선 탐색으로는 최적 경로 찾기 힘들다. 분신술을 써서 여러 경로를 동시에 탐색하는 넓이 우선 탐색을 해야 한다. 여러 분신 중에서 먼저 도착하는 쪽이 최적 경로로 선택 된다.

동영상에서 다익스트라 방식(Dijkstra's algorithm)은 사방팔방으로 넓이 우선 탐색을 하고 길을 선택하는 것은 A*와 달리 출발점에서 가장 가까운 곳만 따진다. 목표까지의 거리를 따지는 것만 없다. 물결이 퍼지듯이 탐색하는 것이 다익스트라이다. 다익스트라는 출발점과 가장 가까운 지점을 먼저 선택하기 때문에 최소치 찾기를 해야 한다. A*의 경우는 출발지와 목표지의 거리를 함께 따진다. 고로 역시 최소치 찾기를 해야 한다. 이런 최소치 찾기가 시간 낭비라고 생각하면 가장 겉 표면을 무조건 돌아가면서 탐색하는 방법도 있다. 이 방법은 다익스트라보단 빠를 것이나 엉뚱한 곳도 탐색하기 때문에 그 시간 낭비가 추가 된다. (최소값 정렬을 하는 거나 모두 돌아 보는 거나 그 시간이 그 시간일 걸?)

그 어떤 알고리즘을 사용하더라도 미로에선 성능이 거의 비슷하다. 미로에선 어차피 모든 길을 다 돌아봐야 한다. 알고리즘의 성능 차이는 미로가 아닌 장애물이 단순한 벌판에서 나타난다. 직진을 하면 바로 도달하는 경우 다익스트라처럼 넓이 우선 탐색을 하는 것은 시간 낭비다. 이 경우 A*가 더 유리하다. 더 간단하게 직선을 그어서 장애물이 있는지 검사하는 것이 가장 빠르다. 장애물이 있다면 돌아가는 길을 찾아야 하는데 장애물 상태에 따라 여러 방법 중에 적당한 하나를 선택하는 게 좋다.

대부분의 경우 단순한 장벽이 있어 돌아가야 할 경우 어디로 돌아갈 것인지 빨리 결정하는데서 성능 차이가 난다. 돌아가면 길이 있는지 여부는 벽 타기를 통해서 쉽게 확인 가능하다. 반드시 돌아가야 하는 좁은 길목은 중간 목표지가 된다. 출발 ~ 중간 목표 ~ 최종 목표까지 최단거리를 구해 조립하면 더 빠르다. 이런 지점은 주로 돌출한 모서리 부분으로 반드시 돌아가야 하는 위치다. 이 모서리 부분만 직선으로 이어도 최단 거리가 나온다.

D. 편법

토폴로지(위상학)를 이용하면 고리 형태를 하는 것 외엔 모두 동그란 한 덩어리로 볼 수 있다는 것이지. 이 원리를 이용해서 동서남북 벽에 붙은 장애물의 특징을 정할 수 있지.

중앙 홀로 있는 장애물 : 0
동쪽 벽에 붙은 장애물 : 1
서쪽 벽에 붙은 장애물 : 2
남쪽 벽에 붙은 장애물 : 4
북쪽 벽에 붙은 장애물 : 8

예를 들어 동과 서에 붙은 장애물은 3 = 2+1이라고 나타낼 수 있다. 이런 특징을 장애물들이 모두 가지고 있다면 그 장애물을 만났을 때 물어 볼 수 있겠지 “너는 어디로 돌아가면 되니?” 거기에 더해서 영역에 ID를 부여할 수 있다. 연결된 영역엔 같은 ID를 부여할 수 있어 ID가 다르다면 통하는 길이 없다는 뜻이다. 목표물이 같은 영역 ID를 가진다면 길이 있다는 의미다. 장애물과 마찬가지로 영역도 동서남북 어느 벽에 붙어 있는지 확인할 수 있다.

위의 그림에서 물체는 모두 영역 C에 있다. 고로 같은 영역이니까 도달할 수 있다. 그런데 영역 C는 동/남/북 벽에 붙어 있다. 중간에 장애물을 만난다. 이 장애물은 서/남/북에 붙어 있다. 무조건 벽만 따라가면 목표물에 도달할 수 있다. 그럼 어느 쪽 방향으로 벽을 따라 가는 게 좋을까? 목표와 가장 가까운 방향으로 일단 간다. 거기서 벽 타기를 양방향으로 동시에 한다. 벽을 따라 가기 지루하니 반드시 벽을 돌아 가야 하는 모서리(돌출 코너)를 추출해서 가장 가까운 곳으로 직진하는 방법을 겸한다.

벽을 따라 갈 때는 지나온 격자 방에 왔던 방향 표시를 해 두어야 한다. 길이 만나게 되면 거기까지 오는 길 중에 짧은 길을 선택하고 긴 쪽은 무시한다. 목표까지 장애물이 없을 때는 벽에서 떨어져 직진 해도 된다. 그래서 가장 짧은 길을 선택한 다음에 그 길을 단축할 수 있는 방법을 찾는데, 그게 돌출한 모퉁이 위치만 연결하는 법이다.

지도 생성 때 이미 교차로나 돌출된 코너를 파악할 수 있다. 그리고 이 교차로/코너 사이에 직접 연결 되는 인접한 교차로/코너에 대한 정보를 연결해 둔다. 자동차 네비게이터와 비슷한 방식으로 길을 찾는 것이다. 길 탐색은 연결된 교차로/코너에 대한 탐색이다. 적절한 길 선택은 A* 방식과 비슷하다. 이렇게 여러 가지 방법을 섞어 쓰면 좀 더 빨리 길 탐색을 끝낼 수 있다.

길이 있는지 없는지 파악
길이 있다면 어느 길로, 어느 방향으로 돌아가는 게 좋은지 파악 (길 선택)
최단 거리 결정 (이건 안 해도 좋다. 길을 헤매는 게 더 그럴 듯하니까)

컴퓨터 게임에서 문제가 아직 지도를 다 열지 않아서 길을 모르는데도 유닛들이 최적의 길을 찾아 간다는 것이다. 유닛이 이동하는 것만 봐도 어디에 장애물이 있는지 추측이 가능하니 실감 나지 않는다. 시야 너머는 보이지 않는다. 지도가 없으면 길을 찾을 수 없다. 고로 유닛은 시야 범위 안에서 무조건 직진을 해야 더 그럴 듯하다. 유닛들도 길을 헤매는 모습을 보여 주는 게 더 그럴 듯하다. 우리도 미로에 들어가면 기억력의 한계 때문에 길을 헤매지 않는가?

E. 배열과 코드

이건 예제 C 코드를 분석한 것인데, 코드는 내 것이 아니라 못 올리겠다. 가장 먼저 데이터 구조를 이해해야 한다. 데이터 구조가 모든 것을 말해 준다. 구조체를 사용하지 않은 이유는 아마도 속도 때문인 것으로 보인다. 가능하면 1차원 배열을 사용해야 속도가 빠르다. 다차원 배열을 사용하면 첨자(index)의 덧셈 시간이 소모되어 속도가 떨어지겠지. 다음과 같은 배열이 필요하다.

지도 2차원 배열

지도의 갈 수 있는 곳과 없는 곳이 표시된 2차원 배열
지도의 방이 탐색할 경계인지 탐색한 내부인지 표시한 2차원 배열
각 방의 부모(출발지)의 x좌표를 저장한 2차원 배열
각 방의 부모(출발지)의 y좌표를 저장한 2차원 배열
각 방의 G값(거리)을 저장한 2차원 배열이다.

탐색 경계 1차원 배열

탐색 경계에 해당하는 방의 아래 정보에 접근할 index를 가진 1차원 배열
탐색 경계에 속하는 방의 x좌표를 저장한 1차원 배열
탐색 경계에 속하는 방의 y좌표를 저장한 1차원 배열
탐색 경계에 속하는 방의 F값(실적 + 예상 거리)을 저장한 1차원 배열
탐색 경계에 속하는 방의 H값(예상 거리)을 저장한 1차원 배열

찾은 길을 저장하는 1차원 배열

인구수에 해당하는, 그들이 기억할 길의 길이(배열 크기)
인구수에 해당하는, 그들이 기억할 길에서 현재 위치
인구수에 해당하는, 그들이 기억할 길을 저장한 가변 길이 배열

A* 호출 함수

실제 길을 찾는 함수(누구, 시작 위치, 목표 위치)

좀 더 길 찾기에만 집중하려면 누구인지도 알 필요 없겠지. 여러 유닛이 같은 길을 따라 갈 수도 있으니까.

길 찾기 작업 순서

1단계 : 지도 유닛/목표 좌표 → 격자 좌표 변환 ※ 중요한 부분은 아니다.
2단계 : 출발=도착? or 도착 지점이 갈 수 없는 곳인지 사전 체크
3단계 : 이전 길 찾기 지도에 표기한 내용들 깔끔하게 지우기
4단계 : 시작 위치를 탐색 경계 목록에 넣는다.
5단계 : 길을 찾을 때까지 아래 내용 반복.

5.1단계 : 탐색 경계 목록 중에서 가장 작은 F값인 놈을 하나 취한다.
5.2단계 : 바이너리 힙을 정리하여 다음 최소 F값인 놈을 앞에 둔다.
5.3단계 : 주변 8개 방을 돌며 다음 내용 반복.
※ 바이너리 힙은 최소값을 찾아 제일 앞에 두는 방법이다.

5.3.1단계 : 지도 밖, 탐색 영역 내부(닫힘), 장애물은 검토하지 않고 피한다.
5.3.2단계 : 수직, 수평이 동시에 막혔을 때는 그 방향 대각을 검토하지 않고 피한다.
5.3.3단계 : 새로운 방이면 경계/표면(열림) 목록에 넣는다.
5.3.4단계 : F, G, H값을 계산한다.
5.3.5단계 : 바이너리 힙을 정리하여 최소 F값인 놈을 앞에 둔다.
5,3,6단계 : 이미 경계/표면(열림) 방이면 최적의 부모를 다시 찾는다.
5.3.7단계 : F, G, H값을 계산한다.
5.3.8단계 : 바이너리 힙을 정리하여 최소 F값인 놈을 앞에 둔다.

6단계 : 탐색 경계/표면(열림) 목록에 아무것도 없으면 더 탐색할 길이 없다.
7단계 : 목표에 도달했다면 길이 있다. 길을 거꾸로 밟아 저장한다.

F. 바이너리 힙

이건 최소값, 최대값을 골라내는 방법이다. 반복해서 최소값을 찾아내야 하기 때문에 순서를 미리 정리해 두면 다음에 찾기 편할 것이다. 삽입 정렬이란 것을 사용하면 새로운 것이 추가될 때 이미 정리 해 둔 순서에 삽입해 넣기만 하면 되니까 시간이 절약 된다는 논리다. 하지만 비교와 삽입(이동)에 처리 시간이 많이 소모된다.

바이너리 힙은 토너먼트 방식의 분할 정리 방식이다. 2등 이후부터는 정확한 순서가 중요하지 않고 무조건 1등만 찾아내는 방식이다. 2명씩 대결 해서 이긴 사람끼리 싸움을 붙이는 방식이다. 각 싸움에서 이긴 사람이 높은 자리를 차지하기 때문에 나중에 새로 끼어든 놈은 1등 자리에서 시작하여 아래로 내려오며 싸워 자기 자리를 찾아 간다. 진 놈은 아래로 내려 가고, 이긴 놈은 위로 올라간다.

1등을 제외하면 같은 층에 있다고 해서 같은 실력은 아니다. 좌측이 전반적으로 약골이고 우측이 전반적으로 강골일 수 있으나 같은 층에 배치된다. 4강이라고 해서 같은 실력의 4등 안에 들어가는 것이 아니다. 토너먼트 방식에선 오직 1등만 의미가 있다. (월드컵 4강 신화가 결국 헛것이었다. 결국 우린 항상 16강도 못 되는 실력이었다.)

1차원 배열이 있을 때 첨자 0의 자리는 배열의 길이를 나타내는데 사용한다. 첨자 1은 최소값, 최대값인 1등의 자리다. 나머지 자리는 토너먼트의 각 층과 짝을 나타낸다. 그래서 자기 짝(형제)을 찾는 방법과 부모와 자식을 찾는 방법이 필요할 것이다. 왜냐하면 자식들은 부모와 싸워 자리 바꾸기를 하기 때문이다.

자세한 동작 순서는 고민해 볼 것. 나도 잘 모르겠다. ㅋㅋㅋㅋ

노인들이 박정희 시대를 살았으니 박정희에 대해 잘 안다? 히틀러 시대를 산 독일인들이 히틀러에 대해 잘 알았을까? 그럼 이 시대를 함께 사니 이명박근혜에 대해서도 잘 알겠군? 어떻게 그 시대를 살았다고 그 시대 사건들을 잘 알겠나? 보수우익꼴통들은 말이 안 되는 얘기를 하도 많이 들어서 현실감이 떨어진다.

서울대 빨갱이는 모두 북한에서 돈 받아 공부했다고 하는데 고등학교까지 교육에 얼마 들어가니? 서울대 들어가면 국가에서 돈을 주는데 왜 북한 돈을 받겠냐? 비싼 연고대라도 들어갈 정도로 머리가 나쁘면 모르겠다. 말이 안 되는 소리를 해도 믿으니 꼴통이라고 할 수밖에 없지. 얘들은 가난하기 때문에 자생적으로 빨갱이가 된 것이다. 박정희가 가난으로부터 구해주지 않아서 말이지.

페이지

2015년 1월 4일 일요일

고교 수학 수준 컴퓨터 게임 인공 지능 길 찾기