본문 바로가기

알고리즘

[알고리즘] FSM, HFSM, BT의 특징
[알고리즘] FSM, HFSM, BT의 특징 🎲 Finite State Machine (유한상태머신) 캐릭터나 몬스터의 행동을 정의하고 구현하기 위해 나온 방법입니다. 각각의 행동상태를 state로 정의하고 특정 조건에 따라 다른state로 넘어가는 방식입니다. 단순히 조건문을 도배하는것보다 훨씬 효율적인 방법이긴 하지만 state가 많아질수록 걷잡을 수 없이 복잡해지기 때문에 복잡한 형태의 AI는 구현하거나 행동들을 추가, 삭제, 수정하기 힘듭니다. 언리얼의 애니메이션 블루프린트와 유니티의 애니메이터 컨트롤러가 이러한 형태입니다. 🎲 Hirerarchy Finite State Machine (계층적 유한상태기계) FSM의 문제점을 조금 개선한 형태의 방식입니다. 특정 상태들이 동시에 이루어지는 것을 FSM에서는 구현하기 힘들었기 때문에 HFSM에..
[Algorithm] CCW알고리즘과 선분 교차 판정 알고리즘
[Algorithm] CCW알고리즘과 선분 교차 판정 알고리즘 CCW알고리즘이란? Counter Clock Wise의 약자로, 벡터의 외적을 이용하여 선분AB를 기준으로 점C가 시계반향에 있는지, 반시계반향에 있는지를 판단하는 알고리즘입니다. 선분 교차 알고리즘이란? 선분 교차 알고리즘은 CCW알고리즘을 이용해서 구할 수 있습니다. 선분AB와 선분CD가 주어질 때, 선분AB를 기준으로 점 C, D가 각각 시계, 반시계 반향에 있고, 선분CD를 기준으로 점 A, B가 각각 시계, 반시계 반향에 있을경우 두선분은 교차합니다. 각각의 선분이 반대 방향인지는 각각의 단위벡터의 z값을 곱했을 때 음수일 경우 다른 방향, 양수일 경우 같은 방향으로 판단합니다.
[Algorithm] 행렬 저장 방법 (COO, CSR, CSC)
[Algorithm] 행렬 저장 방법 (COO, CSR, CSC) Normal Matrix - 기본적인 행렬 저장 방식입니다. 행렬값들을 순차적으로 저장하기 때문에 행렬의 사이즈만 따로 저장해주고 행렬의 인덱스값은 저장하지 않아도 됩니다. 행렬의 데이터 사이즈가 1byte라고 할 때, 아래의 행렬은 36bytes를 차지합니다. COO(COOrdinate matrix) - COO 행렬은 기존 행렬처럼 각각의 값을 위치에 맞게 나열하여 저장하는 것이 아닌, (행, 열, 값)을 하나의 묶음으로 저장하는 방식입니다. 때문에 값이 비어있는 칸(값이 0인)이 많으면 많을 수록 효율적인 저장 방식입니다. 행열의 인덱스가 1byte라고 가정할 때 24bytes를 차지합니다. CSR(Compressed Sparse Row) - COO 행렬의 Row인덱스를 압축하는 방식입니다. 이때, ..

티스토리툴바