Game AI

more

GAME AI - LOD

2024.02.25 - [Game AI] - AI 스케줄링 AI 스케줄링 AI Scheduling 게임이 균등한 프레임을 뽑기 위해서는 다양한 작업들이 제한된 시간 내에 수행되어야 한다. AI역시 마찬가지인데, 이를 제한된 시간 내에 처리하기 위해서는 다음의 3가지 요소가 필 tsyang.tistory.com 개요 게임 그래픽에 LOD를 적용하듯, AI에도 LOD를 적용할 수 있다. 가령 어떤 캐릭터는 복잡하고 정교한 행동을 하고 어떤 캐릭터는 단순한 행동을 하도록 할 수 있다. 그러나 게임 AI의 LOD는 그래픽처럼 단순히 거리만으로 처리할 수 없다. 그래픽과 달리 AI 캐릭터들이 우리가 보고 있지 않을 때도 항상 행동하길 기대하기 때문이다. AI의 LOD는 그 캐릭터가 게임에서 어떤 역할을 하냐에 따..

Game AI 2024.03.03 0

AI 스케줄링

AI Scheduling 게임이 균등한 프레임을 뽑기 위해서는 다양한 작업들이 제한된 시간 내에 수행되어야 한다. AI역시 마찬가지인데, 이를 제한된 시간 내에 처리하기 위해서는 다음의 3가지 요소가 필요하다. AI 작업들에 적절한 시간을 분배하는 것 AI 작업을 여러 프레임에 걸쳐서 수행할 수 있는 알고리즘 AI 작업간에 우선순위 Frequency 작업을 스케줄링하는 가장 간단한 방법 중 하나는 빈도(frequency)를 이용하는 것이다. 스케줄러는 매 프레임마다 어떤 작업을 수행할 것인지를 결정한다. 이때 작업들은 각자 frequency를 가지고 있으며 스케줄러는 이 값을 이용하여 작업을 수행한다. 가령 어떤 작업의 frequency가 5프레임이라면, 스케줄러는 해당 작업을 5프레임마다 한 번 수행한..

Game AI 2024.02.25 0

의사 난수

의사 난수 프로그래밍에서 난수란 세 가지 카테고리로 나눌 수 있다. (거의) 진짜 난수 : 특별한 하드웨어로 만드는 난수들. 각종 물리 실험이나 장비등에 쓰임 암호학 난수(해시값 등) : 사실 난수는 아니지만 예측불가능하고 충분히 잘 분포됨. 보통의 의사난수 : Seed가 필요하며, 생성되는 난수들이 결정적(deterministic)임. 생성되는 난수들을 이용하여 역으로 Seed를 구할 수 있음 의사 난수 생성기는 Seed값에 따라 생성되는 난수들이 결정적이기 때문에, 이를 잘 활용하면 유용하다. 때로는 게임 전체에서 단 하나의 난수 생성기를 사용하기 보다는 분야별로 여러 개의 난수 생성기를 사용하는 것이 좋을 수 있다. 가령 절차적인 맵을 생성하는 게임에서 단 하나의 난수 생성기만 사용한다면 플레이어가..

Game AI 2024.02.18 0

C# / C++

more

ValueTask / ValueTask

이게 뭐고 왜 쓰나 이름처럼 ValueTask는 값(Value) 타입의 Task객체이다. 그렇다 Task는 참조 타입이다. 따라서 Task객체를 생성하는 것은 곧 힙 할당이 일어난다는 말이다. 그런데 Task들 중에서는 작업이 동기적으로 완료될 수 있는 애들이 있다. 즉 한 Task를 호출한 쓰레드가 그대로 이어서 다음 코드를 실행하는 것이다. private async Task GetData(int index){ if (_cachedData.TryGetValue(index, out var data)) return data; return await CalcSomethingLong(index);} 이를태면 위와 같은 메서드는 그 값이 이미 계산된 적이 있다면 즉시 값을 리턴한다. 이 ..

C# 2024.05.02 0

Task.Delay (vs Thread.Sleep)

