0 . 아침 코딩
과제가 끝난김에 다시 코딩 테스트 준비 겸 내가 필요한 코딩 기술을 생각해보았다
게임에서 필요한알고리즘을 먼저 조금알아보니
A* , 다익스트라, FloodFill, BFS, DFS, State Machine, Perlin Noise, Sorting Algorithms, QuadTree & Octree
언리얼에서 사용하는 자료구조는
TArray, TMap, TSet, Priority Queue( TQueue<T> ), Graph , Linked List( TLinkedList<T>), KD-Tree라고 일단알았는데
대부분 길찾기 알고리즘 에서 사용되는 거나 마지막 kdtree에서는 충돌감지까지 할수있다고한다
유닛 이동은 A*
시야처리는 BFS, DFS , Flood Fill
멀티 유닛 움직임 (집단 이동!!) Boid 알고리즘 , Steering Behaviors
충돌 최적화 Quadtree, Octree
자원 관리 시스템 TMap , Priority Queue
등이 있다고 하니 그래프를 공부한건 다행인것 같다
유닛이동은 언리얼에서 내비메쉬 등이 있으니 당장은 아니고
BFS, DFS는 저번에 다뤘고
Flood Fill을 하려고한다.
Flood Fill이란?
영역을 채우는 알고리즘
왜 배워야 하는가?
ai 경로 탐색 ,
퍼즐 게임에서 특정 블록을 제거할때
물건을 설치할때 공간 찾기(rts게임 )
유닛이 이동 가능한 지역을 탐색할 때,
DFS / BFS 방식으로 구현할 수 있어 다른 알고리즘의 기초
AI, 네비게이션, 지형 생성 등 다양한 게임 시스템과 결합 가능
맵에서 특정 지형이나 영역을 구분할 때
언리얼에서는 Navmesh 와 AIPerception이 있는데 왜 이걸 배워야 하는가?
유닛이 이동할 수 있는 영역을 찾거나 표시하기 위해
( AI 유닛의 이동 가능 영역을 정의하고 시각화하는 데 유용)
NavMesh가 AI의 이동 경로를 결정할 때, Flood Fill은 맵의 특정 영역을 탐색하거나 채울 때 더 세밀하게
조작 가능
( NavMesh가 커버하지 못한 작은 구역이나 세부적인 경로 탐색에서 활용됩니다.)
(사실 이 작은 구역때문에 저번 프로젝트에서 좁은 복도와 계단을 이용하지 않았었다.)
맵 상에서 특정 영역을 시각적으로 표시하는 데 유용
Fog of War 시스템에서 탐험하지 않은 지역을 숨기거나, 유닛이 이동할 수 있는 지역을 표시할 때 사용
(이렇게 되면 NavMesh에서 막아놓은 공간을 나중에 치우는 것보다 더 편하지않을까)
맵에서 특정 조건을 만족하는 영역을 채우는 기능을 구현
(이거는 이제 건설 기능 있는 게임에서 필요할 것 같다고 생각된다.)
실시간 AI 시스템에 응용
ai 가 적의 이동 범위나 시야 범위를 탐색하거나 , 다양한 전투 시스템에서 유용하게 사용될 수 있음.
(ai가 벽뒤로 숨는 패턴이면 벽의 영역을 찾는데 활용하거나 적의 공격 범위를 분석해서 피하는 기능을 넣을 수
있을 것 같다.)
#pragma once
#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "FloodFill.generated.h"
UCLASS()
class TESTPROJECT_API AFloodFill : public AActor
{
GENERATED_BODY()
public:
// Sets default values for this actor's properties
AFloodFill();
protected:
// Called when the game starts or when spawned
virtual void BeginPlay() override;
private:
int32 GridWidth = 10; // 맵 가로 크기
int32 GridHeight = 10; // 맵 세로 크기
TArray<TArray<int32>> Grid; // 2D 맵 데이터 ( 2차원 배열)
void FloodFill(int32 X, int32 Y, int32 TargetValue, int32 ReplaceValue);
};헤더 파일
#include "FloodFill.h"
// Sets default values
AFloodFill::AFloodFill()
{
// Set this actor to call Tick() every frame. You can turn this off to improve performance if you don't need it.
PrimaryActorTick.bCanEverTick = false;
}
// Called when the game starts or when spawned
void AFloodFill::BeginPlay()
{
Super::BeginPlay();
//맵 크기 설정
Grid.SetNum(GridHeight); // 세로
for (int32 i = 0; i < GridHeight; i++)
{
Grid[i].SetNum(GridWidth); // 가로
}
// 초기 맵 데이터 설정 (0 = 빈 공간 , 1 = 벽)
for (int32 i = 0; i < GridHeight; i++)
{
for (int32 j = 0; j < GridWidth; j++)
{
Grid[i][j] = (FMath::RandBool()) ? 1 : 0; // 랜덤으로 벽 생성
//이럴경우 완전 막힌 공간도 있지않을까 싶음
}
}
// 특정 좌표에서 Flood Fill 실행 ( 5,5에서 시작)
FloodFill(5, 5, 0, 2);
for (int32 i = 0; i < GridHeight; i++)
{
FString Line;
for (int32 j = 0; j < GridWidth; j++)
{
Line += FString::Printf(TEXT("%d "), Grid[i][j]);
}
UE_LOG(LogTemp, Warning, TEXT("%s"), *Line);
}
}
void AFloodFill::FloodFill(int32 X, int32 Y, int32 TargetValue, int32 ReplaceValue)
{
// 범위를 벗어나면 종료
if (X < 0 || X >= GridWidth || Y < 0 || Y >= GridHeight) return;
//이미 방문 했거나 다른 값이면 종료
if (Grid[Y][X] != TargetValue) return;
//현재 위치를 새로운 값으로 변경
Grid[Y][X] = ReplaceValue;
// 4방향탐색 (좌, 우 , 위, 아래)
FloodFill(X - 1, Y, TargetValue, ReplaceValue);
FloodFill(X + 1, Y, TargetValue, ReplaceValue);
FloodFill(X, Y - 1, TargetValue, ReplaceValue);
FloodFill(X, Y + 1, TargetValue, ReplaceValue);
}소스 파일
| LogTemp: Warning: 0 1 0 1 0 0 0 0 0 0 LogTemp: Warning: 1 0 1 0 0 1 0 1 1 0 LogTemp: Warning: 1 0 0 1 1 0 1 1 1 0 LogTemp: Warning: 1 1 0 1 0 1 2 2 1 0 LogTemp: Warning: 0 1 0 1 1 1 1 2 1 0 LogTemp: Warning: 1 0 0 1 2 2 2 2 1 0 LogTemp: Warning: 0 0 0 0 1 1 2 1 1 1 LogTemp: Warning: 1 0 1 0 1 1 2 1 1 1 LogTemp: Warning: 0 1 0 0 0 0 1 0 1 1 LogTemp: Warning: 1 0 1 0 1 0 0 0 1 1 |
출력
2차원 배열을 언리얼 에서 사용한건 처음이지만
gpt의 도움을 받아서 그대로 따라 적은것이지만
분석해보면
1. 맵을 랜덤으로
0과 1로 나누기 (0은 이동 가능 , 1은 이동 불가능)
2. FloodFill DFS방식으로 위치값을 받은다음 현재 위치에서 0을 이동 가능한 범위 2로 인식하기
(2로 채우기 = 탐색한다)
NavMesh에서 녹색범위로 지나갈수 있는걸 확인하는거와 이방법은 신기했었다.
언리얼에서는 어떻게 사용될까
언리얼의 경우 3d 공간이기 때문에 3d 공간에 맞게 변형해야 한다.
맵을 스캔하고 오브젝트가 있는지 여부를 확인하여 해당 영역을 1 (못지나가는 영역)으로표시하고
오닛이 이동가능한영역을 표시한다.
1. 맵 스캔 ( 3d 공간 에서 타일화 )
맵을 3d 공간으로 분할할 때 , 격자 형태로 나누는 방식이 일반적
3d 그리드로 맵을 나누고 각 그리드 셀에 대한 정보 저장 , 셀에 대한 크기는 유닛크기나
맵의 필요에 따라 조정
(이부분은 실제로 확인하지않으면 힘들 것 같다.
2. 오브젝트 탐지 (맵에서 장애물 확인)
스캔을 통해 맵의 각 셀을 탐색하고 오브젝트 있는지 확인
오브젝트가 있다면 그위치를 1로 표시 좁은 경로를 처리가능!!
3. Flood Fill
주변에 빈공간 0에서 시작하여 주변에 빈공간을 이동가능한 영역인 2로 채운다.
벽을 만났을 때 더이상 채우지 않도록 한다.
유닛이 이동할 수 있는 영역만 표시
4. 오브젝트 크기와 Flood Fill
오브젝트가 3d 공간에서차지하는 크기가 Flood Fill에 영향을 미칠 수 있음.
오브젝트가 크다면, 해당 오브젝트 주변은 더 넓은 범위로 채우기
2의 크기는 유닛이 이동 가능한 영역을 나타내는데,
만약 유닛 크기가 2칸이라면, Flood Fill이 채우는 영역도
유닛이 해당 크기만큼 이동할 수 있도록 2칸으로 확장
예시 : 3D Flood Fill
3차원 배열로 만들고 drawbox도 추가해주었다
공간 곧곧에 비어있는 공간이 보인다.
// Fill out your copyright notice in the Description page of Project Settings.
#include "FloodFill.h"
// Sets default values
AFloodFill::AFloodFill()
{
// Set this actor to call Tick() every frame. You can turn this off to improve performance if you don't need it.
PrimaryActorTick.bCanEverTick = true;
}
// Called when the game starts or when spawned
void AFloodFill::BeginPlay()
{
Super::BeginPlay();
//맵 크기 설정
Grid.SetNum(GridHeight); // 세로
for (int32 i = 0; i < GridHeight; i++)
{
Grid[i].SetNum(GridWidth); // 가로
}
// 초기 맵 데이터 설정 (0 = 빈 공간 , 1 = 벽)
for (int32 i = 0; i < GridHeight; i++)
{
for (int32 j = 0; j < GridWidth; j++)
{
Grid[i][j] = (FMath::RandBool()) ? 1 : 0; // 랜덤으로 벽 생성
//이럴경우 완전 막힌 공간도 있지않을까 싶음
}
}
// 특정 좌표에서 Flood Fill 실행 ( 5,5에서 시작)
FloodFill(5, 5, 0, 2);
for (int32 i = 0; i < GridHeight; i++)
{
FString Line;
for (int32 j = 0; j < GridWidth; j++)
{
Line += FString::Printf(TEXT("%d "), Grid[i][j]);
}
UE_LOG(LogTemp, Warning, TEXT("%s"), *Line);
}
Grids.SetNum(GridDepth);
for (int32 i = 0; i < GridDepth; i++)
{
Grids[i].SetNum(GridHeight); // 높이 설정
for (int32 j = 0; j < GridHeight; j++)
{
Grids[i][j].SetNum(GridWidth); // 너비 설정
}
}
for (int32 i = 0; i < GridDepth; i++)
{
for (int32 j = 0; j < GridHeight; j++)
{
for (int32 k = 0; k < GridWidth; k++)
{
Grids[i][j][k] = (FMath::RandBool()) ? 1 : 0; // 랜덤으로 벽 생성
//이럴경우 완전 막힌 공간도 있지않을까 싶음
}
}
}
FloodFill3D(5, 5, 5, 0, 2);
}
void AFloodFill::FloodFill(int32 X, int32 Y, int32 TargetValue, int32 ReplaceValue)
{
// 범위를 벗어나면 종료
if (X < 0 || X >= GridWidth || Y < 0 || Y >= GridHeight) return;
//이미 방문 했거나 다른 값이면 종료
if (Grid[Y][X] != TargetValue) return;
//현재 위치를 새로운 값으로 변경
Grid[Y][X] = ReplaceValue;
// 4방향탐색 (좌, 우 , 위, 아래)
FloodFill(X - 1, Y, TargetValue, ReplaceValue);
FloodFill(X + 1, Y, TargetValue, ReplaceValue);
FloodFill(X, Y - 1, TargetValue, ReplaceValue);
FloodFill(X, Y + 1, TargetValue, ReplaceValue);
}
void AFloodFill::FloodFill3D(int32 X, int32 Y, int32 Z, int32 TargetValue, int32 ReplaceValue)
{
if (X < 0 || X >= GridWidth ||
Y < 0 || Y >= GridHeight ||
Z < 0 || Z >= GridDepth)
{
return;
}
if (Grids[Z][Y][X] != TargetValue) return;
Grids[Z][Y][X] = ReplaceValue;
//100 인 이유 100.0f 가 1m
float CellSize = 100.0f;
FVector BoxCenter(X * 100.0f, Y * 100.0f, Z * 100.0f);
FVector BoxExtent(CellSize / 2, CellSize / 2, CellSize / 2);
FColor BoxColor = FColor::Green; // 시각화 색상
// DrawDebugBox로 3D 박스 그리기
DrawDebugBox(GetWorld(), BoxCenter, BoxExtent, FQuat::Identity, BoxColor, true, -1, 0, 10);
FloodFill3D(X - 1, Y,Z, TargetValue, ReplaceValue);
FloodFill3D(X + 1, Y, Z, TargetValue, ReplaceValue);
FloodFill3D(X, Y - 1, Z, TargetValue, ReplaceValue);
FloodFill3D(X, Y + 1, Z, TargetValue, ReplaceValue);
FloodFill3D(X, Y , Z - 1, TargetValue, ReplaceValue);
FloodFill3D(X, Y, Z + 1, TargetValue, ReplaceValue);
}0인 경우 해당 위치에 박스를 생성 , 1이나 2일경우 패스
그러면 빈공간은 벽이라고 봐야할듯 하다.