서론
기존에 스크립트를 작성한 적 없던 다익스트라 알고리즘에 대해 알아보고
이를 응용하여 Astar 알고리즘 로직도 구현해보겠다.
TIL 요약
- Dijkstra Algorithm: 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘
- A* Algorithm: 휴리스틱을 사용하는 알고리즘 ('A') 중에서 최적의 결과를 보장하는 알고리즘
Dijkstra Algorithm
그래프에서 한 노드에서 다른 모든 노드까지의 최적 경로를 찾아내는 알고리즘
A*를 알아보기 전 기반이 되는 다익스트라 알고리즘 부터 알아보겠다.
원리
해당 알고리즘의 진행 순서를 알아보자.
1. 준비
- 초기 거리 설정: 시작 노드 제외한 모든 노드에는 거리를 무한대로 설정(경로를 모른다는 뜻)
- 시작지는 0
2. 탐색 및 갱신을 반복
- 출발지로부터 누적 거리(distance)가 가장 짧은 노드 선택하여 현재 노드(U)로 지정
- 이동한 현재 노드를 방문지(visited)로 체크, 시작 노드에서 U까지의 거리를 최단거리로 확정.
- 거리 갱신
1. 현재 노드(U)와 연결된 모든 인접 노드(V) 를 살펴봄
2. 새로운 경로 비용 계산: distances[U](출발지 -> U) + cost(U -> V의 간선 비용)
3. 새로운 경로 비용이 기존보다 작다면 distances[V]를 새로운 경로 비용으로 갱신하고 U를 V의 부모로 기록.3. 종료 및 경로 복원
- 종료: 모든 노드를 방문하거나, 목표 노드의 최단거리가 확정되면 알고리즘 종료.
- 경로 복원: 목표 노드에서 기록된 부모 노드를 역순으로 정렬하면
시작지 -> 출발지까지의 최단 경로를 알아낼 수 있음.
예시)
1. 1번 노드를 제외한 나머지의 거리는
현재 openList {(1, 거리0)}
이후 탐색 시작
2. 연결된 인접 노드 탐색 및 갱신(반복)
진행 과정을 잠시 보면
1)
- 시작점의 인접 노드 탐색
- 노드1 방문처리
- 2와 3의 부모는 1.
- 1→2 = 0 + 8 = 8
- 1→3 = 0 + 5 = 5
- 가중치 낮은 3번 노드를 선택.
현재 openList {(3, 5), (2,8)}
2)
- 노드 3 방문 처리(거리 5 확정)
- 인접 노드(4번) 선택하여 가중치 추가
- 4의 부모는 3.
- 3→4 = 5 + 12 = 17
현재 openList {(4, 17), (2,8)}
3)
- openList 에서 가장 짧은 노드2 선택
- 노드2 방문처리(거리 8 확정)
- 인접 노드(4번) 선택하여 가중치 추가
- 2→4 = 8 + 2 = 10
- 이전 17보다 작은 수치이므로 노드 4의 거리가 17 → 10으로 갱신
- 4의 부모는 더 작은 가중치를 가진 2.
현재 openList {(4, 17), (4,10)}
이런 순서로 부모 노드를 기록해가며 탐색 및 갱신이 이루어짐.
이후 반복은 4→5,6 갱신.
현재 openList {(5, 14), (6,19)}
4→6 은 19
4→5→6은 18이므로 마지막으로 경로 갱신하여 종료.
3. 종료 및 경로 복원
- 다음 선택 목표가 목표인 6이 되었으므로 반복 종료.
- 목표 노드로부터 부모 노드를 역순으로 따라가서 경로 복원
최종 최단 경로: 1 → 2 → 4 → 5 → 6
총 비용 : 18
지루하고 현학적인 진행 과정을 알아보았으니
이를 기반으로 A* Algorithm을 알아보자
A* Algorithm
기본적으로 다익스트라 알고리즘과 비슷한 방식.
어떤 차이점이 있을 지 알아보자.
유래
간단히만 알고 가자.
초기에 A 알고리즘이 존재했었고 이는 휴리스틱을 사용하여 탐색하지만
최단 경로를 보장하지 못했고 이를 최적화시킨 것이 A*
따라서 휴리스틱을 사용하는 알고리즘 (A) 중에서 최적의(Optimal) 결과를 보장하는 알고리즘.
원리
기본 방식이 다익스트라 알고리즘과 큰 차이가 없기에
다익스트라와의 차이점만 알아보면 될 듯 하다.
다익스트라는 이미 진행한 거리(distances) 를 기준으로 최적 거리를 계산한다.
A* 역시 distances를 활용하지만
추가적으로 휴리스틱(Heuristic) 이라는 예상 거리를 사용함.
따라서 A* 는 다음 노드 선택 시에
총 예상 비용 = 지금까지 온 거리 + 앞으로 갈 예상 거리
를 고려하여 탐색한다.
이 방식을 통하여 단순히 가까운 곳을 탐색하는 것이 아닌
목표 지점과 가장 가까울 것으로 예상되는 노드를 우선적으로 탐색하게 되어
다익스트라보다 훨씬 빠르게 경로를 찾을 수 있게 된다.
아래의 움짤로 이해를 도울 수 있을 듯
코드 정리
다익스트라 알고리즘, A* 알고리즘을 알아보았으니
해당 코드는 이 곳에 정리해두겠다.
원랜 다른 비공개 글에 작성해두지만
이번엔 결국 코드 기반의 알고리즘이기에 같이 작성.
1. 다익스트라
using System.Collections.Generic;
using UnityEngine;
class DijkstraNode
{
public int Index; // 번호(구분용)
public Vector2 Pos; // 해당 노드좌표
public float Distance; // 시작점부터 현재 노드까지의 누적거리
public DijkstraNode Parent; // 경로 추적용 부모
public DijkstraNode(int index, Vector2 pos, float distance, DijkstraNode parent = null)
{
Index = index;
Pos = pos;
Distance = distance;
Parent = parent;
}
}
public class DijkstraExample : MonoBehaviour
{
private void Start()
{
int n = 4; //노드 수
int startIndex = 0; //시작과 목표 노드
int goalIndex = 3;
//각각의 노드에 좌표 설정
Vector2[] positions = new Vector2[4]
{
new Vector2(0,0),
new Vector2(1,0),
new Vector2(0,1),
new Vector2(1,1)
};
//튜플로 그래프 구성
//(이동할 노드, 드는 비용)
List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
for (int i = 0; i < n; i++)
{
graph[i] = new List<(int to, float cost)>();
}
//비용 정보 추가
graph[0].Add((1,1)); // A->B 1
graph[0].Add((2,4)); // A->C 4
graph[1].Add((2,2)); // B->C 2
graph[1].Add((3,6)); // B->D 6
graph[2].Add((3,3)); // C->D 3
//각 노드까지의 최소 거리 저장 배열
float[] distances = new float[n];
for (int i = 0; i < n; i++)
{
distances[i] = float.MaxValue;
}
//시작지
distances[startIndex] = 0;
//방문여부 저장 배열
bool[] visited = new bool[n];
//탐색 대기 리스트
var openList = new List<DijkstraNode>();
openList.Add(new DijkstraNode(startIndex, positions[startIndex], 0));
//탐색 루프
while (openList.Count > 0)
{
//거리 기준 정렬
openList.Sort((a, b) => a.Distance.CompareTo(b.Distance));
//최소 거리 노드 선택
var current = openList[0];
//선택한 애는 탐색 제외
openList.RemoveAt(0);
//방문한 노드 스킵
if (visited[current.Index])
{
continue;
}
//방문 처리
visited[current.Index] = true;
//목표 노드 도착 시 경로 복원
if (current.Index == goalIndex)
{
//경로 저장용 리스트
var path =new List<int>();
var temp = current;
//부모 따라 역추적
while (temp != null)
{
path.Add(temp.Index);
temp = temp.Parent;
}
//D C B A 역순으로 정리되므로 리버스
path.Reverse();
//A B C D
Debug.Log("Dijstra Path" + string.Join(" -> ", path));
Debug.Log("Distance: " + current.Distance);
break;
}
foreach (var neighbor in graph[current.Index])
{
//방문 노드 패스
if (visited[neighbor.to])
{
continue;
}
//현재 노드까지의 거리 + 간선 비용
float t = current.Distance + neighbor.cost;
//더 짧은 경로 발견 시
if (t< distances[neighbor.to] )
{
distances[neighbor.to] = t;
//새로운 노드 추가
//
openList.Add(new DijkstraNode(neighbor.to, positions[neighbor.to], t, current));
}
}
}
}
}
2. A*
using System;
using System.Collections.Generic;
using UnityEngine;
class AstarNode : IComparable<AstarNode> //CompareTo 안하면 죽인다
{
public int Index;
public Vector2 Pos;
public float G; //현재까지의 이동 거리
public float H; //휴리스틱, 예측 비용
public float F => G + H; //가중치
public AstarNode Parent; //복원 용도
public AstarNode(int index, Vector2 pos, float g, float h, AstarNode parent = null)
{
Index = index;
Pos = pos;
G = g;
H = h;
Parent = parent;
}
public int CompareTo(AstarNode other)
{
int fCompare = F.CompareTo(other.F);
if (fCompare != 0)
{
return fCompare;
}
return Index.CompareTo(other.Index);
}
}
public class AstarExample : MonoBehaviour
{
//두 좌표 사이의 거리를 휴리스틱으로 사용하기로 함
static float Heuristic(Vector2 a, Vector2 b) => Vector2.Distance(a, b);
private void Start()
{
//노드 수 지정, 시작, 도착점 지정
int n = 4;
int startIndex = 0;
int goalIndex = 3;
//각각의 노드에 좌표 설정
Vector2[] positions = new Vector2[4]
{
new Vector2(0,0),
new Vector2(1,0),
new Vector2(0,1),
new Vector2(1,1)
};
//튜플로 그래프 구성
//(이동할 노드, 드는 비용)
List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];
for (int i = 0; i < n; i++)
{
graph[i] = new List<(int to, float cost)>();
}
//비용 정보 추가
graph[0].Add((1, 1)); // A->B 1
graph[0].Add((2, 4)); // A->C 4
graph[1].Add((2, 2)); // B->C 2
graph[1].Add((3, 6)); // B->D 6
graph[2].Add((3, 3)); // C->D 3
//G 점수 배열 초기화
float[] gScores = new float[n];
for (int i = 0; i < n; i++)
{
gScores[i] = float.MaxValue;
}
//시작지
gScores[startIndex] = 0;
//방문여부 저장 배열
bool[] closed = new bool[n];
//오픈 리스트, 탐색 대상들
var openList = new List<AstarNode>();
//시작 지점 추가!
//float h = 휴리스틱 추가
openList.Add(new AstarNode(startIndex, positions[startIndex], 0,
Heuristic(positions[startIndex], positions[goalIndex])));
while (openList.Count > 0)
{
//f값 기준 정렬
openList.Sort((a, b) => a.CompareTo(b));
//가장 F 낮은 노드 찾기
var current = openList[0];
//방문 노드 제거
openList.RemoveAt(0);
//이미 방문한 노드면 패스
if (closed[current.Index])
{
continue;
}
//방문처리
closed[current.Index] = true;
//목표 도달시 경로 복원
if (current.Index == goalIndex)
{
var path = new List<int>();
var temp = current;
while (temp != null)
{
path.Add(temp.Index);
temp = temp.Parent;
}
path.Reverse();
Debug.Log("Astar Path" + string.Join(" -> ", path));
Debug.Log("Distance: " + current.G);
break;
}
//인접 노드 탐색
foreach (var neighbor in graph[current.Index])
{
if (closed[neighbor.to])
{
continue;
}
//현재의 G + 이동 비용 계산
float t = current.G + neighbor.cost;
//더 짧은 경로 발견 시 갱신
if (t < gScores[neighbor.to])
{
gScores[neighbor.to] = t;
//H값 계산
float h = Heuristic(positions[neighbor.to], positions[goalIndex]);
//새 노드 추가
openList.Add(new AstarNode(neighbor.to, positions[neighbor.to], t, h, current));
}
}
}
}
}
마무리
새로 배운 알고리즘, 디자인 패턴을 공부할 때가 가장 재밌다.
다만 응용할 방법을 떠올리기 아직 어려울 때가 많은데
이번 프로젝트에서 지금까지 추가적으로 배운 패턴 중
어떤 걸 사용하면 좋을 지 고민해보자.
안녕하시와요