Minkowski Sum Minkowski Sum 입니다.https://en.wikipedia.org/wiki/Minkowski_addition 2D Polygon A, B 가 존재할 때 각 Polygon 의 영역을 합한 새로운 영역을 얻습니다.외각 Vertex 를 얻을 수 있으며 ( 0, 0 ) 을 기준으로 합하므로, 기준 좌표를 옮겨 A, B 도형 위로 옮길 수 있습니다. Your browser does not support the HTML canvas tag. 알고리즘 2024.04.26
이진검색 트리 ( binary search tree ) 트리 ( tree ) 는 부모와 자식간의 관계로 이뤄진 구조이다. 여기서 이진 트리 ( binary tree ) 는 이진 ( 2 ) 개의 자식으로 이뤄진 트리 구조이며, 왼쪽의 자식 ( child ) 는 왼쪽 부분 트리 ( left subtree ), 오른쪽 부분 트리 ( right subtree ) 로 부른다. 정의 ( definition ) 을 보면 아래와 같다. 순서가능집합 ( ordered set ) 에 속한 구성 ( item ) 으로 구성된 이진 트리이며 아래 조건을 만족해야 한다. 각 마디는 하나의 키만 가지고 있다 여기서 키는 노드가 대표하는 값 ( id ) 이다 주어진 마디의 왼쪽 부분트리에 있는 키는 그 마디 ( 부모 ) 의 키보다 작거나 같다 주어진 마디의 오른쪽 부분트리에 있는 키는 .. 알고리즘/Search 2023.05.07
AI Perception Perception? 단어의 뜻은 "감각" 을 의미한다. 흔히 AI ( None PC ) 를 표현한다는 것은 의도를 잘 표현하는 것을 의미한다. 여기서 의도를 잘 표현하기 위해서는 적절한 판단을 할 수 있어야하고, 이것은 판단을 위한 정보를 관찰하는 것으로 시작한다. 어떤 정보를 "관찰" 하느냐에 따라 판단의 결과가 달라질 수 있다. 이런 의미로 UE 의 AI System 은 "AI Perception" 을 소개하고 있다. 지금까지는 Perception 의 개념을 설명한 것이고 UE System 관점에서는 행동 양식을 결정하는 데이터가 "BT" 에 의존적이기 때문에 "정보" 를 수집하는 Perception 도 BT 와 연동되어 있다. 여기서 "관찰" 을 두 가지 관점으로 바라볼 수 있다. 첫 번째는 "즉.. 알고리즘/GameAI 2023.05.05
Binary Search 이분검색 ( Binary Search ) Time : O ( logN ) Space : O ( n ) 탐색을 요구하는 대상은 정렬이 필요하다 ( "오름차순" 이 아니여도 상관없다. 방향에 따른 pivot 위치만 바꾸면 된다 ) ( 정렬은 다른 포스팅에서 다루기로 한다 ) 정렬된 대상의 중간 값으로 찾는 값의 크고 작음을 이분하여 다음 순서에 탐색하는 공간을 반씩 줄여간다. 전체 공간을 반씩 줄여가기 때문에 탐색 공간이 log(2) 로 줄어든다. 탐색 공간이 더 이상 없으면 ( low > high ) 탐색에 실패한다. function search(arr, x) { const length = arr.length; let low = 0; let high = length; let mid; let idx = 0;.. 알고리즘/Search 2023.04.29
Sequential Search 순차검색 ( Sequential Search ) Time : O ( n ) Space : O ( n ) Iterator 를 순회하며 Index 를 증가시킨다. 순회 도중에 값과 일치하는 Value 의 Index 를 찾는다. function search(arr, x) { let idx = 0; // result const length = arr.length; while (idx < length && arr[idx] != x) { idx += 1; } // fail to find. if (idx == length) { return -1; } // success return idx; } 알고리즘/Search 2023.04.29
HTN ( Hierarchy Task Network ) "HTN" 은 Hierarchy Task Network 의 약어로 "HTN Planner" 는 현재 상황에서 가장 적절한 Decision 을 하기 위한 계획을 수립합니다. HTN 은 수 많은 TASK 로 구성되어 있으며 "HTN Planner" 는 복수 개의 Task 에서 가장 적절한 Task 들을 선택하여 계획 ( plan ) 을 세웁니다. 이는 Planning 방식으로 많이 알려진 G.O.A.P 과 비슷하지만 차이점이 있습니다. 용어 HTN 은 아래와 같은 추상화 된 개념을 가지고 있습니다. Plan : Task 들의 집합으로 목적을 달성하기 위한 작은 작업들의 집합입니다 Domain : 복수 개의 선언된 Task 들의 집합입니다. Plan 은 Domain 의 Task 로 구성됩니다 WorldStat.. 알고리즘/GameAI 2023.04.29
Smart Object Smart Object 를 처음 접하여 빠르게 개념을 이해하고 싶은 사람, 기억이 나지 않을 때를 위해 내용을 정리합니다. Smart Object 란? 상호 작용이 가능한 Object 를 정의하기 위한 데이터를 ( 행동 양식 ) 을 직접 지정하여, 외부에서 요청에 의한 미리 정의된 패턴 ( 행동 양식 ) 을 손쉽게 수행할 수 있는 도구 입니다. 동작의 흐름 Actor 에 Smart Object Component 를 추가하면서 시작됩니다. Smart Object Component 가 추가된 Actor 는 Smart Object 로써 동작할 수 있습니다. Smart Object Component 에는 Slot 의 개념이 추가됩니다. Slot 이란 위치를 기반으로 행동 양식을 직접 지정할 수 있는 데이터 포맷.. 알고리즘/GameAI 2023.04.29
G.O.A.P ( Goal Oriented Action Planning ) G.O.A.P ( Goal Oriented Action Planning ) 목적 ( 상태 ) 을 달성하기 위한 일련의 행동 ( 액션 ) 을 계획하는 Planner 입니다. 복잡한 FMS 없이 의사결정을 달성할 수 있어 확장하기 용이합니다. G.O.A.P 에서 사용되는 용어는 아래와 같습니다. Action : 상태를 변화하는 행위 Preconditions : 전제조건 Effects : 효과 G.O.A.P 의 Plan 이 수립되는 흐름은 아래와 같습니다. Init State → ( conditon ) Action ( → effect ) → ( condition ) Action ... → Goal 계획 방식은 "backward chaning search" 를 사용하는데 과정은 아래와 같습니다. Add the .. 알고리즘/GameAI 2023.04.29
Alias method Algorithm "Alias method" 를 사용하여 probability ( 확률 ) 기반의 RandomValue ( Index ) 를 얻고자 하는데 관련 한글 문서가 없었다. 영문 위키를 찾아봤지만 생략된 내용이 많아 이해하기 어려웠다. 구글링을 하다 좋은 영문 포스팅을 찾게 되었고 포스팅 : https://www.keithschwarz.com/darts-dice-coins/ 위키 : https://en.wikipedia.org/wiki/Alias_method 이를 통해 대략적인 원리를 이해하는데 도움을 받았다. 그래서 누군가에게 도움이 될까 싶어 이번 기회에 한글로 정리하고자 한다. 원문에서는 수식 및 공식이 많고 이미지가 많은데 최대한 정리하여 핵심 아이디어만 작성한다. Alias method 를 설명하기 전에.. 알고리즘 2023.04.27
boids Boids 알고리즘은 많겠지만 간단한 알고리즘을 써봤습니다. youtube 영상에서 boids 시뮬레이션을 보고, gtihub 주소가 있어 확인했습니다. https://github.com/jackaperkins/boids GitHub - jackaperkins/boids: The age old boids project! The age old boids project! Contribute to jackaperkins/boids development by creating an account on GitHub. github.com 내용 중 boids 알고리즘 부분은 다소 간단하게 확인할 수 있습니다. "boids.pde" 내용으로 아래 절차를 따르고 있습니다. 1. update 1-1. collect boid.. 알고리즘 2023.04.23