격자
글 8개
빈 곳은 큰 칸 하나로 남긴다
밀도가 고르지 않으면 칸 크기를 하나로 정할 수 없습니다. 붐비는 칸만 넷으로 쪼개는 쿼드트리(quadtree)의 동작과, 격자보다 나은 자리와 나쁜 자리를 실측으로 갈라 봅니다.
좌표를 칸으로, 칸을 배열로
균일 격자를 실제로 만들 때 막히는 자리들입니다. 음수 좌표에서 칸 번호가 어긋나는 이유, 맵 밖을 다루는 공간 해시(spatial hash), 같은 쌍을 두 번 보지 않는 법, 칸마다 리스트를 두지 않고 배열 세 개로 짓는 법.
내비메시는 바닥이 아니라 설 수 있는 자리다
유니티가 내비메시를 구울 때 실제로 하는 일과, 런타임에 NavMeshAgent 가 하는 일입니다. 보켈로 덮고 반지름만큼 물러나는 과정, 폴리곤 통로와 코너, 카빙과 링크가 치르는 값.
지도 한 장을 모두가 읽는다
유닛 수백 마리가 같은 곳으로 갈 때 각자 길을 찾는 대신, 목표에서 거꾸로 채운 지도를 한 장 만들어 모두가 읽는 방법입니다. 흐름 필드(Flow Field)의 세 겹 구조와 손익분기점, 목표가 바뀔 때 치르는 값.
건너뛰어도 되는 칸은 건너뛴다
균일한 격자에서는 같은 비용의 길이 수십 개라서 탐색이 그만큼 넓어집니다. 그중 하나만 보게 만드는 점프 포인트 서치(JPS, Jump Point Search)의 규칙과, 이 방법이 통하지 않는 자리.
남은 거리를 짐작하면 덜 헤맨다
목표가 하나일 때 탐색을 그쪽으로 기울이는 A 스타(A*) 알고리즘입니다. 휴리스틱이 지켜야 하는 조건, 과대평가하면 무엇이 깨지는지, 격자에서 무엇을 쓰고 동점은 어떻게 처리하는지.
채우기는 어디서 멈출지를 색으로 정한다
매치3의 같은 색 묶기, 페인트 통, 지뢰찾기의 빈 칸 열기가 전부 플러드 필(flood fill) 하나입니다. 이웃을 색으로 정하는 탐색이 어디서 터지고, 네 방향과 여덟 방향이 무엇을 바꾸는지 봅니다.
전부 검사하지 않으려면 미리 나눠 둔다
적 500마리가 서로 부딪혔는지 보려면 12만 번을 비교해야 합니다. 공간을 칸으로 나눠 두면 같은 칸과 이웃 칸만 보면 됩니다.