[ Unreal Engine 5 / #26 Tile Game TileMatching ]

• 목표
  • 가로 또는 세로로 같은 종류의 타일이 3개 이상 나열되면 해당 타일을 매칭된 것으로 인식하고 삭제한다.
  • 타일이 삭제된 후 위에 있는 타일들이 아래로 내려오며 그리드가 다시 채워진다.
  • 새로운 타일이 빈 공간을 채우는 로직을 구현한다.

• BFS(너비 우선 탐색, Breadth First Search)와 DFS(깊이 우선 탐색, Depth First Search) 를 활용하여 퍼즐 보드를 탐색

• DFS (깊이 우선 탐색)
  • DFS는 탐색할 수 있는 경로를 가능한 깊이까지 우선 탐색하고, 더 이상 탐색할 수 없을 때 이전 노드로 돌아가면서 다른 경로를 찾는 방식입니다. DFS는 재귀적으로 구현될 수 있습니다.
• DFS Pseudocode:
  • 현재 노드를 방문하고 방문했음을 표시합니다.
  • 각 인접한 노드(다음 퍼즐 상태)로 이동하여 그 노드를 방문합니다.
  • 더 이상 이동할 수 없는 경우, 이전 노드로 돌아가며 다른 경로를 탐색합니다.

• BFS ( Breadth-first Search : 너비 우선 탐색 )

  • BFS는 가장 가까운 노드부터 탐색한 후, 그 다음으로 가까운 노드로 점진적으로 탐색을 확장합니다. 큐(Queue)를 사용하여 현재 탐색 중인 노드의 다음 인접한 노드를 차례로 저장하고 탐색하는 방식입니다.

• BFS Pseudocode:

  • 현재 노드를 큐에 추가하고 방문했음을 표시합니다.
  • 큐에서 노드를 하나씩 꺼내어 인접한 노드(다음 퍼즐 상태)를 큐에 추가하고 방문하지 않은 노드를 차례로 방문합니다.
  • 목표 상태를 찾거나 더 이상 방문할 노드가 없을 때까지 반복합니다.

• 비교

  • DFS : 재귀적이고 깊이 우선적으로 탐색을 수행하며,
    하나의 경로를 끝까지 탐색하고 다시 되돌아옵니다.
  • BFS : 큐를 사용하여 너비 우선적으로 탐색하며,
    가까운 노드부터 차례대로 탐색을 수행합니다.

• 언제 DFS, BFS를 선택해야 하는가?

  • 최단 경로를 찾아야 할 때 : BFS는 최단 경로를 보장하므로, 최단 경로 탐색이 필요한 경우 BFS를 선택하는 것이 적합합니다.
  • 메모리 제약이 있는 상황 : 메모리 사용량이 중요한 경우 DFS가 더 적합합니다. DFS는 스택만 사용하여 메모리를 덜 차지합니다.
  • 해답이 깊은 곳에 있을 때 : DFS는 깊이를 우선 탐색하기 때문에, 해답이 깊은 곳에 있을 경우 DFS가 더 효과적입니다.
  • 그래프 순환이 걱정될 때 : BFS는 순환에 안전하기 때문에 순환 구조의 그래프에서 안전하게 탐색할 수 있습니다.

• 재귀 함수의 구조

  • 재귀 함수는 보통 두 가지 요소로 구성됩니다 :
    • 종료 조건(Base Case) : 재귀 호출을 중단하고 결과를 반환하는 조건입니다. 이를 통해 무한 반복을 방지합니다.
    • 재귀 호출(Recursive Call) : 문제를 더 작은 문제로 나누어 자기 자신을 호출하는 부분입니다.

• 스택 오버플로우 주의

  • 재귀 함수는 함수 호출이 스택에 쌓이는 구조이므로, 깊이가 너무 깊어지면 메모리 문제가 발생할 수 있습니다. Unreal Engine 같은 고성능 엔진을 사용할 때도, 성능을 고려해 재귀 호출을 너무 깊게 설계하지 않도록 주의해야 합니다.

• Unreal Engine에서 재귀 함수의 활용

  • 트리 구조 탐색 : Unreal Engine의 Actor나 Component 계층 구조를 순회할 때, 재귀를 통해 하위 노드를 탐색할 수 있습니다.
  • 프랙탈(Fractal) 생성 : 재귀적인 구조를 활용해 자연스러운 절차적 지형이나 패턴을 생성할 때도 사용할 수 있습니다.

• TQueue
  • https://dev.epicgames.com/documentation/en-us/unreal-engine/API/Runtime/Core/Containers/TQueue

Tile Matching

먼저 타일을 순차적으로 탐색하면서 가로 및 세로로 같은 종류의 타일이 3개 이상 연속되었는지 확인합니다. 이를 위해 각각의 타일을 기준 타일로 설정한 후, 해당 타일의 좌우(가로)와 상하(세로)에 있는 타일들이 같은지 검사

• 매칭 확인 함수
  • 우선 타일 매칭 여부를 확인하는 함수를 타일 그리드 클래스에 추가합니다. 타일을 순차적으로 확인하며 가로 및 세로로 3개 이상 매칭된 타일들을 찾아 리스트에 추가

TileGrid.h

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "TileGrid.generated.h"

class ATile;

UCLASS()
class PUZZLESTUDY_API ATileGrid : public AActor
{
	GENERATED_BODY()
	
protected:
	virtual void BeginPlay() override;

public:	
	// Sets default values for this actor's properties
	ATileGrid();

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Tile Grid")
	int32 GridWidth;

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Tile Grid")
	int32 GridHeigh;

	// 타일 간의 배치 간격 ( 기본값 : 100 ) 
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Tile Grid")
	float TileSpacing;

	UPROPERTY()
	TArray<ATile*> TileArray;

	// 타일을 생성할 Blueprint 클래스를 선택할 수 있도록 TSubClassOf 사용
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Tile Grid")
	TSubclassOf<ATile> TileClass; // TileClass는 월드에 배치된 TileGrid에서 설정할 수 있음

	// 그리드 초기화하는 함수
	void InitializeGrid();

	// 특정 타일의 위치를 얻는 함수 
	ATile* GetTile(int32 x, int32 y) const;

	// 특정 타일의 위치를 설정하는 함수
	void SetTile(int32 x, int32 y, ATile* Tile);


	// 바둑판 크기 정의
	const int32 Rows = 4;
	const int32 Colums = 4;

	// TArray 선언
	TArray<int32> GridArray;

	// 바둑판 그리기 함수
	void DrawGrid();

	// 매칭을 확인  Array
	TArray<ATile*> CheckForMatches();

	// swap 함수
	void SwapTiles(ATile* FirstTile, ATile* SecondTile);

	void RemoveMatchingTIles(const TArray<ATile*>& MachingTiles);
	void DropDownTiles();

	bool GetTileGridPosition(ATile* Tile, int32& OutX, int32& OutY) const;

	void RefillGrid();
	FName GenerateRandomTileType();

	void ProcessMatchingLoop();

private:

	TArray<ATile*> CheckHorizontalMatches(int32 StartX, int32 StartY);
	TArray<ATile*> CheckVerticalMatches(int32 StartX, int32 StartY);

};

TileGrid.cpp ( CheckForMatches )

TArray<ATile*> ATileGrid::CheckForMatches()
{
	TArray<ATile*> AllMatchedTile;

	// 가로 매칭 확인
	for (int32 x = 0; x < GridWidth; ++x)
	{
		for (int32 y = 0; y < GridHeigh; ++y)
		{
			ATile* CurrentTile = GetTile(x, y);
			if (!CurrentTile) continue;

			// 가로 매칭된 타일 찾기
			TArray<ATile*> HorizontalMatches = CheckHorizontalMatches(x, y);
			if (HorizontalMatches.Num() >= 3)
			{
				AllMatchedTile.Append(HorizontalMatches);
			}
		}
	}

	// 세로 매칭 확인
	for (int32 x = 0; x < GridWidth; ++x)
	{
		for (int32 y = 0; y < GridHeigh; ++y)
		{
			ATile* CurrentTile = GetTile(x, y);
			if (!CurrentTile) continue;

			// 세로 매칭된 타일 찾기
			TArray<ATile*> VerticalMatches = CheckVerticalMatches(x, y);
			if (VerticalMatches.Num() >= 3)
			{
				AllMatchedTile.Append(VerticalMatches);
			}
		}
	}
	return AllMatchedTile;
}

TileGrid.cpp (CheckHorizontalMatches/CheckVerticalMatches)

TArray<ATile*> ATileGrid::CheckHorizontalMatches(int32 StartX, int32 StartY)
{
	TArray<ATile*> HorizontalMatches; 
	ATile* StartTile = GetTile(StartX, StartY);

	if (!StartTile) return HorizontalMatches;

	HorizontalMatches.Add(StartTile);

	// 오른쪽으로 2칸까지 같은 타일이 있는지 확인
	for (int32 x = StartX + 1; x < GridWidth; ++x)
	{
		ATile* NextTile = GetTile(x, StartY);
		if (NextTile && NextTile->TileType == StartTile->TileType)
		{
			HorizontalMatches.Add(NextTile);
		}
		else
		{
			break;
		}
	}

	return HorizontalMatches;
}

TArray<ATile*> ATileGrid::CheckVerticalMatches(int32 StartX, int32 StartY)
{
	TArray<ATile*> VerticalMatches;
	ATile* StartTile = GetTile(StartX, StartY);

	if (!StartTile) return VerticalMatches;

	VerticalMatches.Add(StartTile);

	// 위쪽으로 2칸까지 같은 타일이 있는지 확인
	for (int32 y = StartY + 1; y < GridHeigh; ++y)
	{
		ATile* NextTile = GetTile(StartX, y);
		if (NextTile && NextTile->TileType == StartTile->TileType)
		{
			VerticalMatches.Add(NextTile);
		}
		else
		{
			break;
		}
	}

	return VerticalMatches;
}

• 이해를 돕고자 개별 함수로 분리 되어 있을뿐, 내용은 비슷하다

TileGrid.cpp ( SwapTiles )

void ATileGrid::SwapTiles(ATile* FirstTile, ATile* SecondTile)
{
	int32 x1, y1, x2, y2;

	if (GetTileGridPosition(FirstTile, x1, y1) && GetTileGridPosition(SecondTile, x2, y2))
	{
		// 타일 배열 업데이트
		SetTile(x1, y1, SecondTile);
		SetTile(x2, y2, FirstTile);

		// 타일의 그리드 좌표도 업데이트
		FVector2D TempPosition = FirstTile->TilePosition;
		FirstTile->TilePosition = SecondTile->TilePosition;
		SecondTile->TilePosition = TempPosition;

		// 타일 위치를 스왑
		FVector TempLocation = FirstTile->GetActorLocation();
		FirstTile->SetActorLocation(SecondTile->GetActorLocation());
		SecondTile->SetActorLocation(TempLocation);
	}
}

TileGrid.cpp ( GetTileGridPosition )

bool ATileGrid::GetTileGridPosition(ATile* Tile, int32& OutX, int32& OutY) const
{
	for (int32 Index = 0; Index < TileArray.Num(); ++Index)
	{
		if (TileArray[Index] == Tile)
		{
			OutX = Index % GridWidth; // X 좌표 계산
			OutY = Index / GridWidth; // Y 좌표 계산
			//OutY = Index / GridHeigh; // 내가 변경한 내용 
			return true;
		}
	}

	// 타일을 찾지 못했을 경우 
	return false;
}

TileGrid.cpp ( RemoveMatchingTIles / DropDownTiles )

void ATileGrid::RemoveMatchingTIles(const TArray<ATile*>& MachingTiles)
{
	for (ATile* Tile : MachingTiles)
	{
		if (Tile)
		{
			int32 X, Y; 
			if (GetTileGridPosition(Tile, X, Y))
			{
				SetTile(X, Y, nullptr);
				
				// 타일을 삭제하기 전에 애니메이션을 적용할 수 있습니다
				// 예시 : Tile->PlayDeletAnimation(); // 0.5초동안 Scale을 0으로 줄이기
				Tile->Destroy();
			}
		}
	}

	/*
	* // 매칭된 타일 수에 따라 점수 추가
	* addScore(NumMatchedTiles * 100 );  // 예시 : 타일 하나당 100점
	*/

	// 빈 공간을 채우기 위해 타일을 아래로 드랍
	DropDownTiles();

	// 이후 매칭 루프 처리
	ProcessMatchingLoop(); // 매칭 루프 시작
}

void ATileGrid::DropDownTiles()
{
	for (int32 x = 0; x < GridWidth; ++x)
	{
		for (int32 y = GridHeigh - 1; y >= 0; --y)
		{
			// 빈 칸일 경우
			if (!GetTile(x, y))
			{
				for (int32 AboveY = y - 1; AboveY >= 0; --AboveY)
				{
					ATile* AboveTile = GetTile(x, AboveY);
					if (AboveTile)
					{
						// 타일 배열 업데이트
						SetTile(x, y, AboveTile);
						SetTile(x, AboveY, nullptr);

						// 타일의 그리드 좌표 갱신
						AboveTile->TilePosition = FVector2D(x, y);

						// 타일을 이동 ( 상대적 위치로 )
						FVector RelativeLocation = FVector(x * TileSpacing, y * TileSpacing, 0.0f);
						AboveTile->SetActorRelativeLocation(RelativeLocation);

						break;
					}
				}
			}
		}
	}

	// 빈 칸을 새로운 타일로 채우기
	RefillGrid();
}

• 타일 삭제 및 그리드 갱신
  • 매칭된 타일들을 삭제하고, 빈 공간을 채우는 로직을 추가합니다.
• 매칭된 타일 삭제 함수
  • 매칭된 타일을 찾아서 삭제하는 함수입니다. 타일을 삭제한 후 그 자리를 위쪽의 타일로 채우는 로직을 포함합니다.

SwapTileCommand.cpp

void USwapTileCommand::Excute()
{
	// 유효성 확인
	if (!FirstTile || !SecondTile)
	{
		UE_LOG(LogTemp, Error, TEXT("Invaild Tile for Swapping. "));
		return;
	}

	// 타일 그리드 가져오기 ( FirstTIle의 소속 그리드 )
	ATileGrid* TileGrid = FirstTile->TileGrid;

	// 그리드가 유효한지 확인
	if (!TileGrid)
	{
		UE_LOG(LogTemp, Warning, TEXT("Failed to retried. "));
	}

	// 타일 swap
	TileGrid->SwapTiles(FirstTile, SecondTile);

	// 타일 swap
	TArray<ATile*> MachingTiles = TileGrid->CheckForMatches();
	if (MachingTiles.Num() > 0) // 매칭이 있을 경우
	{
		TileGrid->RemoveMatchingTIles(MachingTiles);

	}
	else
	{
		// 매칭이 안될시 돌아가기
		Undo();
	}


	// TODO : 매칭 확인 등의 로직
}

void USwapTileCommand::Undo()
{
	// 그리드 내에서 타일을 교환 
	FirstTile->SetActorLocation(FirstTileOrigineType);
	SecondTile->SetActorLocation(SecondTileOrigineType);

	// 그리드 내의 타일 좌표도 원래 좌표로 
	FVector2D TempPosition = FirstTile->TilePosition;
	FirstTile->TilePosition = SecondTile->TilePosition;
	SecondTile->TilePosition = TempPosition;

	ATileGrid* TileGrid = FirstTile->TileGrid;
	if (TileGrid)
	{
		int32 x1, y1, x2, y2;
		if (TileGrid->GetTileGridPosition(FirstTile, x1, y1) && TileGrid->GetTileGridPosition(SecondTile, x2, y2))
		{
			TileGrid->SetTile(x1, y1, FirstTile);
			TileGrid->SetTile(x2, y2, SecondTile);
		}
	}
}

• Swap Excute 구현 내용 업데이트
• TileGrid가 없어서 아마도 밑줄이 그어질껀데 바로 하나 만들어주자

Tile.h

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "TileGrid.h"
#include "Tile.generated.h"

UCLASS()
class PUZZLESTUDY_API ATile : public AActor
{
	GENERATED_BODY()
	
    ...생략
public:
	ATileGrid* TileGrid;

protected:
	void UpdateAppearance();
};

TileGrid.cpp ( InitializeGrid )

• 추가 해준다

TileGamePlayerController.cpp ( ProcessSelectedTile )

void ATIleGmaePlayerController::ProcessSelectedTile()
{
	// 두 개의 타일이 선택되었을때,
	if (!FirstSelectedTile.IsValid() && !SecondSelectedTile.IsValid())
	{
		// 타일 처리 로직 ( 자리교한, 매칭 확인 ) 
		UE_LOG(LogTemp, Error, TEXT("Invaild Tile Selected. "));
		return;
	}

	// 타일이 인접한지 확인
	if (!FirstSelectedTile->IsAdjacentTo(SecondSelectedTile.Get()))
	{
		UE_LOG(LogTemp, Error, TEXT("Tile are not Adjacent! "));
		return;
	}

	// 교환 명령 생성
	USwapTileCommand* SwapCommand = NewObject<USwapTileCommand>(); // 클래스 이름 수정
	SwapCommand->Initalize(FirstSelectedTile.Get(), SecondSelectedTile.Get());

	// 커맨드 실행
	ATileCommandInvoker* CommandInvoker = GetWorld()->SpawnActor<ATileCommandInvoker>();
	CommandInvoker->ExcuteCommand(SwapCommand);

	// 매칭 확인 로직 ( 교환 후 매칭이 있는지 확인 )
	// MatchCheck(FirstSelectedTile, SecondSelectedTile);

	// 두 타일의 선택 해제
	if (FirstSelectedTile.IsValid())FirstSelectedTile->SetSelected(false);
	if (SecondSelectedTile.IsValid())SecondSelectedTile->SetSelected(false);

	// 선택 초기화
	if (FirstSelectedTile.IsValid())FirstSelectedTile = nullptr;
	if (SecondSelectedTile.IsValid())SecondSelectedTile = nullptr;
}

Tile.cpp ( IsAdjacentTo )

bool ATile::IsAdjacentTo(ATile* OtherTile) const
{
	if (!OtherTile)
		return false;

	// 두 타일의 그리드 좌표 차이를 계산하여 인접 여부 확인 
	int32 DeltaX = FMath::Abs(TilePosition.X - OtherTile->TilePosition.X);
	int32 DelatY = FMath::Abs(TilePosition.Y - OtherTile->TilePosition.Y);

	// 두 타일이 가로 또는 세로로 1칸 차이일 경우 인접한 것으로 판단 
	return (DeltaX + DelatY) == 1;
}

TileGrid.cpp ( RefillGrid / GenerateRandomTileType )

void ATileGrid::RefillGrid()
{
	for (int32 x = 0; x < GridWidth; ++x)
	{
		for (int32 y = 0; y < GridHeigh; ++y)
		{
			if (!GetTile(x, y))
			{
				ATile* NewTile = GetWorld()->SpawnActor<ATile>(TileClass);

				if (NewTile)
				{
					// 타일의 그리드 좌표 설정
					NewTile->TilePosition = FVector2D(x, y);
					NewTile->TileType = GenerateRandomTileType();
					NewTile->UpdateTileAppearance();
					NewTile->TileGrid = this;

					// 타일을 TileGrid의 자식으로 설정
					NewTile->AttachToActor(this, FAttachmentTransformRules::KeepRelativeTransform);

					// 상대적 위치 설정 
					FVector RelativeLocation = FVector(x* TileSpacing, y * TileSpacing, 0.0f);
					NewTile->SetActorRelativeLocation(RelativeLocation);

					// 그리드에 새로운 타일 설정 ( TileArray 업데이트 )
					SetTile(x, y, NewTile);
				}
			}
		}
	}

	ProcessMatchingLoop();
}

FName ATileGrid::GenerateRandomTileType()
{
	TArray<FName> TileTypes =
	{
		FName("Cone"),
		FName("Cube"),
		FName("Cylinder"),
		FName("Sphere"),
		FName("Capsule"),
		FName("Pyramid")
	};

	return TileTypes[FMath::RandRange(0, TileTypes.Num() - 1)];
}

• 빈 공간을 새 타일로 채우기
  빈 공간이 남아있는 경우, 새로운 타일을 생성하여 그리드를 다시 채웁니다

TileGrid.cpp ( ProcessMatchingLoop )

void ATileGrid::ProcessMatchingLoop()
{
	// 매칭이 있는지 확인
	TArray<ATile*> MatchingTiles = CheckForMatches();

	if (MatchingTiles.Num() > 0)
	{
		// 매칭된 타일이 있을 경우 삭제
		RemoveMatchingTIles(MatchingTiles);

		// 타일을 빈 공간으로 이동
		DropDownTiles();

		// 빈 공간에 새로운 타일을 채우기
		RefillGrid();

		// 모든 작업이 끝난 후 다시 매칭을 확인하기 위해 재귀 호출 ( 매칭이 더 이상 없을 때까지 반복 )
		ProcessMatchingLoop(); // 재귀 호출
	}
	else
	{
		// 더 이상 매칭이 없으면 루프 종료
		UE_LOG(LogTemp, Display, TEXT("No more matches, puzzle stabilized. "));
	}

}

• DropDownTiles() 함수 수정
  • 이 함수가 실행된 후에, 다시 매칭을 확인할 수 있도록 해야 합니다. 이 함수를 호출할 때 마다 매칭 확인을 재귀적으로 또는 루프에서 다시 실행
• RefillGrid() 함수 수정
  • RefillGrid() 후에 매칭 확인이 다시 이루어지도록 구현