KiTFOx's Notepad 📝

이번에는 맵 이동을 하는 알고리즘에 관한 고찰을 해볼것인데..

아직 리소스가 부족해서 마을은 못만들었지만 가명으로 F마을,W마을이라고 하겠다.

일단 MapManager를 만들어보자

F로 가는 포탈은 파란색 지점에 W로 가는 포탈은 초록색 지점에 있다.

먼저 mapArray로 3가지의 맵을 불러오자.

3개의 맵오브젝트는 Map이라는 게임 오브젝트의 하위에 들어있으며 Awake()함수에서 자동으로 불러오도록 하겠다.

게임을 시작하면 Map 하위 오브젝트들을 불러오는 것을 확인할 수 있다.

그다음 각각의 포탈들을 불러오는 코드들을 똑같이 적용하여준다.

포탈들도 똑같은 과정을 이용하여서 적용시켜준다.

하지만 구조를 다르게 만들었다. 두개 포탈을 이용하여서 왔다갔다 할 수 있도록 만들려고 한다.

두개의 transform을 담고 있는 linkedPotal이라는 클래스를 만들고 2개의 포탈 정보를 저장하고 포탈 정보를 들고 올 수 있도록 만들었다.

2중 for문을 이용하여서 하위 오브젝트 한개를 들고 오고 그 오브젝트의 하위오브젝트들을 저장하는 형식으로 제작하였다.

시작되면 차례차례대로 들어가는걸 볼 수 있다.

이제 포탈에 닿으면 지정된 위치로 변하는 코드를 짜보자

플레이어가 포탈에 닿으면 MapManager의 enterPotal이란 함수를 실행시키도록 하겠다.

밑에 부분은 짤렸는데 pos를 반환한다.

반환한것을 플레이어에서 임시로 저장해놓는다.

왜냐면 fade in과 out을 실행할 것이기 때문이다. 

여기서 잠깐 헤매었는데 fade in out을 시작 싸인을 주고 바로 position을 비꿔버리니까 어색한 감이 있어서 fade out으로 변하는 반환점에서 플레이어의 위치값을 변경해주었다.

할 때는 fade in과 out을 할 생각이 없었는데 하다보니 빠져들어서 홀린듯이 하게 되었다.

완성된 모습

흰색 큐브가 포탈 역할을 한다.

sweep and prune은 교수님께서 특정 논문을 읽으라고 하셨을 때 본 방법입니다

하지만 한글 해석이 된 포스팅이 없어서 간단하게 번역하여 놓고 점점 추가 및 보완할 예정입니다

해당 포스팅은 https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune 을 한국어로 해석한 포스팅으로 문제가될 시 삭제하도록 하겠습니다

광역 충돌 시스템은 모든 물리 엔진의 핵심 과정 중 하나입니다.

이미 광역 충돌에 대해 놓친 게 있다면 광역 충돌시스템을 최적화하는 코드를 짜서 복구하기는 어렵습니다.

물리 엔진에서 충돌 단계에는 3가지가 있습니다.

1. Broadphase : 광대한 범위

- 여기서 어떤 충돌이 실제로 일어날 수 있는지를 감지하고, 충돌할 수 없는 충돌을 폐기합니다.

참고할만한 사이트 : https://developer.nvidia.com/gpugems/gpugems3/part-v-physics-simulation/chapter-32-broad-phase-collision-detection-cuda

2. Midphase : 중간 범위

- 구나 천 물체 같은 기하학적 단계에서의 충돌을 말합니다. 

3. Narrowphase : 좁은 범위

- 이 단계에서 실제 충돌 감지를 수행합니다.  교차점, 충돌 법선 또는 침투 깊이와 같은 충돌 데이터를 검색하는 작업을 합니다.

거의 모든 광역 시스템은 객체의 축 정렬된 경계 상자(aabb)를 사용합니다.

aabb는 꽤 빨리 계산될 수 있으며 교차점을 확인하는 것도 몇 줄의 코드로 수행됩니다.

참고할만한 사이트 : https://blog.naver.com/mycode333/50031266282

그렇다면, 어떻게 하면 "겹치지 않는 쌍의 정렬 과정"을 가속화 할 수 있을까요?

충돌을 감지하기 위한 예전의 접근방식에 대해 몇 가지를 알아봅시다.

for (int i = 0; I < rigidBodies.Count; i++)
{
    for (int e = i; e < rigidBodies.Count; e++)
    {
        if (CheckBoundingBoxForOverlap(i, e))
            DetectNarrowPhase(i,e);
    }
}

