[UE5] 노노그램에 Undo, Redo 기능 추가

 

퍼즐을 푸는 중에 실수를 해서 칸을 잘못 채우는 경우가 종종 발생한다.

의도치 않게 칸이 채워진 것이라 어떻게 했는지 기억이 나지 않는 경우도 있다.

그럴때 Undo 기능이 유용하게 사용된다.

그리고 Undo가 있으면 Redo도 빠질 수 없다.

 

 

 

---

 

 

 

Undo 기능은 간단하게 더블 링크드 리스트로 구현했다.

링크드 리스트의 각 노드들은 퍼즐이 어떻게 변했는지에 대한 정보를 가지게 된다.

어느 칸들이(좌표) 어느 상태에서(From) 어느 상태로(To) 변했는지를 기억한다.

 

변경된 상태들을 저장하는 구조체를 하나 추가한다.

// PlayLog struct

struct FPlayLog
{
    ECellState From;
    ECellState To;
    TArray<FVector2D> Cells;

    FPlayLog()
    {
        From = ECellState::ECS_Invalid;
        To = ECellState::ECS_Invalid;
        Cells = TArray<FVector2D>();
    }

    ~FPlayLog()
    {
        Clear();
    }

    void Clear()
    {
        Cells.Empty();
    }
};

칸의 좌표는 언리얼 엔진의 FVector2D를 사용하기로 했다.

 

그 다음 로그를 저장할 노드 구조체를 추가한다.

// LogNode struct

struct FLogNode
{
    TUniquePtr<FPlayLog> Log;
    TWeakPtr<FLogNode> PrevNode; // 순환 참조 방지 목적으로 Weak 포인터 사용
    TSharedPtr<FLogNode> NextNode;
    
    FLogNode()
        : Log(nullptr)
        , PrevNode(nullptr)
        , NextNode(nullptr)
    {}

    explicit FLogNode(TUniquePtr<FPlayLog> NewLog)
        : Log(MoveTemp(NewLog))
        , PrevNode(nullptr)
        , NextNode(nullptr)
    {}

    ~FLogNode()
    {
        if (Log.IsValid())
        {
            Log->Clear();
        }
        PrevNode.Reset();
        NextNode.Reset();
    }

    void SetLog(TUniquePtr<FPlayLog> NewLog)
    {
        Log = MoveTemp(NewLog);
    }

    // 복사 생성자와 복사 대입 연산자 삭제
    FLogNode(const FLogNode&) = delete;
    FLogNode& operator=(const FLogNode&) = delete;
};

멤버 변수로 유니크 포인터를 가지는 경우에는 복사 생성자와 복사 대입 연산자는 자동으로 생성되지 않는다고 한다.

그래도 명시적으로 삭제해두기로 했다.

 

그 다음 더블 링크드 리스트를 구현한다.

// PlayLogger.h

UCLASS(BlueprintType, Blueprintable)
class NONOGRAM_API UPlayLogger : public UObject
{
    GENERATED_BODY()

public:
    UPlayLogger();
    virtual void BeginDestroy() override;
    
private:
    int32 MaxSize;
    int32 CurrentSize;
    TSharedPtr<FLogNode> Head;
    TSharedPtr<FLogNode> Tail;
    TSharedPtr<FLogNode> Current;

    void DeleteNodesAfter(const TSharedPtr<FLogNode>& Node);
    
    bool PopFront();

public:
    void AddLog(TUniquePtr<FPlayLog> NewLog);

    const FPlayLog* Undo();
    const FPlayLog* Redo();

    bool CanUndo() const;
    bool CanRedo() const;

    void Clear();
};



// PlayLogger.cpp

UPlayLogger::UPlayLogger()
    : MaxSize(10)
    , CurrentSize(0)
    , Head(MakeShared<FLogNode>())
    , Tail(MakeShared<FLogNode>())
    , Current(Head)
{
    Head->NextNode = Tail;
    Tail->PrevNode = Head;
}

