개요
https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.
06- Smooth weight 영상을 보고 정리하는 글이다.
요약을 하자면 각 노드의 weight( 변수로는 movePenalty로 선언함 ) 값들을
주위 노드의 weight 값들과 합산 후 평균을 내서 weight를 좀 세세히 설정한다.
이전 파트에서 구현한 알고리즘으로는 최단경로가 도로의 가장자리만 따라 갔다.
위처럼 가중치값들을 변경하면 도로의 가장자리쪽은 도로 바깥과 연산이 되어서 도로 내부 보다
weight가 높게 설정된다.
따라서 보다 더 안쪽으로 경로가 탐색된다.
Box Blur Algorithm
이번 영상에서 핵심이 되는 알고리즘으로, 그리드에서 노드들을 주위 노드들과 연산 후, 평균 처리해서 저장하는 방식이다.
원래는 이미지를 blur처리하는 알고리즘이지만, 여기선 가중치를 이용해 비슷하게 연산한다.
각 노드의 가중치를 구한 후 각 노드의 가중치를 위 알고리즘 방식으로 다시 연산한다.
방식은 간단하다. 노드 주위 1칸만큼 blur처리를 하려고 해보자.
해당 노드 주위 8개의 노드와 자신 노드까지 총 9개의 노드의 가중치를 다 더한 후,
9로 나눠 평균치를 맞춘다.
하지만 각 노드마다 9개의 노드를 연산하는건 비효율적이다.
따라서 가로 노드들을 먼저 3개씩 계산하고 그리드에 저장한다.
가로 노드들만 계산한 값이 저장된 그리드에서 이제 세로로 3개씩 계산하고 평균을 낸다.
노드들을 3개씩 계산할때도 효율적인 방식이 있다.
노드가 1,2,3,4,5번 노드가 연달아 있을 때, 위에 적은 방식대로 하면
1번노드에 1번,1번,2번노드의 평균,
2번노드에 1,2,3번 노드 평균,
3번 노드에 2,3,4,번 노드 평균
4번 노드에 3,4,5번 노드 평균 이런 식으로 계산이 된다.
여기서 규칙을 볼 수 있는데
바로 n번 노드의 평균값은는 n-1번 노드의 평균값 - n-2번 노드가중치 + n+1번 가중치이다.
따라서 이 식을 가지고 계산하면 연산이 줄어든다.
Agrid클래스
이번 영상에서는 grid클래스만 변경이 되었다.
BlurPenaltyMap함수
private void BlurPenaltyMap(int blurSize)
{
//각 blur노드하나에 생기는 커널. 중심에 정사각형 하나 포함되서 odd여야한다.
int kernelSize = 2 * blurSize + 1;
//kernel이 blur노드하나보다 늘어나는 사이즈
int kernelExtents= (kernelSize-1)/2;
int[,] penaltiesHorizontalPass = new int[gridXCnt, gridYCnt];
int[,] penaltiesVerticalPass = new int[gridXCnt, gridYCnt];
//원래는 각 노드에 주위 8개 노드의 penalty값을 다 더해서 blur을 만듬.
//8개 노드 구하기보단 처음에 horizontal의 3개씩 더해서 수평값만 다 더한 blur값을 구하고,
//해당 값들을 수직으로 더하는 식으로 수평+수직 값을 연산해 계산을 줄임.
for(int y = 0; y < gridYCnt; y++)
{
for(int x= -kernelExtents; x <= kernelExtents; x++)
{
int sampleX = Mathf.Clamp(x, 0, kernelExtents);
penaltiesHorizontalPass[0, y] += grid[sampleX, y].movePenalty;
}
for(int x = 1; x < gridXCnt; x++)
{
int removeIdx = Mathf.Clamp(x - kernelExtents - 1, 0, gridXCnt);
int addIdx = Mathf.Clamp(x + kernelExtents, 0, gridXCnt - 1);
penaltiesHorizontalPass[x, y] = penaltiesHorizontalPass[x - 1, y] - grid[removeIdx, y].movePenalty + grid[addIdx, y].movePenalty;
}
}
for(int x = 0; x < gridXCnt; x++)
{
for(int y= -kernelExtents; y <= kernelExtents; y++)
{
int sampleY = Mathf.Clamp(y, 0, kernelExtents);
penaltiesVerticalPass[x, 0] += penaltiesHorizontalPass[x,sampleY];
}
int blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, 0] / (kernelSize * kernelSize));
grid[x, 0].movePenalty = blurredPenalty;
for (int y = 1; y < gridYCnt; y++)
{
int removeIdx = Mathf.Clamp(y - kernelExtents - 1, 0, gridYCnt);
int addIdx = Mathf.Clamp(y + kernelExtents, 0, gridYCnt - 1);
penaltiesVerticalPass[x, y] = penaltiesVerticalPass[x, y-1] - penaltiesHorizontalPass[x,removeIdx] + penaltiesHorizontalPass[x,addIdx];
blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, y] / (kernelSize * kernelSize));
grid[x, y].movePenalty = blurredPenalty;
if (blurredPenalty > penaltyMax)
{
penaltyMax = blurredPenalty;
}
if (blurredPenalty < penaltyMin)
{
penaltyMin = blurredPenalty;
}
}
}
}한줄 한줄 설명해보자면,
kernelsize는 평균 낼 직사각형의 길이를 의미한다.
예를들어 blurSize가 3으로 들어왔다고 하자.
각 노드 한개를 평균내려면 2*3+1 총 7개의 노드를 평균내야한다.
평균낼 때 사용될 7개 노드들은 왼쪽으로 3개, 오른쪽 3개, 자기자신이다.
kernelExtents는 평균 낼 직사각형 길이에서 자신노드를 제외한 길이의 절반이다.
(위의 예시로 kernelExtents를 구하면 평균 낼 직사각형 길이(KernelSize)는 7이다.
자기 자신노드 1개 빼준 후 나누기 2를 해서 kernelExtents는 3이 나온다.)
blurSize와 같은 값이다.
배열을 두개 선언해줬다.
int[,] penaltiesHorizontalPass
int[,] penaltiesVerticalPass 위에서 말했듯, 수평으로 먼저 평균을 낸 값들을 penaltiesHorizontalPass배열에,
해당 평균값을 가지고 수직으로 평균을 낸 값들을 penaltiesVerticalPass배열에 저장한다.
for(int y = 0; y < gridYCnt; y++)
{
for(int x= -kernelExtents; x <= kernelExtents; x++)
{
int sampleX = Mathf.Clamp(x, 0, kernelExtents);
penaltiesHorizontalPass[0, y] += grid[sampleX, y].movePenalty;
}
for(int x = 1; x < gridXCnt; x++)
{
int removeIdx = Mathf.Clamp(x - kernelExtents - 1, 0, gridXCnt);
int addIdx = Mathf.Clamp(x + kernelExtents, 0, gridXCnt - 1);
penaltiesHorizontalPass[x, y] = penaltiesHorizontalPass[x - 1, y] - grid[removeIdx, y].movePenalty + grid[addIdx, y].movePenalty;
}
}먼저 y행의 첫번째 x열값을 구해준다. x값은 -kernelExtents부터 kernelExtents값까지 가진다.
하지만 배열에 음수인덱스는 없으므로 음수인덱스일 때는 Mathf.Clamp함수를 통해 0으로 계산한다.
간단히 kernelExtents를 1이라고 하고 구해보자.
grid [0,y] weight + grid [0,y] weight + grid[1, y] weight값이 penaltiesHorizontalPass[ 0 , y ] 값이다.
penaltiesHorizontalPass[0 , y]을 구한 후로는,
n번 노드의 평균값은는 n-1번 노드의 평균값 - n-2번 노드가중치 + n+1번 가중치 식을 이용해서 채워나간다.
for(int x = 0; x < gridXCnt; x++)
{
for(int y= -kernelExtents; y <= kernelExtents; y++)
{
int sampleY = Mathf.Clamp(y, 0, kernelExtents);
penaltiesVerticalPass[x, 0] += penaltiesHorizontalPass[x,sampleY];
}
}
수직 값들을 구하는 방식과와 수평값을 구하는 방식이 유사하다.
차이점은 이제 수평값들의 합을 저장한 penaltiesHorizontalPass배열이 존재하므로
해당 배열의 값을 가지고 계산하면 된다.
kernelExtents가 1이라고 해보자.
첫번째 열 값을 구할때 , penaltiesVerticalPass[ x, 0 ] 값에는
penaltiesHorizontalPass[x,0]+penaltiesHorizontalPass[x,0]+penaltiesHorizontalPass[x,1] 값이 들어간다.
그 후, 아래 반복문을 보면
for (int y = 1; y < gridYCnt; y++)
{
int removeIdx = Mathf.Clamp(y - kernelExtents - 1, 0, gridYCnt);
int addIdx = Mathf.Clamp(y + kernelExtents, 0, gridYCnt - 1);
penaltiesVerticalPass[x, y] = penaltiesVerticalPass[x, y-1] - penaltiesHorizontalPass[x,removeIdx] + penaltiesHorizontalPass[x,addIdx];
blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, y] / (kernelSize * kernelSize));
grid[x, y].movePenalty = blurredPenalty;
if (blurredPenalty > penaltyMax)
{
penaltyMax = blurredPenalty;
}
if (blurredPenalty < penaltyMin)
{
penaltyMin = blurredPenalty;
}
}수평값을 구할때 와 똑같은 방식으로 평균값을 구한다. 대신 weight값들을 grid에서 가져오는것이 아닌
penaltiesHorizontalPass에서 가져온다.
값을 구하고, 아직 더하기만 했지 평균을 안 구한 상태이므로 (kernelsize*kernelSize)값으로 나눠준다.
나눠준 값을 blurredPenalty변수에 저장후 grid[x,y]값을 갱신해준다.
뒤에 OnDrawGizmos함수에서 Lerp함수에 사용하기위해 penaltyMax, penaltyMin 값을 갱신하며 구해준다.
반복문 y가 1부터 시작하는 특성상 grid[x,0]은 갱신이 안 된다.
따라서 이 반복문 윗줄에 따로 적어서 y가 0일때를 갱신해줘야한다.
int blurredPenalty = Mathf.RoundToInt((float)penaltiesVerticalPass[x, 0] / (kernelSize * kernelSize));
grid[x, 0].movePenalty = blurredPenalty;CreateGrid함수
private void CreateGrid()
{
for (int i = 0; i < gridXCnt; i++)
{
for (int j = 0; j < gridYCnt; j++)
{
Vector3 worldPoint = worldBottomLeft + (i * nodeDiameter + nodeRadius) * Vector3.right + (j * nodeDiameter + nodeRadius) * Vector3.forward;
bool walkable = !Physics.CheckSphere(worldPoint, nodeRadius, UnWalkableLayer);
int movePenalty = 0;
Ray ray = new Ray(worldPoint + Vector3.up * 50, Vector3.down);
RaycastHit hit;
if (Physics.Raycast(ray, out hit, 100, walkableMask))
{
walkableRegionsDictionary.TryGetValue(hit.collider.gameObject.layer, out movePenalty);
}
if (!walkable)
{
movePenalty += obstacleProximityPenalty;
}
grid[i, j] = new Node(walkable, worldPoint, i, j, movePenalty);
}
}
BlurPenaltyMap(3);
}걸어다닐수 없는 노드라면 movePenalty를 따로 선언한 obstacleProximityPenalty만큼 추가했다.
현재 걸어다닐 수 없는 노드들은 UnWalkable레이어만 추가해주고 한게 없어서 movePenalty가 0이다.
따라서 실행해보면 장애물 주위 노드들은 movepenalty평균값이 작게 나온다.
그래서 선언한 obstacleProximityPenalty를 추가해줬다.
함수 마지막 부분에 BlurPenaltyMap함수를 실행하고 blurSize는 3을 넣어줬다.
OnDrawGizmos함수
private void OnDrawGizmos()
{
Gizmos.DrawWireCube(transform.position, new Vector3(gridWorldSize.x, 1, gridWorldSize.y));
if (grid != null && displayGridGizmos)
{
foreach (Node n in grid)
{
Gizmos.color = Color.Lerp(Color.white, Color.black, Mathf.InverseLerp(penaltyMin, penaltyMax, n.movePenalty));
Gizmos.color = (n.walkable) ? Gizmos.color : Color.red;
Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter));
}
}
}바뀐 부분은 이제 도로에서 가중치에 의해 바뀌는 수치를 시각화하는 부분이다.
우선 InverseLerp함수를 통해 위 BlurPenaltyMap함수에서 구한 penaltyMin, penaltyMax범위에서 노드의 weight값을 0~1사이값으로 구한다.
penaltyMax에 가까울수록 1에 근접하게 나오고 min에 가까울수록 0에 근접하게 나온다.
해당 수치를 가지고 Color.Lerp함수에 넣으면 penaltyMin쪽에 가까울수록 White에 근접해지고,
penaltyMax쪽에 가까울수록 black으로 계산이 된다.
실행 예
도로의 가장자리에 그라데이션이 생겼다. 도로의 가장자리쪽 weight가 잘 분산된 것을 볼수 있다,
도로 내부의 하얀색 노드쪽으로만 경로가 설정되어 가장자리로만 가던 현상이 줄었다.
Obstacle에 가중치를 주위보다 많이 설정해서 obstacle들의 주위는 훨씬 검정색이다.
레퍼런스