그렇게 나쁘지는 않지만..

만약 10x10x10 충돌 감지 되는 큐브가 있다면, 최상의 경우 수천 개의 충돌 가능한 쌍을 확인하여 위의 코드를 수행해야 합니다. 좁은 범위의 충돌 체크는 0.25백만 개를 체크해야합니다.

자연적으로 광역 범위는 O(n^2) 문제가 생기는데 이에 대해 무엇을 할 수 있을까요?

데이터 구조를 가속화해야 합니다.

웹에서 "광역상 충돌 탐지"를 검색하면 Sweep And Prune(SAP)접근법을 발견하게 됩니다.

많은 변형된 구현들이 있지만 분류한 다음 다듬는다(Prune)는 공통점이 있습니다.

SAP 알고리즘에서 가장 간단한 "flavor"를 지속되지 않는 단일 축 SAP에서 사용한다는 것이 무엇을 의미하는지 알아봅시다.

1. 공간 안의 모든 물체들은 "AxisList"라는 목록 안에 들어있습니다. 경계상자의 시작을 이용해 한 개의 축(여기서는 X축)으로 리스트를 정렬합니다. 따라서 물체 5의 가장 왼쪽 지점이 X축을 직접 볼 때 물체 6의 가장 왼쪽 지점보다 더 왼쪽에 있다는 것을 알 수 있습니다.

2. "ActiveList"라는 새로운 임시 리스트를 만들자. 이제 "AxisList"의 다음 항목을 보고 "ActiveList"의 모든 항목과 비교합니다.(현재는 단 하나) 만약 새 항목의 왼쪽이 더 크면 현재 "ActiveList"의 오른쪽 항목이 제거되고 "ActiveList"에서 현재 "ActiveList" 아이템이 제거됩니다. 그렇지 않으면 새 "AxisList" 항목과 현재 "ActiveList" 항목 간의 충돌 가능성이 생깁니다. 새 항목 자체를 "ActiveList"에 추가하고 "AxisList"의 다음 항목을 계속합니다.

이 접근법이 지속적이지 않다는 것을 알게됩니다.

정렬은 처음부터 모든 프레임에서 수행되며(quicksort 성능이 좋다) 한 축(여기에서는 X축)에 대해 정렬된다.

우리는 장면의 일관성을 이용하지 않는다.(한 프레임에서 장면이 많이 변하지 않을 가능성이 있다)

속도 향상은 어디서 발생하는것일까?

정답은 충돌 탐지는 검색 문제이기 때문입니다. 그리고 사전 분류된 목록을 검색은 O(nlog(n)) 보다 빠릅니다.

이 쉬운 접근법을 구현하면 무차별 힘 알고리즘(brute force algorithm)에 비해 엄청난 속도 향상이 가능합니다.

JigLib (Danny Chapman이 만든 코드)에서 C # (JigLibX)로 이식되었을 때, JigLib의 원래 버전은 무차별적인 힘과 매우 기본적인 그리드 접근법을 포함하고있었습니다.
존 와트는 위에서 설명한 코드를 정확하게 사용하는 프로젝트에 SAP 알고리즘을 적용했는데, 이는 복잡한 그리드 접근법을 쉽게 극복했습니다.

따라서 이 코드는 이미 꽤 잘 수행되지만, 그럼에도 불구하고 X축에서 모든 물체가 겹치면 런타임은 다시 O (n *2)이다.

(따라서, 대부분의 물체가 그곳에서 겹치기 때문에, 분리 축으로 up-축을 사용하지 않아야 합니다)

Sweep and Prune을 하기 위한 더 복잡한(그리고 더 빠른) 접근법은 완전한 3축 검사를 하는 것입니다.

두 물체가 충돌하면 세 축 모두 겹치는 경우에만 충돌합니다 (분리 축 정리).

지속적 3Axis SAP는 다음과 같이 요약하여 작동합니다.

우리는 세 개의 목록 (각 축 1에 대해)을 사용하고 삽입 정렬을 사용하여 정렬된 목록을 유지합니다.

삽입 정렬은 거의 정렬된 목록에서 O(n)입니다.

삽입 정렬 알고리즘의 스왑은 개체가 다른 본체와 중첩되기 시작/중지하는 것을 의미합니다.

