알고리즘 라이브 세션-이진탐색

돌아보기

• 재귀: 자기 자신 호출
• 콜 스택: 재귀 호출마다 스택 프레임 쌓이고, base case부터 다시 빠진다

순차 탐색 - 처음부터 하나씩

• 정렬되지 않는 배열에서 값을 찾으려면? 시간복잡도 O(n)
• 처음부터 끝까지 찾기.
• 사실 정렬되어 있어도? 순차 탐색 하면 시간복잡도 O(n)

이진 탐색의 원리

• 정렬된 배열의 가운데 (mid) 보고 찾는 값이 mid보다 크면 오른쪽만, 작으면 왼쪽 절반만
• 이걸 반복
• 시간복잡도 O(log n) - 정렬에 한번 시간 투자하고 나중에 검색 시간 단축

분할 정복 + 재귀

• 분할: 배열을 mid 기준으로 절반.
• 정복: 한쪽 절반 탐색
• 다시 올라와서 값 반환
• 병합 정렬과이 차이: 병합정렬은 양쪽 모두를 처리(정렬해야하므로). 이진탐색은 한쪽씩만
  • O (n log n) vs O(log n)
• 재귀 깊이 vs 스택 오버플로우 - log n 만큼의 깊이이므로 스택 오버플로우 가능성 거의 없다

upper_bound/ lower_bound

• x 이상인 첫 번째 위치, x 초과인 첫 번째 위치 를 각각 찾아서
• 특정 숫자가 여러개 있을 때도 조회 가능
• 값 개수, 범위 내 원소 수 찾을 때 유용

위험 - 정수 오버플로우

• mid = (left + right) / 2: 위험
• left + (right - left) / 2; 로 쓰기

키워드

ApplyRadialDamage TakeDamage DamagePreventionChannel ECC_Visibility ECC_MAX VoxelChunkActor VoxelWorld ProceduralMeshComponent RadialDamage

오늘 한 일

팀 프로젝트 One, Two... Shoot!에서 포탄 폭발이 복셀 지형에 닿았을 때, 지형 파괴와 Actor 데미지를 어떤 구조로 처리할지 정리했다.

처음에는 ApplyRadialDamage가 VoxelChunkActor에 닿는 것을 인식하면 충분하다고 생각했다. 실제로 AVoxelChunkActor::TakeDamage()를 override하면 radial damage event를 받을 수 있다.

float AVoxelChunkActor::TakeDamage(
	float DamageAmount,
	FDamageEvent const& DamageEvent,
	AController* EventInstigator,
	AActor* DamageCauser
)
{
	if (DamageEvent.IsOfType(FRadialDamageEvent::ClassID))
	{
		const FRadialDamageEvent& RadialDamageEvent =
			static_cast<const FRadialDamageEvent&>(DamageEvent);

		const FVector ExplosionOrigin = RadialDamageEvent.Origin;
		const float ExplosionRadius = RadialDamageEvent.Params.OuterRadius;
	}

	return Super::TakeDamage(DamageAmount, DamageEvent, EventInstigator, DamageCauser);
}

하지만 실제로 생각해보니 단순히 VoxelChunkActor에서 바로 파괴하는 구조는 문제가 있었다.

폭발은 한 청크에서 발생해도 옆 청크까지 영향을 줘야 한다. 그런데 VoxelChunkActor는 자기 청크의 복셀 배열만 알고 있다. 옆 청크까지 처리하려면 여러 청크를 알고 있는 VoxelWorld가 필요하다.

그래서 현재 방향은 다음과 같이 정리했다.

1. 포탄이 폭발한다.
2. ApplyRadialDamageWithFalloff를 호출한다.
3. VoxelChunkActor::TakeDamage()가 폭발 신호를 받는다.
4. VoxelChunkActor는 직접 파괴하지 않고 VoxelWorld에 폭발 위치와 반경을 전달한다.
5. VoxelWorld가 전체 청크를 대상으로 실제 파괴를 처리한다.

기억해야 할 것

ApplyRadialDamage는 단순한 반경 알림이 아니다

처음에는 ApplyRadialDamageWithFalloff를 반경 안 Actor에게 전부 damage event를 보내는 함수처럼 생각했다.

하지만 실제로는 DamagePreventionChannel의 영향을 받는다. 기본적으로 폭발 지점과 대상 사이에 trace를 쏴서, 중간에 막는 물체가 있으면 데미지가 차단될 수 있다.

이때 ECC_Visibility를 쓰면 복셀 벽 뒤에 있는 플레이어나 적이 데미지를 받지 않는다. 이것은 원하는 동작이다.

UGameplayStatics::ApplyRadialDamageWithFalloff(
	this,
	ProjectileDamage,
	10.0f,
	Hit.ImpactPoint,
	FinalRadius,
	FinalRadius,
	1.0f,
	nullptr,
	TArray<AActor*>(),
	this,
	GetInstigatorController(),
	ECC_Visibility
);

문제는 VoxelChunkActor도 이 trace의 영향을 받는다는 점이다. 폭발이 한 청크에서 터졌을 때, 옆 청크가 반경 안에 있어도 앞 청크의 collision 때문에 damage event를 못 받을 수 있다.

