내일배움캠프 53일차 TIL : A* 알고리즘 2

김정환·2024년 11월 28일
0

키워드

  • A* 알고리즘 c# 구현

어제 이론을 살펴봤다면 오늘은 구현해봤다.

구현

아래 그림과 같이 8 x 8 그리드가 있다.
그리드로 한 이유는 이번 프로젝트에서 써볼 환경이 그리드 환경이라서 그렇다.

휴리스틱 함수 : 맨해튼 거리

휴리스틱 추정값을 구하는 방법이 3개 정도 있다.

  • 유클리디안 거리 : 직선 거리 탐색에 유용
  • 맨해튼 거리 : 격자형 그래프에서 상하좌우로 움직일 때 적합
  • 체스판 거리 : 격자형에서 대각선 이동이 가능할 때 적합

이 중에 맨해튼 거리는 격자형 그래프에서 두 점 간의 거리 계산에 사용되는 방법이다.
이동 방식이 상,하,좌,우 이렇게 네 가지인 경우에 적합하다.

거리 계산 공식

두 점 (x1, y1), (x2, y2)가 있을 때

거리 = | x2 - x1 | + | y2 - y1 |

준비

public class Node
{
    public Node parent;
    public Vector2Int coord;
    public float g;
    public float h;
    public float cost;
    public GameObject obj;
    
    public void RecalculateCost()
    {
        cost = g + h;
    }
}
  • 위와 같이 노드 클래스를 미리 준비한다.
  • 좌표와 함께 비용 계산에 쓸 g, h, f에 해당하는 변수들도 만들어둔다.

과정

1. 격자 만들기

  • 격자 그리드를 만들어준다.
  • 사이즈는 8 x 8로 해두었다.

2. 탐색 시작


  • 인스펙터에 시작점(0,0)과 목적지(5,4)를 입력해서 탐색을 시작한다.
  • 이동 비용은 1로 넣어둔 상태이다.

3. 경로 찾기 : 초기화

  • 탐색 예정 노드 목록 openList를 생성한다.
    • f값을 통해서 최적값을 구하기 위해서 우선순위 큐를 이용할 수 있다.
  • 탐색 완료 노드 목록 closedList를 생성한다.
    • 중복 방지를 위해 set로 만들었다.
  • 시작 node 초기화
    • 시작 노드의 g(시작점~현재지점)는 당연히 0을 넣는다.
    • h는 맨해튼 거리 계산식으로 구한다.
      float GetHeuristic(Vector2 start, Vector2 end)
      {
          // 맨해튼 거리 계산 방식
          return Mathf.Abs(end.x - start.x) + Mathf.Abs(end.y - start.y);
      }
    • g, h 값을 구했으니 f값을 적용한다.
  • openList에 시작점을 추가하면서 초기화를 마무리한다.

4. 경로 찾기 (반복) : 탐색

  • openList에서 f값(cost)이 가장 작은 것을 꺼내온다.
  • 그리고 꺼낸 node의 좌표가 목적지인지 확인해서 탐색 진행 여부를 결정한다.
  • 만약 목적지가 아니라면 현재 node는 탐색 완료로 처리한다.
    • closedList에 넣음으로써 탐색 완료 처리한다.

5. 경로 찾기 (반복) : 이웃 확인

  • 상하좌우의 이웃 좌표를 구한다.
    • 이때 맵 사이즈를 벗어나면 생략한다.
  • 유효한 이웃 좌표를 통해 node를 찾는다.
    • 만약 이미 탐색한 노드라면 생략한다. (closedList 확인)
  • 이웃 노드로 이동했을 때, g값을 미리 계산해둔다.
  • 그리고 이 노드가 탐색 중인 것이 아니라면,
    g, h값을 갱신하고 부모 노드로 current 노드를 넣는다.
    • 이후 openList에 추가해서 비용 검사 대상이 되도록한다.
  • 만약에 이미 탐색할 노드인데, 더 나은 경로로 발견했다면 비용과 부모 노드를 갱신한다.
    • 더 나은 경로인지 판단할 때, 미리 계산한 g값을 이용한다.
  • 이렇게 상하좌우를 다 찾으면 다시 f값(cost)가 가장 작은 노드를 구하고,
    목적지인지 확인하는 일련의 과정을 반복한다.

  • 상하좌우 이동을 위한 배열

6. 경로 찾기 : 목적지를 찾은 경우

  • 목적지를 찾은 경우 현재 노드를 이용해서 경로를 구성한다.
  • 현재 노드의 부모 노드를 거슬러 올라가면서 path 리스트를 만든다.
    • 단, 이때 방향이 역순이므로 한번 뒤집어주어야한다.

예외. 목적지를 못 찾은 경우

  • 어떤 이유로 경로를 못 찾을때 이렇게 null을 반환한다.

결과

  • 결과로 이렇게 (5,4) 지점을 찾은 모습이다.

#내일배움캠프 #스파르타내일배움캠프 #스파르타내일배움캠프TIL

profile
사파 개발자

0개의 댓글

관련 채용 정보