인공지능
목 차 인공지능 게임에서의인공지능 게임트리 A* 알고리즘 네비게이션메시 애니메이션및게임실습 2
게임에서의인공지능 게임에서인공지능의역사 1990 년대후반 1997 2000 그래픽과사운드기능의안정화 게임의재미요소요구 인공지능에사용되는 CPU : 5% 이하 인공지능담당프로그래머 : 25% 인공지능에사용되는 CPU : 25% 인공지능담당프로그래머 : 80% 애니메이션및게임실습 3
게임에서의인공지능 게임에서인공지능의역할 게임의상대역할 인공지능과의대결, 유사한수준의상대역할 게임의보조자 RPG 의보조캐릭터 NPC(Non-Player Character) RPG 에서한술집의다른손님혹은주인 주인공과의상호작용 애니메이션동작의제어 야구게임에서 1 루견제시외야수와 1 루수의움직임 애니메이션및게임실습 4
게임에서의인공지능 Rule Based System 많은규칙을나열하고현상황에해당하는규칙을골라내어이규칙에따른결과를얻는방법 Rule memory, working memory 애니메이션및게임실습 5
게임에서의인공지능 Rule Based System 규칙이많아지면현상태에해당하는규칙을찾아내는데시간이많이걸림 복잡한캐릭터의조합으로이루어지는 RPG 에서주로사용 애니메이션및게임실습 6
게임에서의인공지능 퍼지이론 Zadeh 교수의논문 Fuzzy Set 정보의손실을최소화하고인간에좀더가까운컴퓨터를만들기위해서애매한 표현도그대로기계적으로처리하는이론 애매한표현 우리반에서키큰사람 모여고에서이쁜여학생 학생들이존경하는선생님들 매우, 꽤, 별로, 약간, 적당히 애니메이션및게임실습 7
게임에서의인공지능 퍼지표현 애니메이션및게임실습 8
게임에서의인공지능 퍼지연산 애니메이션및게임실습 9
게임에서의인공지능 알파컷 소속함수의값을기준으로일정한값이상의요소를취해야할필요가있을경우에사용 퍼지집합에 α-cut 을적용하면크리스프집합획득 애니메이션및게임실습 10
게임에서의인공지능 퍼지추론 Fuzzy Rule Base (based on Expert s knowledge) g) Crisp data fuzzification Fuzzy data Fuzzy Inference Engine Fuzzy data defuzzification Crisp data 애니메이션및게임실습 11
게임에서의인공지능 역퍼지화 추론엔진으로나온 fuzzy 값을 crisp 으로변환 애니메이션및게임실습 12
게임에서의인공지능 신경망모델 신경망 개발자 ( 완성시기 ) 개발동기 퍼셉트론 F.Rosenblatt(1957) 인쇄체문자인식 자기조직화지도 T.Kohonen(1980) 패턴분류 홉필드망 J.Hopfield(1982) 영상복원및검색 네오코그니트론 K.Fukushima(1984) 필기체문자인식 역전파모델 D.Rumelhart 외 (1985) 문자인식, 음성합성등 적응공명이론 G.Carpenter 외 (1985) 레이더신호의패턴인식 볼쯔만기계 J.Hinton 외 (1986) 레이더를위한패턴인식 애니메이션및게임실습 13
게임에서의인공지능 Supervised learning Programming by example 입력과출력을알고있음 Back propagation, Hopfield Network, Boltzmann Machine Unsupervised learning 입력은알고있지만, 출력은모름 Kohonen map, ART 애니메이션및게임실습 14
게임에서의인공지능 초기신경망 애니메이션및게임실습 15
게임에서의인공지능 Back-Propagation 애니메이션및게임실습 16
게임에서의인공지능 Back-Propagation Supervised learning, Feed-forward 오류역전파 (Backward propagation of error) 출력 y ( = ) 활성화함수 i = f sum j xiwij + θ j f ( sum j ) 1 = 1+ e sum j 애니메이션및게임실습 17
게임에서의인공지능 Genetic Algorithm 자연선택또는적자생존의원칙에입각한알고리즘 개체군중에서환경에대한적합도가높은개체일수록재생할수있게되며, 개체군은환경에적응을할수있게된다. 애니메이션및게임실습 18
게임에서의인공지능 Genetic Algorithm 선택 적응도비례방식 순위방식 토너먼트방식 룰렛방식 애니메이션및게임실습 19
게임에서의인공지능 Genetic Algorithm 교배 애니메이션및게임실습 20
게임에서의인공지능 Genetic Algorithm 돌연변이 지역적한계를벗어나기위해서 00111010 0 1 1 0 1 0 00101010 0 0 1 0 1 0 애니메이션및게임실습 21
게임에서의인공지능 Genetic Algorithm 복수개의개체사이의상호협력에의한해의탐색 단순한병렬적해의탐색과비교하여보다좋은해발견용이 번거로운미분연산등이불필요 유전자알고리즘에서는현재적응도를분별할수있으면되기때문에알고리즘이단순하고, 평가함수가불연속인경우에도적용이가능 문제해결을위한일반화가없음 유전자형의코딩은설계자의몫 파라미터가많음 개체수, 선택방법, 교배법, 돌연변이의비율 애니메이션및게임실습 22
게임에서의인공지능 Decision Tree 현재의상태에따라행할기능을트리형태로나누어해당하는행동을하도록하는방법 If then else 애니메이션및게임실습 23
게임에서의인공지능 Decision Tree age income student credit_rating <=30 highh no fair <=30 high no excellent 31 40 high no fair >40 medium no fair >40 low yes fair >40 low yes excellent 31 40 low yes excellent <=30 medium no fair <=30 low yes fair >40 medium yes fair <=30 medium yes excellent 31 40 medium no excellent 31 40 high yes fair >40 medium no excellent no no student? age? <=30 30..40 >40 yes yes yes credit rating? excellent no fair yes 애니메이션및게임실습 24
게임에서의인공지능 Decision Tree 상태수의제한이없음 결과가하나혹은아주적은수 행동예측가능 애니메이션및게임실습 25
게임에서의인공지능 FSM(Finite State Machine) 유한한개수의상태들로구성된하나의간단한기계 상태 (state) 하나의조건 문 : 열린상태, 닫힌상태 하나의입력을받고그에의거해서현재상태로부터다른상태로전이하는방법 예 문 : 닫힘, 잠김 키사용 : 잠기지않은상태 손사용 : 열림상태 애니메이션및게임실습 26
게임에서의인공지능 FSM(Finite State Machine) 게임세계의관리를위한기반구조로사용 NPC 의감정조절도구 게임상태관리, 입력해석, 객체의조건관리 애니메이션및게임실습 27
게임에서의인공지능 FSM(Finite State Machine) 객체의상태구분 광분, 분노, 흥분, 불쾌, 보통 입력정의 플레이어의등장 플레이어의공격 플레이어떠남 몬스터다침 몬스터치료 애니메이션및게임실습 28
게임에서의인공지능 FSM(Finite State Machine) 보통 플레이어공격 플레이어떠남몬스터치료 흥분 몬스터다침 몬스터치료 광분 플레이어등장 몬스터치료 불쾌 몬스터치료 플레이어공격 분노 몬스터다침 애니메이션및게임실습 29
게임에서의인공지능 FSM(Finite State Machine) 현재상태입력출력상태 보통플레이어등장불쾌 보통플레이어공격흥분 흥분몬스터다침분노 흥분몬스터치료보통 분노몬스터다침광분 분노몬스처치료불쾌 광분몬스터다침광분 광분몬스터치료분노 불쾌플레이어떠남보통 불쾌플레이어공격분노 불쾌몬스터치료보통 애니메이션및게임실습 30
게임에서의인공지능 FSM(Finite State Machine) 단점 상태가늘어나면상태다이어그램을그리기어려움 상태변화를가능하게하는외부센서입력루틴이복잡 캐릭터의행동예측이쉬움 애니메이션및게임실습 31
게임에서의인공지능 실습 애니메이션및게임실습 32
게임에서의인공지능 AI 를적용한전략게임에관한연구 애니메이션및게임실습 33
게임에서의인공지능 AI 를적용한전략게임에관한연구 애니메이션및게임실습 34
게임에서의인공지능 AI 를적용한전략게임에관한연구 애니메이션및게임실습 35
게임에서의인공지능 AI 를적용한전략게임에관한연구 애니메이션및게임실습 36
게임에서의인공지능 퍼지클러스터링을이용한사용자적응형게임캐릭터의구현 애니메이션및게임실습 37
게임에서의인공지능 신경망을이용한지능형게임캐릭터의구현 상대방캐릭터의행동과상대방캐릭터와의거리를입력받아지능캐릭터의행동을결정 애니메이션및게임실습 38
게임에서의인공지능 신경망을이용한지능형게임캐릭터의구현 기초학습단계 애니메이션및게임실습 39
게임에서의인공지능 신경망을이용한지능형게임캐릭터의구현 실전학습단계 애니메이션및게임실습 40
게임트리 Game Tree 체스나장기등보드게임에서주로사용 게임트리는각각의노드가게임의한상태를의미 각노드의자식노드들은한수이후에도달할수있는다음위치들을의미 게임트리를이용해서다음수순을미리예측하고가장유리한수를찾음 복잡한게임의경우가능한수순의경우가매우크기때문에게임트리를적절한크기로제한하기위한유효한평가함수필요 애니메이션및게임실습 41
게임트리 제로섬게임 (zero-sum game) 한플레이어에게유리한수는상대플레이어에게불리한수 보드의평가를내쪽으로최대화 상대쪽으로최소화 3 목 (tic-tac-toe) 게임 애니메이션및게임실습 42
게임트리 제로섬게임 (zero-sum game) 애니메이션및게임실습 43
게임트리 Depth-First Search 애니메이션및게임실습 44
게임트리 Breadth-First Search 애니메이션및게임실습 45
게임트리 Best-First Search 깊이 - 우선 + 너비 - 우선 현재까지분기되어탐색한노드중모든잎노드들로부터가장좋은노드를선택하여확장 애니메이션및게임실습 46
게임트리 Hill-Climbing 현재의상태에서확장될수있는다음상태중에서현재상태보다더목표상태에가까운상태를하나선택한후, 이와같은방법을반복하면서목표상태를찾는방법 f ( n) = d( n) + W ( n) 애니메이션및게임실습 47
게임트리 Minimax Procedure 휴리스틱을사용하여일정한깊이까지깊이 - 우선탐색을한후가장유리한다음상태를선택하는방법 깊이 1 깊이 2 플레이어는최상의결과를낼수있는보드위치로말을이동 플레이어 1 은다음턴에서플레이어 2 가최고의결과를얻지못하게하는이동 애니메이션및게임실습 48
게임트리 Minimax Procedure 애니메이션및게임실습 49
게임트리 Minimax alpha-beta pruning 특정경우게임트리의일정가지는더이상탐색할필요가없다는점에기반 상대가현재위치이후의어떤지점에서더유리한결과를얻을수있다면, 현재위치를만드는수는나에게무조건불리하므로더이상고려할필요가없음 현재최대값이나의현재최대값보다크다면그부분이하는더이상고려하지않음 나의최대값 : 알파 상대의현재최대값 : 베타 애니메이션및게임실습 50
게임트리 Minimax alpha-beta pruning >=2 Q=2 R<=1 S 5 10 2 P=1?? 애니메이션및게임실습 51
A* 알고리즘 A* 의개요 상태공간안의특정상태에이웃한, 즉인접한상태들을조사해나가면서시작상태로부터목표상태로이르는가장싼비용의경로를찾는알고리즘 맵상의두지점들사이의경로를찾는방법 두지점을잇는경로가여러개존재할때가장짧은경로를찾음 비교적빠르게탐색 애니메이션및게임실습 52
A* 알고리즘 용어들 맵 (map) 또는그래프 (graph) A* 가두지점사이의경로를찾고자할때사용하는공간 사각형, 육각형, 3차원영역, 게임트리의공간적표현 노드 (node) 맵상의위치및부가정보를표현하는자료구조 거리 (distance) 또는휴리스틱 (heuristic) 탐색되는노드의적합성을평가하는데사용 비용 (cost) 거리 + 에너지 + 여비 + etc 애니메이션및게임실습 53
A* 알고리즘 알고리즘 현재의위치에서목표물까지가는경로찾기 f = g + h f : fitness( 적합도 ), g : goal( 목표 ), h : heuristic( 휴리스틱 ) S 1 2 3 4 5 T 애니메이션및게임실습 54
A* 알고리즘 h 구하기 Manhattan distance h( n) = D*( abs( n. x goal. x) + abs( n. y goal. y)) 애니메이션및게임실습 55
A* 알고리즘 h 구하기 Diagonal distance h( n) = D*max( abs( n. x goal. x), abs( n. y goal. y)) 애니메이션및게임실습 56
A* 알고리즘 h 구하기 Euclidean distance h 2 ( n) = D* ( n. x goal. x) + ( n. y goal. y ) 2 애니메이션및게임실습 57
A* 알고리즘 알고리즘 열린목록 (Open List) 아직탐색하지않은노드들 닫힌목록 (Closed List) 이미탐색한노드들 이미탐색한노드들의재탐색방지 애니메이션및게임실습 58
A* 알고리즘 알고리즘 1. 시작지점을노드 P로지정 2. P에 f, g, h 값들배정 3. P를열린목록에추가 4. 열린목록의노드들중최선의노드를 B로둔다 1. B가목표노드이면탐색종료 2. 열린목록이비었으면탐색실패 5. B 에연결된유효한노드를 C 로둔다 1. C에 f, g, h 값들배정 2. C가열린목록이나닫힌목록에들어있는지점검 1. 만일들어있으면새경로가효율적인지점검 1. 만일그렇지않으면경로갱신 2. 들어있지않다면 C를열린목록에추가 3. 단계 5를 B에연결된모든유효한자식노드들에대해반복 6. 4 부터다시반복 애니메이션및게임실습 59
A* 알고리즘 예제 애니메이션및게임실습 60
A* 알고리즘 예제 애니메이션및게임실습 61
A* 알고리즘 예제 애니메이션및게임실습 62
A* 알고리즘 예제 애니메이션및게임실습 63
A* 알고리즘 실습 애니메이션및게임실습 64
A* 알고리즘 실습 애니메이션및게임실습 65
A* 알고리즘 단점 메모리효율성 열린목록과닫힌목록의관리 CPU 효율성 비현실적인 CPU 사용량 경로가존재하지않는경우 모든경로탐색후존재여부확인가능 애니메이션및게임실습 66
A* 의미학적최적화 자연스러운경로만들기 경로직선화 경로매끄럽게만들기 직접적인경로만들기 애니메이션및게임실습 67
A* 의미학적최적화 직선적경로 좀더지능적이고자연스러운경로만들기 비용가중치에대한고려 현재상태와동일한방향이아니면비용증가 검색속도의저하 애니메이션및게임실습 68
A* 의미학적최적화 매끄러운경로 부드러운방향전환 Catmull-Rom 스플라인곡선 제어점들을지나는곡선 부드러운곡선 베지어 (Bezier) 곡선 제어점들을지나지않는곡선 가장부드러운곡선 애니메이션및게임실습 69
A* 의미학적최적화 Catmull-Rom 스플라인기법 주어진네개의입력점들로부터두번째와세번째점을지나는매끄러운곡선생성 애니메이션및게임실습 70
A* 의미학적최적화 Catmull-Rom 스플라인기법 u = 0.0 ~ 1.0 output_point point = point_1 * (-0.5f*u*u*u + u*u 0.5f*u) + point_2 * (1.5f*u*u*u + -2.5f*u*u + 1.0f) + point_3 * (-1.5f*u*u*u + 2.0f*u*u + 0.5f*u) + point_4 * (0.5f*u*u*u + -0.5f*u*u) 애니메이션및게임실습 71
A* 의미학적최적화 직접적인경로만들기 계통적경로만들기 (hierarchical pathing) 검색대상공간을계통적으로분할 큰범위공간에서경로탐색 하위범위공간들에서개별적으로경로탐색 애니메이션및게임실습 72
A* 의미학적최적화 직접적인경로만들기 애니메이션및게임실습 73
A* 의미학적최적화 직접적인경로만들기 야외에서의계통적길찾기 애니메이션및게임실습 74
A* 의미학적최적화 직접적인경로만들기 계통적검색도중의시간지연 부분적인길찾기의반복으로인한검색지연발생가능 입구에도착하기전에다음경로탐색시작 반응성 길찾기의성능에따른실제감감소 체감반응시간의감소필요 소리이용 : 명령에대한대답, 옛써 눈속임애니메이션의사용 큐를이용한순차적경로탐색 : 집단행동의경우 리더만탐색 : 집단행동의경우 애니메이션및게임실습 75
A* 의속도최적화 A* 의단점극복 검색공간의최적화 1000 X 1000 크기의사각형격자맵 : 1,000,000 개의노드존재 검색공간의최적화필요 메모리사용의최적화필요 빈번한메모리할당과해제 빈번한정렬 A* 를쓰지않는경우를이용 직선화 애니메이션및게임실습 76
A* 의속도최적화 검색공간의최적화 검색공간을표현하기위한네가지방식 사각또는육각형격자 실제다각형바닥 특수화된다각형바닥 가시점 (point of visibility) 방식 애니메이션및게임실습 77
A* 의속도최적화 검색공간의최적화 사각또는육각형격자 피해가야할장애물이나캐릭터들을격자안에서표현하기쉬움 2D 타일기반맵에적합 검색공간의크기가가장큼 사각형격자는 3D 세계와부조화 캐릭터가칸단위로이동하므로이동경로의부자연스러움발생 애니메이션및게임실습 78
A* 의속도최적화 검색공간의최적화 실제다각형바닥 데이터구조가이미 3D 맵에존재 BSP 트리를이용한빠른검색가능 3D 맵이복잡하면다각형들의개수가매우많을가능성존재 공간안의캐릭터들이나바닥위에놓여진탁자나의자같은장애물들을표현할수없음 다각형안의제어점들을선택하기위한알고리즘필요 애니메이션및게임실습 79
A* 의속도최적화 검색공간의최적화 특수화된다각형바닥 검색공간이작다 BSP 트리를이용한빠른검색가능 바닥위에놓인장애물들의표현가능 레벨디자이너의수작업필요 공간안의캐릭터들을표현할수없음 다각형안의제어점들을선택하기위한알고리즘필요 애니메이션및게임실습 80
A* 의속도최적화 검색공간의최적화 가시점방식 게임세계안에서어떠한장애물에도부딛히지않고돌아다닐수있는직선들로구성된그래프 애니메이션및게임실습 81
A* 의속도최적화 검색공간의최적화 가시점방식 가장작은검색공간 장애물들이함께표현 결과로얻은경로가완전직접적 알고리즘또는수작업을통해서사전에그래프생성 장애물이파괴되어도그래프상에서는여전히장애물이있는상태로남음 공간안의캐릭터들을표현할수없음 넓게늘어선캐릭터들처럼너비가큰객체들을제대로다루지못함 곡선으로된벽이존재하면그래프가필요이상으로복잡해짐 애니메이션및게임실습 82
A* 의속도최적화 알고리즘의최적화 휴리스틱비용 (heuristic cost) : 목표까지의실제비용을미리추정한값 휴리스틱비용의과대평가 목표를향한빠른진행, 속도향상 휴리스틱비용의과소평가 목표에대한최적경로, 탐색시간소요 애니메이션및게임실습 83
A* 의속도최적화 알고리즘의최적화 휴리스틱비용의과대평가 노드선택기준 : 총비용이작은노드 총비용 : 현재노드까지의비용 + 휴리스틱비용 애니메이션및게임실습 84
A* 의속도최적화 알고리즘의최적화 검색공간으로부터길찾기데이터분리 A* 는각각의검색과정을저장하기위해서상당한양의메모리소비 이메모리는검색가능한각노드안에저장 검색공간이사각형격자인경우 : 각칸마다저장 검색공간이다각형메시인경우 : 각삼각형마다저장 1,000 X 1,000의타일로된맵에서 100 X 100의영역에대해검색이수행되면총 9/10 의메모리낭비 길찾기노드데이터를검색공간에서분리 메모리요구량감소 검색속도향상 애니메이션및게임실습 85
A* 의속도최적화 알고리즘의최적화 최소량의메모리를미리할당 검색공간에서노드데이터를분리할경우메모리할당과해제에따른문제발생 한번의 A* 검색에충분할정도의메모리블록을미리할당해두고매번의 A* 검색마다그것을재사용 부모노드를가리키는포인터 이노드까지의비용 총비용 이노드가열린목록에들어있는지의여부 이노드가닫힌목록에들어있는지의여부 애니메이션및게임실습 86
네비게이션메시 개념 3D 공간을 2D 공간으로변환 장애물들을제외한바닥부분을삼각형메시로만드는것 캐릭터가마음놓고이동할수있는하나의자유공간 애니메이션및게임실습 87
네비게이션메시 Navigation Mesh 2D 타일기반게임의격자시스템과동일한방식으로처리가능 메시를구성하는각각의삼각형을격자의칸으로간주 3D 의장점활용가능 크기가다른삼각형을이용하여계단, 언덕표현가능 높이가다른삼각형들을겹쳐서다리표현가능 객체와주변의정적인환경사이의충돌검사에필요한계산량감소 애니메이션및게임실습 88
네비게이션메시 구조 삼각형들로만구성 하나의평면 전체메시는반드시연속적이어야함 모든인접한삼각형들은두개의정점들과하나의변을공유 서로다른두삼각형이동일한평면에겹치면안됨 어떤삼각형안의한점은오직그삼각형에만속해야함 애니메이션및게임실습 89
네비게이션메시 활용 객체가네비게이션메시상에서만움직이기 제어점 : 메시표면위를자유롭게움직일수있지만표면바깥으로나갈수없음 객체가움직이면제어점도같이움직임 객체의위치를갱신하면, 갱신된위치는네비게이션메시표면상의제어점의위치로변환 그위치는 3D 환경안에서의객체의실제위치로변환 그결과객체는새로운위치로변환 애니메이션및게임실습 90
네비게이션메시 알고리즘 객체의이동벡터를현재칸의평면에대해투영. 즉 3D 이동벡터를현재칸의평면상의 2D 벡터로변환. 이벡터를이동경로라고하고하나의 2D 선분으로표현 이동경로가메시칸의 2D 삼각형변들과교차하는지검사 이동경로가공유되지않는벽에교차한다면벽이나어떤장애물과충돌이동경로의선분을제한하거나객체의방향을조정 이동경로가공유된변과교차한다면인접한칸으로이동단계 1로돌아가서새칸의평면에대해다시벡터를투영하고교차검사 나머지경우는이동이현재삼각형을벗어나지않은경우선분의끝에해당하는점을다시 3D 좌표로변환하고그것을이용해서실제로객체이동 애니메이션및게임실습 91
네비게이션메시 개선된알고리즘 빠른투영을위해서모든칸들의법선들이미리주어진축과동일한방향을가지게함 제어점으로부터목표위치로가는이동경로를만들고, 주어진공통축값을제거해서 2D 이동벡터를얻음 2D 이동벡터와삼각형변들의교차여부를판단하는과정수행 새 (x, z) 제어점이놓여진칸의평면방정식을이용해서 (x,z) 로부터 y 값을얻음 얻어진좌표를이용해서실제 3D 좌표로객체이동 애니메이션및게임실습 92
네비게이션메시 최적의경로찾기 애니메이션및게임실습 93
네비게이션메시 좀더그럴듯한경로 애니메이션및게임실습 94
네비게이션메시 실습 애니메이션및게임실습 95
네비게이션메시 실습 애니메이션및게임실습 96
Question? 애니메이션및게임실습 97