728x90 분류 전체보기222 [Algorithm] A* 알고리즘 ■ 들어가기 전 BFS의 두 가지 문제 중 가장 먼저 발견한 노드들을 방문한다는 한계점을 보완하기 위해 (1) 가중치 그래프(Weighted Graph)와 (2) 우선순위큐 (Priority Queue)를 사용한 다익스트라(Dijikstra) 알고리즘이 탄생했다. https://yjhdevelopdiary.tistory.com/196 [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 yjhdevelopdiary.tistory.com 하지만 다익스트라도 또 다른 BFS의 한계점은 보완하지 못했는데.. 2024. 3. 29. [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 탐색한다. (2) 가장 먼저 발견한(Discovered) 정점들을 방문 예약한다. 다익스트라 알고리즘은 위에서 (2) 문제를 해결하기 위해 고안된 알고리즘이다. ■ 특징 먼저 가중치 그래프를 활용하고 일반적인 큐(Queue)를 사용하는 BFS와 달리 우선순위 큐(Priority Queue)를 사용한다. (+)===== 우선 순위 큐는 아래 포스팅에 서술 및 구현해봤었다. https://yjhdevelopdiary.tistory.com/193 [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론.. 2024. 3. 25. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 25 다음 728x90
