■ 방 생성 BSP 알고리즘을 통해 공갈이 분할되면, 자식이 없는 단말(리프) 노드에 실제 방을 생성해야 한다. 단말 노드들은 더 이상 분할되지 않는 영역이기 때문이다.private List GetAllLeafNode(){ var leafNodes = new List(); var queue = new Queue(new[] { _roomNodeList[0] }); while (queue.Count > 0) { var node = queue.Dequeue(); if (node.ChildNode.Count 너비 우선 탐색(BFS) 방식으로 트리를 순회하며, 자식 노드가 없는 경우(단말 노드)만 리스트에 추가한다. ■ 방 생성 구현public class RoomGenerator{ private..

2025-05-15 (수정사항)- NodePosition을 초기화 할 때 (좌상단, 우하단)기준에서 (좌하단, 우상단)기준으로 초기화하도록 수정. ■ 이진 공간 분할법 - Binary Space Partitioning(BSP) BSP 알고리즘은 공간을 재귀적으로 둘로 분할해 가며 이진트리를 구성하는 알고리즘이다. 최종적으로 자식이 없는 리프 노드에 각 분할된 공간이 저장된다.이를 활용하여 던전등의 지형을 절차적으로 생성할 수 있다. BSP 알고리즘 동작 순서현재 공간의 분할 방향(수직, 수평)을 결정한다.선택된 방향으로 공간을 2개로 분할, 이 공간을 큐에 추가한다.분할된 공간에 대해 1~2번의 과정을 더 이상 분할이 불가능할때까지 반복한다. ■ BSP 구현1. BSP 트리 노드 구성using Syste..

■ 터레인 생성 앞서 생성했던 PerlinNoise 맵을 HeightMap으로 사용하여 Terrain을 만들어보자. Unity에서 Terrain을 생성하는 과정은 매우 간단하다. 1. Terrain 생성 코드public void CreateTerrain(){ var terrainData = terrain.terrainData; terrainData.heightmapResolution = Mathf.Max(noiseData.Width, noiseData.Height); terrainData.size = new Vector3(noiseData.Width, maxHeight, noiseData.Height); terrainData.SetHeights(0, 0, _fractalMap); Set..

■ 프랙탈 합(Fractal Noise)하나의 PerlinNoise는 큰 흐름만 존재하고 세부 디테일이 부족하기 때문에, 복잡한 자연 지형을 표현하기엔 한계가 있다.복잡한 자연 지형을 표현하기 위해 동일한 PerlinNoise를 여러 옥타브(Octave)에 걸쳐 주파수(Frequency - 빈도)는 높이고, 진폭(Amplitude-세기)은 줄이며 반복적으로 합산한 복합 노이즈인 프렉탈 합(Fractal Noise)를 사용한다.이러한 방식은 fBm(Fractal Brownian Motion)이라고도 불리며, 다양한 랜덤 패턴의 기반이 된다.Fractal Noise는 자연 지형, 구름, 바위 텍스처 등의 절차적 생성에 사용된다. 보통 다음과 같은 파라미터로 주파수와 진폭을 제어한다.Lacunarity : 주..

■ PerlinNoise PerlinNoise는 1983년 Ken Perlin이 개발한 그래디언트 기반의 노이즈(Gradient Noise)함수로, 지형의 절차적 생성, 텍스처 생성, 구름이나 연기 같은 자연 현상 표현 등 다양한 절차적 콘텐츠 생성에 활용된다. 1. Noise함수 Noise함수는 입력값에 따라 “의사 난수(Pseudo-random)”값을 반환하는 함수다. 일반적인 난수와 달리, 입력값이 비슷할수록 결과값도 유사해지는 부드러운 변화를 가진다.// 호출할 때마다 완전히 다른 값.Random.Range(0f, 1f);// 항상 같은 입력에 같은 결과.Mathf.PerlinNoise(x, y);// 입력이 조금 달라지면, 출력도 조금만 변화 -> 부드러운 노이즈Mathf.PerlinNoise..

■ Recursive BacktrackingRecursive Backtracking은 말 그대로,재귀(Recursive) 적으로 경로를 탐색하고,백트래킹(Backtracking), 즉 더 이상 갈 수 없을 때 되돌아가며 다른 경로를 찾는 알고리즘이다. 🛠️ 알고리즘 핵심 구조먼저 임의의 시작 위치로부터 랜덤한 방향을 선택해 두 칸 떨어진 타일로 이동할 수 있는지 확인한다. 이때, 중간에 있는 벽을 허물고 다음 타일까지 길을 만든다. 여기서 “두 칸 이동”이 핵심이다. 만약 인접한 타일(1칸 거리)을 곧바로 길로 만든다면, 그 셀이 이미 길인지 아닌지를 구분할 수 없어 모든 타일이 길인 허술한 미로가 만들어진다. 미로의 구조는 항상 [길] → [벽] → [길] 순서를 따른다.따라서 길을 만들 땐, 중간의..

■ A* 알고리즘“BFS에서 발전한 알고리즘이 다익스트라라면, 다익스트라에서 한 단계 더 발전한 것이 바로 A 알고리즘이다.” 다익스트라와 동작 방식은 비슷하지만, 목표 노드(n)까지의 거리 측정값인 휴리스틱(Heuristic)을 추가로 사용한다. 각 타일에는 다음과 같은 정보가 저장된다. 이름설명 g(n) 현재 노드까지의 누적 비용. 가중치가 없다면 상하좌우 이동은 10(또는 1), 대각선 이동은 14(또는 1.4)로 계산한다. h(n) 목표 지점까지의 예상 비용(휴리스틱). 맨해튼 거리 방식이나 정수 근사 휴리스틱(10/14)을 사용해 계산한다. f(n) g(n) + h(n). A* 알고리즘에서 우선순위를 결정할 때 사용하는 총 비용. 다익스트라에서는 우선순위 큐의 기준이 g(n) 값(누적..

■ 다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘은 가중치 있는 그래프에서 시작 노드부터 다른 노드들까지의 최단 경로를 찾는다.시작 노드로부터 모든 노드에 대한 최단 경로를 계산한다.가중치는 음수일 수 없다.다익스트라는 그라디(Greedy) 알고리즘이며, 동적 배열 갱신 과정에서 다이내믹 프로그래밍의 성격도 일부 포함된다그라디 알고리즘과 다이나믹 프로그래밍에 대해 정리한 부분은 아래에서 참조할 수 있다. ▼ 그라디 알고리즘2025.04.10 - [Unity,C#/알고리즘] - [C#, Algorithm] 그라디(탐욕, 욕심쟁이) 알고리즘 [C#, Algorithm] 그라디(탐욕, 욕심쟁이) 알고리즘■ 그라디(Greedy) 알고리즘그라디(탐욕, 욕심쟁이) 알고리즘은 매 단계에서 “가장 좋아 보이는..

■ Dynamic Programming(동적 계획법)큰 문제를 작은 문제로 나누고, 그 작은 문제의 결과를 저장하여 같은 계산을 반복하지 않도록 하는 알고리즘 기법이다.중복 부분 문제 (Overlapping Subproblems)동일한 부분 문제를 여러 번 계산하게 되는 구조.최적 부분 구조(Optimal Substructure)문제의 최적해가 부분 문제의 최적해로 구성될 수 있다.기법특징 재귀 모든 경우를 완전 탐색. 그라디 항상 가장 좋아 보이는 선택을 한다. 최적해를 보장하지 않을 수 있다. DP 중복 계산을 피하며 모든 경우를 고려. 항상 최적해를 구한다.  DP에는 크게 2가지 구현 방식이 있다. 이 구현 방식을 피보나치 수열을 구하는 문제를 통해 알아보자. 1. Top-Down 방식p..