지난 포스팅에서는 글라이딩과 벽타기가 포함된 3D 길찾기를 구현하기 위해서 생성되는 Voxel에 벽영역인지 땅영역인지에 대한 데이터를 추가하는 방법에 관해서 다뤘습니다. 이번 포스팅에서는 이렇게 추가한 데이터를 기반으로 최적의 경로를 계산하도록 A* 알고리즘을 수정한 과정을 이야기해보도록 하겠습니다.

(목표 이미지)

이용할 수 있는 데이터

위 그림은 현재 Voxel들에 저장된 정보를 시각화한 결과입니다. 자주색은 땅, 파란색은 벽, 초록색은 빈공간을 나타냅니다. 이 정보를 이용해서 A*알고리즘을 수정해보도록 하겠습니다.

Z좌표 상승 예외처리

기존 알고리즘에서는 특정 Voxel의 이웃한 6방향의 Voxel들을 A*알고리즘에서 사용되는 Queue에 Push하는 방식으로 동작했습니다. 하지만, 제가 구현할 알고리즘은 오직 벽을 타는 행위를 통해서만 고도가 상승할 수 있는 구조이기 때문에 다음과 같은 예외처리 코드를 작성했습니다.

if ( NewTreeNode.WorldLocation.Z > CurrentNode.WorldLocation.Z )
{//고도 상승 예외처리
	bool IsPassable = ExtractIsWallFromData(NewTreeNode.TreeUserData);
	if ( !IsPassable )
		continue;
}

위 코드는 새로운 Voxel노드가 Z좌표가 증가하는 노드일때는 다음 노드가 '벽'상태일때만 Queue에 Push하도록 강제합니다.

그 결과 위 사진과 같은 경로를 안내하게 되었습니다.

Z좌표 하강 예외처리

제가 구현할 알고리즘은 자유롭게 하늘을 날아다니는 상황이 아닌 글라이딩과 벽타기를 통한 제한적인 상황임으로 Z좌표가 낮아질때도 예외처리가 필요했습니다. 예를 들어

이런 상황에서 건너편 섬까지 일직선으로 가는 경로는 실제 플레이어가 가게되는 경로가 아닙니다. 대신에, 글라이딩을 통해서 Z좌표가 좀 떨어진 지점에서 건너편 섬의 벽에 붙게 되는 경로를 안내해야 할 것입니다.
저는 이 문제를 해결하기 위해서 A*알고리즘이 계산되는 while루프안에 다음과 같은 코드를 추가했습니다.

if( CurrentNode.GlidingStartLocation.IsNearlyZero() )
{//글라이딩 시작지점 설정
	NewTreeNode.GlidingStartLocation = CurrentNode.WorldLocation;
}
else
{
	NewTreeNode.GlidingStartLocation = CurrentNode.GlidingStartLocation;
}
if ( ExtractIsGroundFromData(NewTreeNode.TreeUserData) || ExtractIsWallFromData(NewTreeNode.TreeUserData) &&
	ExtractIsGroundFromData(CurrentNode.TreeUserData) || ExtractIsWallFromData(CurrentNode.TreeUserData))
{//글라이딩 시작지점 재설정
	NewTreeNode.GlidingStartLocation = NewTreeNode.WorldLocation;
}
if ( NewTreeNode.WorldLocation.Z <= CurrentNode.WorldLocation.Z )
{//고도가 하강할시
	FVector worldPositionToGlidingStart = NewTreeNode.GlidingStartLocation - NewTreeNode.WorldLocation;
	float gradient = FMath::Sqrt(FMath::Pow(worldPositionToGlidingStart.X , 2) + FMath::Pow(worldPositionToGlidingStart.Y , 2))
		/ FMath::Abs(worldPositionToGlidingStart.Z+0.001f);
	if ( gradient > GoalGradient )//gradient: x증분/z증분
		continue;
}

위 코드는 각각의 Voxel에 GlidingStartLocation 이라는 FVector정보를 저장하고 각각의 복셀이 글라이딩을 시작한 위치를 이용해서 기울기조건을 통해서 가능한 경로를 판단하는 계산을 수행합니다.
이 코드를 통해서 Z좌표 변화없이 수평으로 진행하는 경로들을 차단할 수 있었습니다. 다음은 결과 사진입니다.

GoalGradient값에 따라 목표로 하는 기울기 제한값에 따라 경로를 안내하게 됩니다.

A* 평가값 수정

위 그림과 같은 안내가 가능하기 위해서는 '글라이딩을 통해서 날아가는 속도가 땅을 통해 걸어가는 속도보다 빠르다' 라는 정보를 설정할 필요가 있었습니다. 이 정보를 설정하기 위해서 '땅'을 통해서 진행하게 되면 A*알고리즘 평가값이 더 커지도록 하는 방식으로 구현했습니다. 추가로 '벽'을 통해서 진행하면 좀 더 느리게 진행하게 된다는 정보도 설정해줬습니다.

void ACPathVolumeHermes::CalcFitness(CPathAStarNode& Node , FVector TargetLocation , int32 UserData)
{
	check(Node.PreviousNode);

	Node.DistanceSoFar = Node.PreviousNode->DistanceSoFar + FVector::Distance(Node.PreviousNode->WorldLocation, Node.WorldLocation);//현재노드까지 거리누적
	
	
	if (ExtractIsGroundFromData(Node.TreeUserData))
	{
		Node.DistanceSoFar += GroundPenalty;
	}
	if (ExtractIsWallFromData(Node.TreeUserData))
	{
		Node.DistanceSoFar += WallPenalty;
	}
	
	Node.FitnessResult = Node.DistanceSoFar + 3.5f * FVector::Distance(Node.WorldLocation, TargetLocation);//FitnessResult: A*평가값, 낮을수록 우선순위
}

그 결과 목표로 했던 경로안내가 가능하게 되었습니다.

---

이번 포스팅에서는 특수한 상황(글라이딩,벽타기)를 고려해서 A*알고리즘을 수정하는 내용을 다뤘습니다. 다음 포스팅에서는 최적화를 위해서 복셀의 Baking기능을 구현한 내용을 적어보도록 하겠습니다.