그래서 한 개의 해시 테이블을 겹쳐서 보관하고, 각 프레임은 삽입구역을 하고, 해시 테이블 구조를 업데이트하는 데 사용하는 변경사항만 보고받습니다.

Jitter의 절차

private void SortAxis(List<SweepPoint> axis)
{
    for (int j = 1; j < axis.Count; j++)
    {
        SweepPoint keyelement = axis[j];
        float key = keyelement.Value;
        
        int i = j - 1;
        
        while (i >= 0 && axis[i].Value > key)
        {
            SweepPoint swapper = axis[i];
            
            if (keyelement.Begin && !swapper.Begin)
            {
                if (CheckBoundingBoxes(swapper.Body, keyelement.Body))
                {
                    lock (fullOverlaps)
                    {
                        fullOverlaps.Add(new BroadphasePair(swapper.Body, keyelement.Body));
                    }
                }
            }
            
            if (!keyelement.Begin && swapper.Begin)
            {
                lock (fullOverlaps) 
                {
                    fullOverlaps.Remove(new BroadphasePair(swapper.Body, keyelement.Body));
                }
            }
            
            axis[i + 1] = swapper;
            i = i - 1;
        }
        axis[i + 1] = keyelement;
    }
}

만약 당신이 전형적인 SAP 데이터 구조의 모든 세부사항에 관심이 있다면, 나는 피에르 테르디만이 쓴 훌륭한 기사를 읽을 것을 추천합니다.

그렇지 않다면 각 프레임에 "A가 축 C에서 B와 겹친다"는 정보나 "A가 축 C에서 B의 중첩을 중지했다"는 정보만 전달받으면 X, Y 또는 Z축이 될 수 있습니다.

처음 이것을 시행했을 때, 나는 내가 받는 값싼 결과에 매우 만족했고, 그리고 나서 실수를 했습니다.

각각의 쌍이 얼마나 중복되는지를 기억하는 데이터 구조를 구현했습니다.

겹치는 횟수가 3회(모든 축에서 겹치는 횟수가 1회임을 의미)인 경우, 물체는 충돌합니다.

이것은 효과가 있지만 끔찍합니다.

한 축에 겹치는 쌍의 수는 매우 높을 수 있으므로 중복 계수 = 1인 수천 개의 잠재적 겹치는 쌍을 저장해야 한다. 단지 몇 개만 두 번째 축에 겹치고 겹치는 횟수가 2이고, 세 번째 축에 겹치는 횟수는 3이라는 것을 깨달았습니다.

결국 런타임은 O(nlogn)였지만 메모리 사용량은 O(n^2)이었다(내 사전 구조를 죽이는 것)

이 문제의 해결책은 간단합니다. 아무것도 저장하지 마라.

한 축이 중첩을 보고하는 경우 저렴한 전체 경계 상자 확인 – 양수일 경우 해당 쌍을 풀오버랩에 추가하십시오.

한 축에 두 개의 몸체가 분리되어 있다고 보고된 경우, 풀오버랩에서 쌍을 제거하십시오. (이것은 위의 코드로 행해진다.) 따라서 SAP에 사용되는 메모리는 다시 O(n)에 지나지 않습니다.

("CollisionSystemPersistent"에서 Jitter의 구현을 찾을 수 있음) SAP.cs".)

지속적인 Sweep and Prune 알고리즘의 단점 중 하나는 많은 비활성 객체를 가진 정말 큰 세계를 경험한다는 것이다.

총알이 정적인 물체가 많은 마을을 관통하는 것을 상상해보라.

각 물체(총탄으로부터 수마일 떨어져 있어도)와 탄환 자체 사이에 교환이 있다

이 문제는 그리드(광범위 단계)를 구성하는 여러 개의 소형 SAP를 사용하여 해결할 수 있다.

내가 알아차린 또 다른 문제는 광선과 경계 상자 질의가 효율적으로 수행될 수 없다는 것이다.

레이캐스팅의 경우, 정렬된 세 개의 목록은 균일하지 않은 복셀 그리드로 해석될 수 있으므로, 주문한 레이 쿼리를 얻을 수 있다.

이것은 실제로는 다소 느리다.

왜냐하면 많은 복셀 그리드가 비어 있고 초기 타격을 받은 광선에 대한 해결책일 뿐이기 때문이다.

단지 각 물체에 대해 거친 힘 검사를 하는 것이 종종 더 빠르기 때문이다.

