20231220 54일차 A* Algorithm1

A*알고리즘을 통해 Terrain에서 움직이는 Object를 구현해보자.

 

먼저 A*알고리즘을 구성해주는 AStar를 정의한다.

#pragma once

class AStar
{
public:
    AStar(UINT width = 20, UINT height = 20);
    ~AStar();

    // Render: 그리드의 현재 상태를 표시합니다 (디버깅 또는 시각화 목적).
    void Render();

    // SetNode: 지형 정보로 A* 그리드를 초기화합니다.
    void SetNode(Terrain* terrain);

    // FindCloseNode: 주어진 위치를 기반으로 가장 가까운 노드를 찾습니다.
    int FindCloseNode(Vector3 pos);

    // GetPath: 시작 노드에서 종단 노드까지의 최적 경로를 찾습니다.
    void GetPath(IN int start, IN int end, OUT vector<Vector3>& path);

    // IsCollisionObstacle: 두 지점 사이에 장애물과 충돌이 있는지 확인합니다.
    bool IsCollisionObstacle(Vector3 start, Vector3 end);

    // AddObstacle: 그리드에 장애물을 추가합니다.
    void AddObstacle(Collider* collider) { obstacles.push_back(collider); }

private:
    // Reset: A* 알고리즘의 내부 상태를 초기화합니다.
    void Reset();

    // GetDiagonalManhattanDistance: 두 노드 사이의 대각 맨해튼 거리를 계산합니다.
    float GetDiagonalManhattanDistance(int start, int end);

    // Extend: 현재 중심 노드에서 종단 노드로 검색을 확장합니다.
    void Extend(int center, int end);

    // GetMinNode: openNodes 목록에서 총 비용이 가장 작은 노드를 찾습니다.
    int GetMinNode();

    // SetEdge: 그리드 내에서 노드 간의 엣지를 설정합니다.
    void SetEdge();

private:
    UINT width, height;          // 그리드의 크기.
    Vector3 interval;             // 노드 간의 간격.

    vector<Node*> nodes;          // 그리드 내 모든 노드의 목록.
    vector<int> openNodes;        // 탐색을 위한 열린 노드 목록.

    vector<Collider*> obstacles;  // 그리드 내의 장애물 목록.
};

A*알고리즘은 정의를 정리해놓은걸 참고하면 더 쉽게 이해가 가능하다.

 

맵 전체에 Node를 뿌려놓고, 해당 Node로 이동하는 것 이 더 빠르게 해당 경로로 이동하는게 가능하다면, 해당 Node로 이동하고, 다음 Node경로를 탐색하는 방식으로 이루어진다.

 

#include "Framework.h"

AStar::AStar(UINT width, UINT height)
    : width(width), height(height)
{
}

AStar::~AStar()
{
    // 동적으로 할당된 노드들을 정리합니다.
    for (Node* node : nodes)
        delete node;
}

void AStar::Render()
{
    // 그리드 내의 각 노드를 렌더링합니다.
    for (Node* node : nodes)
        node->Render();
}

void AStar::SetNode(Terrain* terrain)
{
    // 지형 크기를 기반으로 노드 간의 간격을 계산합니다.
    Float2 size = terrain->GetSize();
    interval.x = size.x / width;
    interval.y = size.y / height;

    // 노드의 자주 발생하는 재할당을 피하기 위해 공간을 예약합니다.
    nodes.reserve((width + 1) * (height + 1));

    // 각 그리드 위치에 대한 노드를 생성합니다.
    for (UINT z = 0; z <= height; z++)
    {
        for (UINT x = 0; x <= width; x++)
        {
            Vector3 pos = Vector3(x * interval.x, 0, z * interval.y);
            pos.y = terrain->GetOnGrondPosition(pos).y;

            // 노드를 생성하고 목록에 추가합니다.
            nodes.push_back(new Node(pos, nodes.size()));
            nodes.back()->UpdateWorld();

            // 지형 높이가 일정 값 이상인 경우 장애물로 설정합니다.
            if (pos.y > 5.0f)
            {
                nodes.back()->SetState(Node::OBSTACLE);
            }
        }
    }

    // 노드 간의 엣지를 설정합니다.
    SetEdge();
}

int AStar::FindCloseNode(Vector3 pos)
{
    // TODO: 주어진 위치에 가장 가까운 노드를 찾는 로직을 구현합니다.
    return 0;
}

void AStar::GetPath(IN int start, IN int end, OUT vector<Vector3>& path)
{
    // TODO: 시작 노드에서 종단 노드까지의 최적 경로를 찾는 로직을 구현합니다.
}

bool AStar::IsCollisionObstacle(Vector3 start, Vector3 end)
{
    // TODO: 두 지점 사이에 장애물과 충돌이 있는지 확인하는 로직을 구현합니다.
    return false;
}

void AStar::Reset()
{
    // TODO: A* 알고리즘의 내부 상태를 초기화하는 로직을 구현합니다.
}

float AStar::GetDiagonalManhattanDistance(int start, int end)
{
    // TODO: 두 노드 사이의 대각 맨해튼 거리를 계산하는 로직을 구현합니다.
    return 0.0f;
}

void AStar::Extend(int center, int end)
{
    // TODO: 현재 중심 노드에서 종단 노드로 검색을 확장하는 로직을 구현합니다.
}

int AStar::GetMinNode()
{
    // TODO: openNodes 목록에서 총 비용이 가장 작은 노드를 찾는 로직을 구현합니다.
    return 0;
}