ECC_MAX는 쉬운 해결책처럼 보이지만 최종 답은 아니다

한때 ECC_MAX를 사용해 damage prevention trace를 사실상 끄는 방법도 생각했다.

UGameplayStatics::ApplyRadialDamageWithFalloff(
	this,
	ProjectileDamage,
	10.0f,
	Hit.ImpactPoint,
	FinalRadius,
	FinalRadius,
	1.0f,
	nullptr,
	TArray<AActor*>(),
	this,
	GetInstigatorController(),
	ECC_MAX
);

이렇게 하면 옆 청크까지 damage event가 잘 전달된다.

하지만 이 방식은 복셀 벽 뒤에 있는 플레이어나 적도 데미지를 받을 수 있다. 포탄이 벽 너머의 Actor에게 데미지를 주면 안 되는 상황에서는 맞지 않는다.

결국 ECC_MAX는 지형 파괴 테스트에는 편하지만, Actor 데미지 규칙까지 생각하면 최종 구조로 쓰기 어렵다.

VoxelChunkActor는 파괴 계산의 주체가 아니라 entry point에 가깝다

VoxelChunkActor가 TakeDamage()를 받는 것은 좋다. Unreal의 damage system 흐름에 자연스럽게 들어가기 때문이다.

하지만 VoxelChunkActor가 직접 모든 파괴를 계산하면 옆 청크를 처리하기 어렵다.

현재 구조에서 VoxelWorld는 이미 여러 청크를 알고 있다.

void AVoxelWorld::DestroyVoxelsAtWorldLocation(FVector WorldLocation, float Radius)
{
	for (AVoxelChunkActor* Chunk : Chunks)
	{
		if (IsValid(Chunk))
		{
			Chunk->DestroyVoxelsAtWorldLocation(WorldLocation, Radius);
		}
	}
}

그래서 VoxelChunkActor::TakeDamage()는 폭발 정보를 받는 입구로만 사용하고, 실제 파괴 전파는 VoxelWorld가 처리하는 쪽이 더 자연스럽다.

현재 정리한 흐름은 다음과 같다.

Projectile
→ ApplyRadialDamageWithFalloff(..., ECC_Visibility)
→ VoxelChunkActor::TakeDamage
→ VoxelWorld::DestroyVoxelsAtWorldLocation
→ 각 VoxelChunkActor가 자기 범위 안의 복셀 파괴

너무 빨리 복잡한 차폐 규칙을 넣지 않기

중간에 복셀 타입별 차폐도 생각했다.

예를 들어 다음과 같은 상황이다.

폭발 - Stone - Air - Stone

이 경우 앞쪽 Stone은 파괴되고, 공기 뒤의 Stone은 살아남는 것이 자연스러울 수 있다.

반대로 다음처럼 같은 덩어리라면:

폭발 - Stone - Stone - Stone

전부 같은 solid 덩어리이므로 같이 파괴되는 것이 맞을 수 있다.

이 규칙까지 제대로 처리하려면 단순 반경 파괴가 아니라, VoxelWorld 기준으로 연결된 solid voxel을 탐색하는 방식이 필요하다.

하지만 지금 단계에서 이 로직까지 넣으려 하니 구조가 너무 복잡해졌다.

아직은 다음 흐름이 안정적으로 동작하는지 확인하는 것이 먼저다.

1. 포탄이 복셀 청크에 맞는다.
2. VoxelChunkActor::TakeDamage()가 호출된다.
3. VoxelWorld가 폭발 위치와 반경을 받는다.
4. 옆 청크까지 반경 파괴가 적용된다.
5. 복셀 벽 뒤 Actor는 ECC_Visibility 때문에 데미지를 받지 않는다.

차폐 규칙은 이 흐름이 안정된 뒤에 다시 설계하는 것이 맞다.

오늘의 결론

오늘 가장 크게 정리된 점은 ApplyRadialDamage 하나로 지형 파괴와 Actor 데미지를 모두 해결하려고 하면 구조가 꼬인다는 것이다.

Actor 데미지는 ECC_Visibility를 사용해서 벽에 막히게 처리하는 것이 맞다.

반면 지형 파괴는 VoxelChunkActor 하나가 아니라, 여러 청크를 알고 있는 VoxelWorld가 처리하는 것이 맞다.

지금 단계의 최종 구조는 다음과 같다.

Actor 데미지
→ ApplyRadialDamageWithFalloff + ECC_Visibility

Voxel 파괴
→ VoxelChunkActor::TakeDamage
→ VoxelWorld에 폭발 전달
→ VoxelWorld가 전체 청크에 반경 파괴 적용

오늘 배운 점은 이것이다.

복잡한 예외 상황을 전부 미리 해결하려고 하면, 지금 필요한 구조까지 흐려질 수 있다.

지금은 단순한 구조로 폭발 흐름을 안정화하고, 복셀 타입별 차폐나 연결된 덩어리 판정은 나중에 필요해졌을 때 다시 추가하는 것이 좋다.