또 다른 문제는 장면에 하나의 큰 물체(대개 지면이나 레벨)가 포함되어 있다는 것이다.
이 개체의 끝점은 완전히 왼쪽에 있고 목록 오른쪽에 있다.

스위프 포인트에 저장된 추가 정보가 없으면 개체가 훨씬 더 큰 엔티티의 끝점에 의해 둘러싸이는지 여부를 효율적으로 감지할 수 있는 방법이 없다.

소켓이란

-TCP/IP로 통신하는 컴퓨터가 가지는 네트워크 내의 주소인 IP address,IP address의 서브 address인 포트 번호를 조합한 Network address

-네트워크 상에서 클라이언트 프로그램과 서버 프로그램 사이의 통신방법

-네트워크상에서 서버와 클라이언트 두개의 프로그램이 특정포트를 통해 양방향 통신이 가능하도록 만들어주는 소프트웨어 장치

-멀리 떨어져 있는 두개의 호스트(host)를 연결시켜주는 매개체 역할

-소켓은 반드시 네트워크를 통해서 통신을 할 때만 사용되는 것은 아님

-유닉스 계열의 시스템에서 시스템 내부의 프로세스들끼리 통신을 하기 위한 용도로도 사용될 수 있음

프로토콜이란

정보기기 사이에서 정보교환이 필요한 경우, 이를 원활하게 하기 위하여 정한 여러가지 통신규칙과 방법에 대한 약속

일반적으로 기종이 다른 컴퓨터는 통신규약도 다르기 때문에 기종이 다른 컴퓨터간에 정보통신을 하려면 표준 프로토콜을 설정하여 통신망을 구축하여야 한다.

대표적인 표준 프로토콜의 예는 인터넷에서 사용하고 있는 TCP/IP가 이에 해당된다.

프로토콜에 포함되어야 할 목록

오류제어,동기,흐름제어,코드변환,전송속도,통신하는 상대방의 위치에 따라 통신 개체가 어느 OSI 계층에 있는 가,효율적인 정보전송을 위한 기법,정보의 안전성(보안)에 관한 약속

새 프로젝트를 눌러주자!

이런 창이 뜨면 Win32 콜솔 응용 프로그램을 만들것이다.

이름을 바꿔주면 프로젝트의 이름이 바뀌고 위치는 자신이 설정해주고 싶은 곳에 지정해주면 된다.

(참고로 이름과 솔루션 이름은 동일하게 자동으로 입력된다.)

확인을 누르고 그다음 뜨는 창에서 다음을 또 눌러주자.

이러한 창이 뜨게 되면 우리가 만들고 싶은 것은 빈 프로젝트이기에 빈프로젝트를 체크하고 마침을 눌러주면 생성된다.

자 그러면 이제 솔루션 탐색기에 내가 만든 프로젝트가 뜨게 되는데 여기에서

[소스파일] 우클릭 -> 추가 -> 새 항목 을 눌러주자

그러면 이러한 창이 뜨게 되는데

C++ 파일 을 클릭해놓고 이른에는 소스이름(소스이름은 꼭 영어로 만들도록 하자).c 를 해주어야한다.

소스이름.cpp 파일을 만들게 되면 C언어가 아닌 C++언어로 만들어지므로 확장자는 꼭 .c로 만들어주도록 하자.

야생의 빈 소스파일이 하나 만들어졌다!

그러면 이제 수학의 집합단원과 같은 C언어의 Hello,World! 출력하는 코드를 한번 만들어보자.

이렇게 적었으면 Ctrl+F5 번을 눌러서 솔루션을 빌드해보자.

이런 창이 떳다면 성공한것이다. (한글 윈도우에서는 "계속하려면 아무 키나 누르십시오..." 일것이다.)

한글을 적어도 잘 출력된다.

음 그런데 여기서 창의 색깔이 흰색인게 마음에 안든다 싶으면 창에서 마우스 우클릭을 하면

여기서 Properties(속성)에 들어가보자.

여기서 여러가지 속성을 바꿀 수 있다.

이렇게 바꿀 수 있다!

*C언어는 절차지향적 특성을 지닌다.

C언어는 정해진 순서의 실행흐름을 중시한다. 절차지향적이기 때문에 처음 접하는 사람도 조금만 공부하면 쉽게 익숙해질 수 있다.

*C언어로 구현된 프로그램은 좋은 성능을 보인다.

사용하는 메모리의 양이 상대적으로 적고, 속도를 저하시키는 요소들을 최소화한 언어이기 때문이다.