void AStar::SetEdge()
{
    // 그리드 내의 각 노드에 대해 엣지를 설정합니다.
    UINT gridWidth = this->width + 1;

    FOR(nodes.size())
    {
        if (i % gridWidth != gridWidth - 1)
        {
            // 오른쪽 노드와의 엣지를 추가합니다.
            nodes[i]->AddEdge(nodes[i + 1]);
            nodes[i + 1]->AddEdge(nodes[i]);
        }

        if (i < nodes.size() - gridWidth)
        {
            // 아래쪽 노드와의 엣지를 추가합니다.
            nodes[i]->AddEdge(nodes[i + gridWidth]);
            nodes[i + gridWidth]->AddEdge(nodes[i]);
        }

        if (i % gridWidth != gridWidth - 1 && i < nodes.size() - gridWidth)
        {
            // 오른쪽 아래 대각선 노드와의 엣지를 추가합니다.
            nodes[i]->AddEdge(nodes[i + 1 + gridWidth]);
            nodes[i + 1 + gridWidth]->AddEdge(nodes[i]);
        }

        if (i % gridWidth != 0 && i < nodes.size() - gridWidth)
        {
            // 왼쪽 아래 대각선 노드와의 엣지를 추가합니다.
            nodes[i]->AddEdge(nodes[i - 1 + gridWidth]);
            nodes[i - 1 + gridWidth]->AddEdge(nodes[i]);
        }
    }
}

 

Terrain의 Size에 맞추어서 이동경로를 추가하고, 해당 이동경로에 대해 AStarNode를 배치하는 알고리즘까지 구현한 코드이다.

 

#pragma once
class Node : public BoxCollider
{
public:
    friend class AStar;

    // 노드의 상태를 정의하는 열거형
    enum State
    {
        NONE, OPEN, CLOSED, USING, OBSTACLE
    };

    // 노드 간의 엣지 정보를 저장하는 구조체
    struct Edge
    {
        int index;  // 연결된 노드의 인덱스
        float cost; // 엣지의 비용
    };

public:
    // 생성자: 위치와 인덱스를 초기화합니다.
    Node(Vector3 pos, int index);

    // 소멸자: 동적으로 할당된 엣지를 정리합니다.
    ~Node();

    // 노드를 렌더링하는 함수
    void Render();

    // 다른 노드와의 연결된 엣지를 추가하는 함수
    void AddEdge(Node* node);

    // 노드의 상태를 설정하는 함수
    void SetState(State state) { this->state = state; }

    // 현재까지의 총 비용을 반환하는 함수
    float GetCost() { return f; }

private:
    int index = 0; // 노드의 인덱스
    int via = -1;  // 경로 탐색 시 경유한 노드의 인덱스

    // 비용
    float f = 0, g = 0, h = 0;

    State state = NONE; // 노드의 상태

    vector<Edge*> edges; // 노드와 연결된 엣지들의 목록
};

 

각 노드를 구성하는 객체는 위와 같은 헤더를 따른다.

 

노드는 스스로의 상태를 설정하고, 현재 Node로 이동하는 Cost를 반환한다.

#include "Framework.h"

Node::Node(Vector3 pos, int index)
{
    // 노드의 로컬 위치를 초기화합니다.
    localPosition = pos;
}

Node::~Node()
{
    // 동적으로 할당된 엣지들을 정리합니다.
    for (Edge* edge : edges)
        delete edge;
}

void Node::Render()
{
    // 노드의 상태에 따라 색상을 설정합니다.
    switch (state)
    {
    case Node::NONE:
        SetColor(0, 1, 1); // 하늘색
        break;
    case Node::OPEN:
        SetColor(0, 0, 1); // 파란색
        break;
    case Node::CLOSED:
        SetColor(0, 0, 0); // 검은색
        break;
    case Node::USING:
        SetColor(0, 1, 0); // 녹색
        break;
    case Node::OBSTACLE:
        SetColor(1, 0, 0); // 빨간색
        break;
    }

    // Collider의 Render 함수를 호출하여 색상을 적용합니다.
    Collider::Render();
}

void Node::AddEdge(Node* node)
{
    // 새로운 엣지를 생성하고 정보를 설정합니다.
    Edge* edge = new Edge();
    edge->index = node->index;
    edge->cost = MATH->Distance(node->GetGlobalPosition(), GetGlobalPosition());

    // 엣지를 노드의 엣지 목록에 추가합니다.
    edges.push_back(edge);
}

 

각 노드들이 연결된 edge를 설정한다. 즉, 이동이 가능한 Node간의 Line을 표기한 것 이다.

 

이 객체를 Scene에 배치하여 표시해보자.

 

#include "Framework.h"

AStarScene::AStarScene()
{
	terrain = new Terrain();
	astar = new AStar();
	astar->SetNode(terrain);

	lion = new Lion();
	lion->SetTerrain(terrain);
}

AStarScene::~AStarScene()
{
	delete terrain;
	delete lion;
}

void AStarScene::Update()
{
	lion->Update();
}

void AStarScene::PreRender()
{
}

void AStarScene::Render()
{
	terrain->Render();
	lion->Render();
	astar->Render();
}

void AStarScene::PostRender()
{
}

void AStarScene::GUIRender()
{
	terrain->GUIRender();
	lion->GUIRender();
}

Terrain에 고르게 분포된 Node를 확인할 수 있다.

높이값에 따라 이동이 가능한지 아닌지를 표기한다.