본문 바로가기

전체 글238

[Algorithm] BFS, DFS ■ 탐색 알고리즘 BFS, DFS는 그래프를 탐색할 때 사용하는 대표적인 탐색 알고리즘이다. 그래프는 이전 포스팅에서 정리해봤다. https://yjhdevelopdiary.tistory.com/194 [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. yjhdevelopdiary.tistory.com ■ DFS (깊이 우선 탐색; Depth First Search) 시작점 기준 뎁스 가장 끝 부분까지 깊이 파고들어서 정보를 추출해주는 알고리즘이다. 막다른 길을 만날 때 까지 뎁스를 늘려 계속 파고드는 원리이다. [구현 방법] (1).. 2024. 3. 25.
[자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. ■ 구성 (1) 정점 (Vertex) : 데이터를 표현 (사물, 개념 등) (2) 간선 (Edge) : 정점들을 연결하는데 사용 [사용 예시] 1. 소셜 네트워크 관계도 2. 지하철 노선도 3. 최적 길 판단 4. 다수 간의 호감도 등 ■ 종류 (1) 가중치 그래프 (Weighted Graph) 정점과 정점 사이를 잇는 간선에 가중치(비용)가 주어진 그래프를 뜻한다. (2) 방향 그래프 (Directed Graph) 정점과 정점 사이를 잇는 간선에 방향이 주어진 그래프를 뜻한다. ■ 표현 방법 (1) 인접 리스트 :.. 2024. 3. 25.
[자료구조] 우선 순위 큐 (Priority Queue) ■ 이론 우선 순위 큐는 힙 트리(Heap Tree)의 구조를 갖는다. 최적 조건에 해당하는 값을 한 번에 구하고 싶을 때 유용한 자료구조이다. 연결리스트나 벡터 같은 경우 최대값 최소값을 찾으려면 O(n)만큼 선회하며 모든 값을 비교해줘야 도출할 수 있다. 하지만 우선순위큐는 힙트리의 구조로인하여 완전이진트리의 형태를 띄고 있다. 데이터를 삭제 및 추가하는 과정에서 대소관계를 비교하며 노드를 이동시키는 연산이 트리의 높이(logN)만큼 발생하므로 O(logN) 정도의 시간복잡도로 수행된다. [힙트리 설명 및 힙 정렬 알고리즘은 아래 포스팅에서 이전에 C#으로 구현해봤었다.] https://yjhdevelopdiary.tistory.com/172 [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 .. 2024. 3. 25.
[C++] 동적 미로 생성, 우수법 탈출 AI ■ 구조 [main] (1) 맵 생성판을 초기화 시켜준다. - Board (맵 판떼기)의 초기화 함수는 맵 동적 생성 함수를 실행시켜준다. 그 외 부수적인 함수로 인자로 받은 Pos이 지나갈 수 있는 위치인지 판별하는 함수와 색깔을 칠해주는 함수가 존재한다. (2) 플레이어 클래스를 초기화 시켜준다. 밑의 내용은 이동할 때 지나가야하는 타일들의 위치 정보를 벡터 컨테이너 담아주는 함수이다. (3) 유니티의 deltaTime처럼 이전 프레임과 현재 프레임의 차이를 인자로 player의 업데이트 함수를 실행시켜준다. - 플레이어의 Update함수는 초기화 시점에 캐싱해놨던 Pos 값들에 따라 차례대로 이동하는 함수이다. 아래 MOVE_TICK 변수의 값을 설정함으로써 이동 딜레이 시간을 조절해줄 수 있다. .. 2024. 3. 24.
[ShadeLab] Triplanar ■ 이슈 다이내믹하게 지형을 생성하면 아래와 같은 문제가 발생할 수 있다. 옆면이 찌그러진 상태로 늘어나는 현상인데 하나의 uv를 갖고 모든 면이 사용하고 있기 때문이다. 각각의 앞면, 뒷면, 옆면, 윗면 uv를 갖고 있으면 위와 같이 지형이 생성된다해도 찌그러지는 현상은 없어질 것이다. 왜 xz냐면 위에서 봤을 때 아래와 같이 U(가로)V(세로)에 대응되는 것이 xz이기 때문이다. [World Position을 uv로 활용했을때 GIF] 월드포지션 xz에 대응되는 텍스처의 uv좌표를 가져다 사용하기 때문에 월드포지션에 따라 텍스처의 모습이 바뀌는 것 이를 윗면 뿐만이 아니라 앞면, 옆면에 모두 사용해야한다. 위 Front와 Side면을 본다면 각각 uv에다가 월드좌표의 xy, zy를 대입해야함을 알 수.. 2024. 3. 11.
[ShaderLab] Water ■ 물 쉐이더 평면(Plane)을 여러개 깔아놓고 스카이박스가 반사되도록 쉐이더를 작성했다. 물보다는 수은 덩어리 같아서 알파값을 추가했고 프레넬효과를 주기 위해 앞서 배운 림라이트를 추가하였다. 이제 조금씩 움직이도록 설정했다. 노말 한 개를 두 번 다른 방향으로 시간의 흐름에 따라 움직이도록 언팩하여 이들의 평균값을 노말에 대입했다. [GIF] 이제 물에 햇빛이 반사되어보이도록 스페큘러를 추가했다. 이제 바다가 역동적으로 움직일려면 버텍스 쉐이더(vertex shader) 부분을 건드려야한다. sin 그래프와 비슷한 모양을 가질 수 있도록 의도했다. 아래 사진을 보면 y=sinx 그래프가 파도의 모습과 비슷하다는 것을 볼 수 있다. *2-1 연산으로 0~1의 범위를 -1 ~ 1의 범위로 만들어준 뒤 .. 2024. 3. 11.
[ShaderLab] Refraction ■ 굴절 (Refraction) 먼저 굴절 영역이 되어줄 quad 오브젝 하나를 배치해줬다. 해당 오브젝트의 쉐이더는 GrabPass{} 내용이 추가될 것이다. GrabPass란 화면을 캡처하는 내용이라 생각하면 된다. 이는 sampler2D _GrabTexture에 저장이 될 것이고 현재 화면의 UV 값을 가진 Input 구조체의 내장된 변수 screePos를 사용할 것이다. 일단 스크린 좌표계가 필요하기 때문에 UV가 정상적으로 입력되는지 확인해봐야 한다. screen UV가 카메라의 거리에 따른 영향을 받지 않도록 rgb/a 처리를 해줬다. 이제 uv가 정상적으로 처리되는 것을 확인했으니 이를 갖고 굴절에 적용해보겠다. 다른 오브젝트들보다 나중에 그려져야 배경을 캡쳐할 수 있으므로 Transpare.. 2024. 3. 10.
[ShaderLab] Matcap ■ Matcap이란? Matcap이란 Material Capture의 준말. Ramp Texture와 같이 이미지로 조명을 대신 사용하는 방식 [IBL; Image Based Lighting]이다. 최적화를 많이 신경써야하는 모바일에서 자주 사용하는 Fake Lighting 기법이다. 라이트를 전혀 사용하지 않고도 조명을 내는 효과를 낼 수 있다. ■ 구현 먼저 월드 좌표계 노말을 활용해 라이팅 없이 각 버텍스의 컬러를 조절해주는 설정을 해보겠다. 빛의 영향을 받지 않는 Emission에 월드노말을 대입했을 때 위와 같은 모습을 띈다. 하지만 카메라의 방향과 각도에 따라 달라지게 할려면 아래와 같이 뷰 좌표계를 기준으로 노말을 계산해줘야한다. View Matrix (뷰 행렬)을 월드 노말에 곱함으로써 뷰.. 2024. 3. 10.
[ShaderLab] Dissolve ■ Dissolve 소멸 효과를 줄 때 많이 사용하는 쉐이더 기법. Unity C#에 있는 Mathf 클래스의 Pingpong이 Shaderlab에는 없어서 어떻게 구현할지 고민 후 내장된 변수 시간(Time)에 따라 사라졌다가 다시 생기도록 설정해봤다. [1st Pass: 몸속 내부가 보이지 않도록 설정] [2nd Pass: 몸 외부가 사라졌다가 다시 생겨나는 dissovle 효과] [완성된 모습] 그냥 보기엔 밋밋하다. 사라지는 구간의 외곽에 색깔을 더하겠다. 프로퍼티로 Color와 Thickness를 추가했고 Color같은 경우 0~1범위를 벗어나는 색깔을 표현하고자 [HDR] 키워드를 추가했다. HDR을 사용하려면 그래픽세팅에 Use HDR이 체크되어있어야하고 Quality 옵션에서 Anti-Al.. 2024. 3. 6.

티스토리툴바