경로 찾기 알고리즘 : A Pathfinding* Algorithm

2023. 6. 14. 11:19·C#/Algorithm
반응형

A* 알고리즘

A* 알고리즘은 경로찾기 알고리즘 중 하나로, 출발지점부터 목적지점까지의 최적 경로를 탐색합니다. 이 알고리즘은 가중치 그래프에서 최단 경로를 찾는 데 사용됩니다. A* 알고리즘은 다음과 같은 특징을 가지고 있습니다.

  • 휴리스틱 함수를 사용하여 최적 경로를 탐색합니다.
  • 경로의 비용을 계산하고, 비용이 가장 적은 경로를 선택합니다.
  • 경로를 찾는 과정에서 이동할 수 있는 모든 경로를 검사합니다.

A* 알고리즘은 C#에서 구현하기 쉽고, 많은 개발자들이 사용하고 있습니다.

A* 알고리즘 구현

A* 알고리즘을 구현하기 위해서는 다음과 같은 단계를 따르면 됩니다.

  1. 출발점과 목적지점을 설정합니다.
  2. 휴리스틱 함수를 구현합니다.
  3. 우선순위 큐를 구현합니다.
  4. A* 알고리즘을 구현합니다.

출발점과 목적지점 설정

출발점과 목적지점을 설정하는 방법은 다양합니다. 가장 간단한 방법은 다음과 같습니다.

// 출발점 설정
Vector2Int start = new Vector2Int(0, 0);

// 목적지점 설정
Vector2Int goal = new Vector2Int(5, 5);

휴리스틱 함수 구현

A* 알고리즘에서는 휴리스틱 함수를 사용하여 최적 경로를 탐색합니다. 휴리스틱 함수는 출발점에서 목적지점까지의 예상 비용을 계산하는 함수입니다. 여기서는 맨하탄 거리를 사용하는 휴리스틱 함수를 구현합니다.

// 맨하탄 거리를 계산하는 휴리스틱 함수
private int Heuristic(Vector2Int a, Vector2Int b)
{
    return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}

우선순위 큐 구현

A* 알고리즘에서는 우선순위 큐를 사용하여 경로를 탐색합니다. 우선순위 큐는 비용이 가장 적은 경로를 먼저 검사하도록 하는 자료구조입니다. C#에서는 SortedSet을 사용하여 우선순위 큐를 구현할 수 있습니다.

// 우선순위 큐 구현
SortedSet<PathNode> openSet = new SortedSet<PathNode>();

A* 알고리즘 구현

A* 알고리즘을 구현하는 방법은 다양합니다. 여기서는 다음과 같은 단계를 따릅니다.

  1. 출발점을 우선순위 큐에 추가합니다.
  2. 우선순위 큐에서 비용이 가장 적은 경로를 선택합니다.
  3. 선택한 경로를 폐쇄목록에 추가합니다.
  4. 선택한 경로의 인접한 경로들을 검사합니다.
  5. 인접한 경로들 중에서 폐쇄목록에 없는 경로를 우선순위 큐에 추가합니다.
  6. 목적지점에 도달하면 경로를 반환합니다.
// A* 알고리즘 구현
PathNode startNode = new PathNode(start);
openSet.Add(startNode);

while (openSet.Count > 0)
{
    PathNode currentNode = openSet.First();
    openSet.Remove(currentNode);

    if (currentNode.position == goal)
    {
        return currentNode;
    }

    closedSet.Add(currentNode);

    foreach (Vector2Int neighborPosition in GetNeighborPositions(currentNode.position))
    {
        PathNode neighborNode = new PathNode(neighborPosition, currentNode);
        if (closedSet.Contains(neighborNode))
        {
            continue;
        }

        int newCost = currentNode.cost + 1;
        if (newCost < neighborNode.cost || !openSet.Contains(neighborNode))
        {
            neighborNode.cost = newCost;
            neighborNode.heuristic = Heuristic(neighborNode.position, goal);
            neighborNode.totalCost = neighborNode.cost + neighborNode.heuristic;
            neighborNode.parent = currentNode;

            if (!openSet.Contains(neighborNode))
            {
                openSet.Add(neighborNode);
            }
        }
    }
}

return null;

마치며

이번 글에서는 C#에서 경로찾기 알고리즘을 구현하는 방법과 그에 대한 자세한 설명을 다루었습니다. 위에서 다룬 A* 알고리즘을 사용하면 게임 개발에서 매우 유용하게 사용할 수 있습니다. 이를 참고하여 프로그래밍 실력을 더욱 향상시켜보세요.

저작자표시 비영리 변경금지 (새창열림)

'C# > Algorithm' 카테고리의 다른 글

무차별 대입 알고리즘 : Brute Force  (0) 2023.07.10
최단 경로 알고리즘 : Dijkstra  (0) 2023.07.10
Greedy Algorithm: 간단하면서도 효과적인 문제 해결 방법  (0) 2023.07.09
역추적 알고리즘 : Backtracking  (0) 2023.07.07
Boids/Flocking Algorithm  (0) 2023.06.16
'C#/Algorithm' 카테고리의 다른 글
  • 최단 경로 알고리즘 : Dijkstra
  • Greedy Algorithm: 간단하면서도 효과적인 문제 해결 방법
  • 역추적 알고리즘 : Backtracking
  • Boids/Flocking Algorithm
코샵
코샵
나의 코딩 일기장
    반응형
  • 코샵
    끄적끄적 코딩 공방
    코샵
    • 분류 전체보기 (725)
      • 스마트팜 (0)
      • 상품 추천 (223)
      • MongoDB (4)
      • 하드웨어 (17)
      • 일기장 (4)
      • 파이썬 (130)
        • Basic (41)
        • OpenCV (8)
        • Pandas (15)
        • PyQT (3)
        • SBC(Single Board Computer) (1)
        • 크롤링 (14)
        • Fast API (29)
        • Package (6)
      • Unity (138)
        • Tip (41)
        • Project (1)
        • Design Pattern (8)
        • Firebase (6)
        • Asset (2)
      • Linux (4)
      • C# (97)
        • Algorithm (11)
        • Window (7)
      • TypeScript (51)
        • CSS (10)
      • Git (11)
      • SQL (5)
      • Flutter (10)
        • Tip (1)
      • System (1)
      • BaekJoon (6)
      • Portfolio (2)
      • MacOS (1)
      • 유틸리티 (1)
      • 서비스 (6)
      • 자동화 (3)
      • Hobby (10)
        • 물생활 (10)
        • 식집사 (0)
  • 인기 글

  • 태그

    파이썬
    리뷰이관
    카페24리뷰이관
    리스트
    셀레니움
    unity
    ipcamera
    카페24리뷰
    cv2
    rtsp
    C#
    codingtips
    appdevelopment
    리뷰관리
    긴유통기한우유
    Python
    스크립트 실행 순서
    learntocode
    상품 리뷰 크롤링
    스크립트 실행
    믈레코비타멸균우유
    list
    programmerlife
    devlife
    유니티
    라떼우유
    스마트스토어리뷰
    programming101
    쇼핑몰리뷰
    codingcommunity
  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
코샵
경로 찾기 알고리즘 : A Pathfinding* Algorithm
상단으로

티스토리툴바