개요 Task.Delay를 통해 진행중인 Task를 일시정지 할 수 있다. public static async Task DoSomethingAsync() { await Task.Delay(100); //100ms 이상 대기한다. return Thread.CurrentThread.ManagedThreadId; } 이를 이용하여 소프트 타임아웃을 구현할 수 있다. public static async Task TaskWithSoftTimeout() { Task someTask = DoSomethingAsync(); var timeoutTask = Task.Delay(100); //둘 중 하나가 완료되길 대기 var completeTask = Task.WhenAny(someTask, timeoutTask); i..

C# 2024.04.10 2

동시성 개요

개념 정리 동시성 : 한 번에 두 가지 이상의 작업을 수행 멀티스레딩 : 다수의 실행 스레드를 사용하는 동시성의 한 형태 병렬 처리 : 많은 작업을 여러 스레드에 나눠 수행하는 멀티스레딩의 한 형태 비동기 프로그래밍 : 불필요한 스레드의 사용을 피하기 위해 퓨처나 콜백을 사용하는 동시성의 한 형태 리액티브 프로그래밍 : 앱이 이벤트에 대응하는 방식 병렬 프로그래밍 병렬 프로그래밍은 데이터 병렬과 작업 병렬로 나눌 수 있다. 데이터 병렬 : 처리해야 할 데이터들을 다른 데이터들과 독립적으로 처리할 수 있을 때 해당된다. 작업 병렬 : 작업 풀에 있는 작업들이 다른 작업과 독립적일 때 해당. 모든 작업이 독립적이면 동기화가 필요 없어지므로 병렬 처리가 극대화된다. 스레드 풀 스레드 풀은 알아서 작업을 잘 처..

C# 2024.04.01 0

게임 엔진

more

엔진 지원 시스템

시스템 클래스 생성 게임에서 사용되는 각종 매니저와 같은 싱글톤 혹은 정적 클래스들은 어떻게 생성하고 파괴해야 할까? 이런 클래스들을 생성/파괴할 때는 클래스들끼리의 의존성을 고려해야 한다. 유일한 클래스를 생성하는 메서드를 정의한 다음 의존성에 맞게 호출. //class RenderManager //... static RenderManager& get() { static RenderManager sSingleton; return sSingleton; } RenderManager() { VideoManager::get(); TextureManager::get(); //... } //... 그러나 위와 같은 방법은 아래와 같은 단점이 있다. 파괴 순서를 제어할 수 없어 파괴 과정에서 의존성이 훼손될 수 있..

일반 2024.02.11 0

IL2CPP가 Virtual Call과 Boxing을 처리하는 방법

이 글의 정보들은 2016년에 작성된 글을 기반으로 함. 따라서 2023년 현재 바뀐 부분이 있을 수 있음. Devirtualization 당연한 얘기지만, Virtual Call은 Direct Call보다 더 느리다. 따라서 일부 컴파일러는 Virtual Call을 Direct Call로 바꾸는 Devirtualization 기법을 사용하기도 한다. 단, 해당 코드가 컴파일 타임에 어떤 메서드를 실행시킬지를 판단할 수 있어야 한다. 이는 IL2CPP도 마찬가지이다. 다만 IL2CPP는 최적화에 보수적이기 때문에... var dog = new Dog(); //Dog는 Animal 클래스를 상속함. dog.Speak(); 위와 같은 상황에서도 Virtual Call을 호출하는 C++코드를 만들어낸다. (2..

유니티 2023.11.19 0

(협업) Unity Accelerator - 임포트 시간 단축

에셋 임포팅 에셋 데이터는 CPU GPU등의 하드웨어에서 즉시 쓰일 수 있는 포맷일 필요가 있다. 그러나 대부분의 파일 포맷은 저장공간을 최소화하도록 되어있다.(압축) 따라서 유니티는 저장공간에 있는 데이터를 에셋 데이터로 컨버전 한다. 그리고 이렇게 변환된 에셋 데이터는 라이브러리 폴더에 캐싱된다. 이 과정을 에셋 임포팅이라 한다. 문제는? 근데 에셋 임포팅은 오래 걸림. 변경이 많으면 많을수록 더 오래걸린다. 만약 아예 모든 에셋을 임포트 해야 하는 상황이거나 플랫폼을 바꿔야 하는 경우라면 더욱 더 오래걸린다. 그러면 이걸 어떻게 해결할까? 임포트된 에셋 데이터는 라이브러리에 캐싱된다. 따라서 팀내에서 라이브러리 폴더를 공유할 수 있다. 플랫폼 스위칭 같은 경우를 대비하여 플랫폼별로 라이브러리 폴더를..

유니티 2023.06.10 0

이론

more

게임 네트워크 - 보안

패킷 스니핑 중간자 공격을 막기 위해서는 민감한 데이터를 암호화해야 한다. 평범한 리플리케이션 같은 정도라면 중간자가 감청해봤자 별 소용이 없을 것이다. 그럼에도 패킷 스니핑 측면에서는 암호화도 고려할만 한다. 모든 네트워크 게임은 호스트 머신에서 수행하는 패킷 스니핑에 노출되어 있다고 봐야 한다. 아무리 암호화를 해도 실행 파일 어딘가에는 암호를 해독하는 체계가 있을 것이고 이런 체계를 밝히는 것은 시간 문제이다. 그럼에도 잠재적인 치터가 분석하기 어렵도록 암호화를 하는 게 좋다. 더 나아가 암호 키와 메모리 오프셋을 주기적으로 변경하는것이 좋은데, 치터를 귀찮게 할 수 있기 때문이다. 어쨋든 결국에 암호화는 뚫릴 것이기 때문에 호스트에게 내려주는 정보를 제한하는 것도 하나의 방법이다. (ex. FPS..

네트워크 2023.09.17 0

네트워크 - 스코프

객체 스코프 멀리 떨어져서 알 필요 없는 플레이어의 정보를 동기화 하는것은 리소스 낭비이다. 따라서 어떤 객체가 특정 클라이언트의 동기화 대상이라면, 해당 객체가 클라이언트의 스코프 내에 있다 혹은 해당 클라이언트와 연관성(relevancy)이 있다라고 표현할 수 있다. 스코프를 나눌 때, 얼마나 떨어져 있는지를 기준으로 쓸 수 있다. 그러나 FPS의 줌같은 개념때문에 거리만 가지고 판단하는것은 애매하다. 또 벽 뒤나 등 뒤에 있는 객체들은 거리만 가지고 판단하기 애매한데, 그래서 가시성을 객체 스코프 판정에 활용하기도 한다. . 스태틱 존 스코프에 포함되는 잠재적인 객체 수를 줄이는 방법 중 하나로, 월드를 고정된 여러 지역으로 나눌 수 있다. 이렇게 나준 지역을 스태틱 존이라고 한다. 가령 MMORP..

네트워크 2023.09.10 0

네트워크 - 레이턴시 및 신뢰성

레이턴시 레이턴시 원인 네트워크가 아닌 레이턴시로 입력 샘플링, 랜더링, 인풋렉 등등이 있을 수 있다. 네트워크에 해당하는 레이턴시에는 다음 지연들이 포함된다. 처리 지연 : 네트워크 주소 변환이나 암호화 => 요즘 라우터 성능이 좋아서 크게 신경쓰지 않아도.. 전송 지연 : 물리적 매체에 비트를 기록하는 시간. => 서버의 물리적 위치 조정이나, 패킷을 가능한 크게 만들어서 헤더 비중이 적게 만들어 개선할 수 있음. 큐잉 지연 : 라우터의 처리 용량보다 많은 패킷이 도착했을 때 큐잉해놓고 나중에 처리. 이때 대기열에 머무르는 시간 => 적은 수의 큰 패킷을 보내는게 유리하다. 전파 지연 : 매체를 타고 전파되는데 걸리는 시간. => 일단 물리적 거리를 가깝게 할 수 있음. 그러나 라우터등의 배치에 따라..

기초 2023.09.01 0

수학

more

한 점과 가장 가까운 곡선 위의 점 구하기

※ 매개변수로 표현할 수 있는 곡선 (ex. 베지에 곡선)의 경우만 다룸. 관련 글 : 2021.07.11 - [이론] - 곡선(Curve) & 스플라인(Spline) 곡선(Curve) & 스플라인(Spline) 곡선 곡선을 표현하기에 앞서, 두 정점 (A, B) 사이에 있는 점 P를 다음과 같이 표현할 수 있다. 또한 곡선은 t에 대한 방정식(P(t))으로 표현할 수 있다. 베지에 곡선(Bézier Curves) n차 베지에 곡선은 n tsyang.tistory.com 문제 Q ) t에대한 다항식으로 이뤄져 있는 곡선 $q(t)$ 와 곡선 밖의 점 $P$가 있다. 이때 점 $P$와 가장 가까운 곡선 $q(t)$ 위의 점 $X$는 어떻게 구할 수 있을까? 곡선 $q(t)$를 2차원상의 3차 베지에 곡선이..

이론 2021.09.04 0

다항식의 근 구하기

루트격리(root isolation) 루트 격리는 근이 여러 개인 다항식에서 정해진 개수의 근이 존재하는 구간을 구하는 것이다. (주로 근이 1개인 구간을 구한다.) 이를 이용해서 근 구하기 알고리즘 등을 사용한다. 1. 스트룸 정리 아래에 있는 데카르트 부호 법칙에 기반한 방법이나, 빈센트 정리에 기반한 방법보다는 느리고 덜 효율적이다. 중근을 한 개로 간주한다는 특징이 있어 덜 효율적이지만 꽤 쓰이는 듯. https://tsyang.tistory.com/62 스트룸 정리 (Strum's theorem) 루트 격리 (root isolation) 위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경..

이론 2021.08.29 0

스트룸 체인(Strum Chain) 구현

2021.08.13 - [수학] - 스트룸 정리 (Strum's theorem) 스트룸 정리 (Strum's theorem) 루트 격리 (root isolation) 위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경우 모든 tsyang.tistory.com 목표 : 스트룸 정리를 이용하여 다항식의 해 찾기. 다항식 클래스 우선 다항식을 표현할 방법이 필요하여 Polynomial 클래스를 만들었다. Polynomial 클래스는 $a_0x^0 + a_1x^1+a_2x^2+ ... + a_nx^n$ 으로 표현되는 다항식의 각 계수 $(a_0, a_1, ... , a_n)$를 저장한다. 스트룸 정리에 ..

구현 2021.08.22 0