정의

에이스타(A*; A-star) 알고리즘은 경로 탐색 및 길 찾기 문제를 해결하기 위한 효율적인 알고리즘 중 하나입니다. 특히, 그래프 기반의 환경에서 시작점과 목적지 간의 최적 경로를 찾는 데 사용됩니다. 에이스타 알고리즘은 다익스트라 알고리즘의 변형으로, 휴리스틱(Heuristic) 함수를 사용하여 탐색을 가속화하고 최적 경로를 빠르게 찾을 수 있습니다.

---

휴리스틱(Heuristic) 함수

다익스트라 알고리즘은 현재 노드가 출발 지점으로부터 얼마나 떨어져 있는지만을 고려하여 경로를 결정하는데, 이로 인해 모든 가능한 경로를 무조건적으로 고려해야 하므로 계산량이 많고 비효율적일 수 있습니다. 최적 경로를 찾는 데 중점을 두기 때문에 목적지에 대한 추가 정보를 활용하지 않습니다.

에이스타 알고리즘은 이러한 단점을 보완하기 위해 휴리스틱 함수를 도입하였습니다. 이 함수는 현재 노드에서 목적지까지의 추정 거리를 계산하여 경로의 방향을 결정하는 데 활용됩니다. 목적지에 대한 추가 정보를 고려함으로써 더 효율적으로 경로를 탐색할 수 있습니다.

아래 사진은 다익스트라와 에이스타를 비교한 것입니다.

이러한 휴리스틱 함수에는 여러가지 종류의 공식들을 사용할 수 있습니다.

---

코드 구현

출처 사이트에서의 코드를 통해 맵을 변경하며 학습한 결과 맨허튼 거리만을 휴리스틱 함수로 사용하면 경로 생성에 문제점이 있다는 것을 발견하였습니다. 이에 대각선 방향에 대한 이동을 고려해주었고 장애물에 가중치를 두어 보다 안전한 경로를 생성하도록 하였습니다.

            # f, g, h값 업데이트

            a = 0
            b = (child.position[0] - currentNode.position[0])**2 + (child.position[1] - currentNode.position[1])**2
            c = 0
            for crossPosition in [(0, -1), (0, 1), (-1, 0), (1, 0)]:

                # 노드 위치 업데이트
                weightPosition = (
                    currentNode.position[0] + crossPosition[0],  # X
                    currentNode.position[1] + crossPosition[1])  # Y
                    
                # 미로 maze index 범위 안에 있어야함
                within_range_criteria = [
                    weightPosition[0] > (len(maze) - 1),
                    weightPosition[0] < 0,
                    weightPosition[1] > (len(maze[len(maze) - 1]) - 1),
                    weightPosition[1] < 0,
                ]

                if any(within_range_criteria):  # 하나라도 true면 범위 밖임
                    continue
                
                if maze[weightPosition[0]][weightPosition[1]] == 1:
                    a = 1
                    break
            if a == 1 and b == 2:
                c = 3


            child.g = currentNode.g + b**(1/2)
            dx = abs(child.position[0] - endNode.position[0])
            dy = abs(child.position[1] - endNode.position[1])
            D=1
            D2=2 ** 0.5
            child.h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) + c
            
            child.f = child.g + child.h

---

출처

https://qiao.github.io/PathFinding.js/visual/
https://choiseokwon.tistory.com/210