void UPlayLogger::BeginDestroy()
{
    Clear();
    Head.Reset();
    Tail.Reset();
    Current.Reset();
    
    Super::BeginDestroy();
}

void UPlayLogger::DeleteNodesAfter(const TSharedPtr<FLogNode>& Node)
{
    if (!Node.IsValid() || Node == Tail)
    {
        return;
    }

    TSharedPtr<FLogNode> It = Node->NextNode;
    while (It.IsValid() && It != Tail)
    {
        It = It->NextNode;
        CurrentSize--;
    }
    CurrentSize = FMath::Max(0, CurrentSize);
    Node->NextNode = Tail;
    Tail->PrevNode = Node;
}

bool UPlayLogger::PopFront()
{
    TSharedPtr<FLogNode> FrontNode = Head->NextNode;
    if (FrontNode.IsValid() && FrontNode != Tail)
    {
        Head->NextNode = FrontNode->NextNode;
        if (FrontNode->NextNode.IsValid())
        {
            FrontNode->NextNode->PrevNode = Head;
        }
        CurrentSize--;
        return true;
    }
    return false;
}

void UPlayLogger::AddLog(TUniquePtr<FPlayLog> NewLog)
{
    // Current 뒤의 모든 노드 제거
    DeleteNodesAfter(Current);

    // 새로운 노드 생성 후 Current 뒤에 추가
    TSharedPtr<FLogNode> NewNode = MakeShared<FLogNode>(MoveTemp(NewLog));
    NewNode->PrevNode = Current;
    NewNode->NextNode = Current->NextNode;

    if (Current->NextNode.IsValid())
    {
        Current->NextNode->PrevNode = NewNode;
    }
    Current->NextNode = NewNode;

    Current = NewNode;

    // 크기 증가
    CurrentSize++;
    while (CurrentSize > MaxSize)
    {
        // 최대 로그 크기를 넘으면 가장 오래된 로그 제거
        if (!PopFront())
        {
            break;
        }
    }
}

const FPlayLog* UPlayLogger::Undo()
{
    if (CanUndo())
    {
        const FPlayLog* Ret = Current->Log.Get();
        Current = Current->PrevNode.Pin();
        return Ret;
    }
    return nullptr;
}

const FPlayLog* UPlayLogger::Redo()
{
    if (CanRedo())
    {
        Current = Current->NextNode;
        return Current->Log.Get();
    }
    return nullptr;
}

bool UPlayLogger::CanUndo() const
{
    return Current != Head;
}

bool UPlayLogger::CanRedo() const
{
    return Current->NextNode != Tail;
}

void UPlayLogger::Clear()
{
    DeleteNodesAfter(Head);
    Current = Head;
    CurrentSize = 0;
}

여기에서는 링크드 리스트의 Head와 Tail 노드에는 아무런 정보를 넣지 않고 끝을 알려주는 용도로 사용한다.

그리고 Current는 현재 상태를 가리키고 있다.

DeleteNodesAfter 함수는 지정한 노드의 뒤를 모두 지우는 작업을 한다.

Undo를 하면 Current 뒤에 여러 로그가 존재하는데 이 상태에서 새로운 로그가 추가되면 Current 뒤에있는 로그들은 사용이 불가능하기 때문에 Current 뒤의 로그를 모두 지우고 새로운 로그를 추가해야한다.

이때 DeleteNodesAfter 함수가 사용된다.

그리고 모든 로그를 지울때에도 유용하게 사용된다.

 

Undo와 Redo를 할 때에는 Current가 가리키는 노드의 로그를 전달해줘서 퍼즐을 관리하는 클래스에게 그 로그의 정보를 활용하게 하면 된다.

 

 

 

---

 

 

 

적용 결과는 아래 영상의 초반에 나온다.

https://youtu.be/umDbsPMNqFY?si=Zs9ByabBvK5PifE_ 

Undo와 Redo를 한 뒤에는 CanUndo와 CanRedo함수로 각 동작이 가능한지 한번 더 확인해서 불가능한 경우에는 버튼을 비활성화 해줬다.