알고리즘
27편
안 보이는 것을 안 그리는 값도 든다
앞의 여섯 편은 무엇을 판정할지 줄였습니다. 컬링은 무엇을 그릴지 줄입니다. 절두체 판정을 하나씩 할 때와 묶어서 할 때, 구로 먼저 거를 때의 손익, LOD 가 덜컹거리는 횟수를 실측으로 봅니다.
벽은 막고 문은 통과시킨다
앞의 다섯 편은 물체를 추렸습니다. 포털 컬링은 보이는 영역 자체를 잘라 나갑니다. 문을 지날 때마다 시야가 얼마나 좁아지는지, BSP(binary space partitioning)가 왜 축에 갇히지 않는지 실측으로 봅니다.
움직이는 것들에는 트리를 짓지 않는다
앞의 네 편은 구조를 지어 두고 질의를 던졌습니다. 스윕 앤 프룬(sweep and prune)은 한 축으로 줄만 세워 둡니다. 프레임마다 순서가 거의 안 바뀐다는 성질 하나로 어디까지 갈 수 있는지, 대신 무엇을 내주는지 실측으로 봅니다.
공간이 아니라 물체를 나눈다
격자도 쿼드트리도 KD 트리도 공간을 잘라 왔습니다. BVH(bounding volume hierarchy)는 물체를 둘로 갈라 각 무리를 상자로 감쌉니다. 크기가 있는 물체가 왜 여기에만 온전히 담기는지, 상자끼리 겹쳐도 괜찮은 이유를 실측으로 봅니다.
가운데가 아니라 중앙값에서 자른다
쿼드트리는 공간의 한가운데를 자르고 KD 트리(k-d tree)는 점들의 중앙값을 자릅니다. 트리 모양이 분포에서 풀려나는 대신 무엇을 내주는지, 가지치기가 실제로 몇 개를 걷어 내는지 실측으로 봅니다.
빈 곳은 큰 칸 하나로 남긴다
밀도가 고르지 않으면 칸 크기를 하나로 정할 수 없습니다. 붐비는 칸만 넷으로 쪼개는 쿼드트리(quadtree)의 동작과, 격자보다 나은 자리와 나쁜 자리를 실측으로 갈라 봅니다.
좌표를 칸으로, 칸을 배열로
균일 격자를 실제로 만들 때 막히는 자리들입니다. 음수 좌표에서 칸 번호가 어긋나는 이유, 맵 밖을 다루는 공간 해시(spatial hash), 같은 쌍을 두 번 보지 않는 법, 칸마다 리스트를 두지 않고 배열 세 개로 짓는 법.
내비메시는 바닥이 아니라 설 수 있는 자리다
유니티가 내비메시를 구울 때 실제로 하는 일과, 런타임에 NavMeshAgent 가 하는 일입니다. 보켈로 덮고 반지름만큼 물러나는 과정, 폴리곤 통로와 코너, 카빙과 링크가 치르는 값.
통로 안에서 줄을 당긴다
길찾기가 내놓은 계단 경로와 폴리곤 통로를 사람이 걷는 선으로 펴는 방법입니다. 보이는 점끼리 잇는 스트링 풀링(String Pulling)과, 통로 안 최단을 한 번에 뽑는 깔때기 알고리즘(Funnel Algorithm).
지도 한 장을 모두가 읽는다
유닛 수백 마리가 같은 곳으로 갈 때 각자 길을 찾는 대신, 목표에서 거꾸로 채운 지도를 한 장 만들어 모두가 읽는 방법입니다. 흐름 필드(Flow Field)의 세 겹 구조와 손익분기점, 목표가 바뀔 때 치르는 값.
칸이 아니라 구역 사이를 먼저 잇는다
맵이 커지면 한 칸씩 훑는 길찾기는 넓이만큼 헤맵니다. 맵을 구역으로 나누고 구역 사이만 미리 이어 두는 계층형 길찾기(HPA*, Hierarchical Pathfinding A*)의 구조와, 전처리·경로 품질·구역 크기의 거래.
건너뛰어도 되는 칸은 건너뛴다
균일한 격자에서는 같은 비용의 길이 수십 개라서 탐색이 그만큼 넓어집니다. 그중 하나만 보게 만드는 점프 포인트 서치(JPS, Jump Point Search)의 규칙과, 이 방법이 통하지 않는 자리.
음수가 있거나 모든 쌍이 필요할 때
비용이 가장 적은 후보부터 확정하는 방식이 안 통하는 두 경우입니다. 음수 간선을 다루는 벨만-포드(Bellman-Ford)와 모든 쌍의 거리를 한 번에 구하는 플로이드-워셜(Floyd-Warshall), 그리고 셋 중 무엇을 고를지.
남은 거리를 짐작하면 덜 헤맨다
목표가 하나일 때 탐색을 그쪽으로 기울이는 A 스타(A*) 알고리즘입니다. 휴리스틱이 지켜야 하는 조건, 과대평가하면 무엇이 깨지는지, 격자에서 무엇을 쓰고 동점은 어떻게 처리하는지.
꺼내는 순서를 큐가 아니라 비용이 정한다
칸마다 이동 비용이 다른 맵에서 최단 경로를 찾는 다익스트라 알고리즘(Dijkstra's algorithm)입니다. 왜 한 번 확정한 것을 다시 안 봐도 되는지, 음수 간선에서 왜 무너지는지, 게임에서 가중치를 어디서 얻는지.
가장 작은 것만 꺼낼 건데 전부 정렬할 필요는 없다
우선순위 큐(priority queue)와 그것을 떠받치는 이진 힙(binary heap) 이야기입니다. 트리처럼 보이지만 배열 하나이고, 넣기와 꺼내기가 왜 둘 다 log n 인지, 유니티에서는 무엇을 쓸 수 있는지 봅니다.
채우기는 어디서 멈출지를 색으로 정한다
매치3의 같은 색 묶기, 페인트 통, 지뢰찾기의 빈 칸 열기가 전부 플러드 필(flood fill) 하나입니다. 이웃을 색으로 정하는 탐색이 어디서 터지고, 네 방향과 여덟 방향이 무엇을 바꾸는지 봅니다.
가까운 곳부터 한 겹씩 퍼지면 그게 곧 최단 거리다
너비 우선 탐색은 꺼내는 자리를 스택에서 큐로 바꾼 것이 전부입니다. 그 하나가 왜 최단 거리를 보장하는지, 거리와 부모를 어떻게 기록해 경로를 되짚는지, 그리고 칸마다 비용이 달라지면 왜 무너지는지.
한 갈래를 끝까지 가 보고 막히면 되돌아온다
깊이 우선 탐색이 실제로 어떻게 도는지 봅니다. 재귀와 스택이 왜 같은 코드인지, 방문 표시를 어디서 찍어야 하는지, 그리고 던전 연결 검사와 미로 생성에서 이 순서가 왜 필요한지.
1,000마리에서 멀쩡하던 코드가 10,000마리에서 죽는다
초를 재는 대신 입력이 커질 때 연산이 몇 번으로 늘어나는지를 셉니다. Big-O 를 읽는 법, 최악과 평균이 갈리는 자리, 그리고 기울기가 좋은 쪽이 지는 구간까지.
타일맵도 스킬 트리도 결국 같은 모양이다
점과 선으로 보면 길찾기, 스킬 선행 조건, 던전 방 연결이 한 문제가 됩니다. 그래프를 인접 행렬과 인접 리스트 중 무엇으로 저장할지, 격자는 왜 저장하지 않아도 되는지 봅니다.
꼭짓점은 양 끝이 아니라 두 점을 비교해서 찾는다
올라갔다 내려오는 곡선의 최고점을 찾는 문제입니다. 크다 작다로는 방향을 알 수 없어서, 가운데 두 점을 견줘 삼분의 일씩 버립니다. 그 전제가 깨지는 자리까지.
한 바퀴 돌아간 배열에서도 반쪽은 정렬돼 있다
링 버퍼처럼 어느 지점에서 끊긴 정렬 배열에서 값을 찾습니다. 가운데를 보면 두 반쪽 중 하나는 반드시 정렬돼 있고, 그 사실 하나로 절반을 버릴 수 있습니다.
배열이 아니라 답을 이분 탐색한다
찾는 대상이 배열의 값이 아니라 설정값일 때도 반으로 자를 수 있습니다. 판정이 단조롭기만 하면 됩니다. 그 전제가 깨지는 자리와 실수 범위를 다루는 법까지.
끝이 어딘지 모르는 배열에서 찾기
길이를 알려주지 않는 정렬된 데이터에서 값을 찾는 지수 탐색(exponential search)입니다. 경계를 두 배씩 넓혀 구간부터 만든 다음 이진 탐색으로 넘기는 방법과, 그 비용이 왜 전체 크기와 무관한지.
찾았는데 멈추면 안 되는 이유
정렬된 배열에 같은 값이 여러 개일 때 첫 자리를 찾는 문제입니다. 일반 이진 탐색이 왜 모자란지, 찾은 뒤 왼쪽으로 훑으면 왜 선형이 되는지, 그리고 한 줄만 바꾸면 그게 어떻게 사라지는지.
반으로 자르면 백만 칸이 스무 번에 끝난다
이진 탐색의 기본형입니다. 구간을 닫힌 것으로 잡을지 열린 것으로 잡을지, 언제 멈출지, 그리고 무한 루프와 오버플로가 나는 자리를 봅니다.