그래프와 경로
14편
내비메시는 바닥이 아니라 설 수 있는 자리다
유니티가 내비메시를 구울 때 실제로 하는 일과, 런타임에 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 를 읽는 법, 최악과 평균이 갈리는 자리, 그리고 기울기가 좋은 쪽이 지는 구간까지.
타일맵도 스킬 트리도 결국 같은 모양이다
점과 선으로 보면 길찾기, 스킬 선행 조건, 던전 방 연결이 한 문제가 됩니다. 그래프를 인접 행렬과 인접 리스트 중 무엇으로 저장할지, 격자는 왜 저장하지 않아도 되는지 봅니다.