득이공간
[게임 알고리즘] 1장. 길찾기 알고리즘의 이해 본문
해당 게시물은 이득우 교수님의 '꼭 배워야하는 게임 알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.
📌 목차 - 1장. 길찾기 알고리즘의 이해
1-1. A* 길찾기 알고리즘의 이해
1-2. A* 알고리즘 구현
1-3. A* 알고리즘 최적화
📌 1-1. A* 길찾기 알고리즘의 이해
* A* 알고리즘의 개발
- 1968년도 SRI(Standford Research Institute)에서 개발
- 모바일 자율 주행 로봇 Shakey 프로젝트의 일환으로 고안
* Dijkstra 알고리즘
- 1959년에 발표
- 그래프의 모든 경로를 탐색하고 최적의 경로를 계산
* A* 알고리즘
- Dijkstra 알고리즘에서 휴리스틱을 활용해 메모리 사용 및 검색 속도를 개선
- 휴리스틱(Heuristic): 경험적 지식을 활용해 답을 구하는 방법
* A* 알고리즘 동작 원리
- f(n) = g(n) + h(n)
- f: 최종값, g: 경로값, h: 휴리스틱 예측값
* 휴리스틱의 설정
- 일반적으로 목적지까지의 최단 거리로 설정
- 휴리스틱을 통해서 다양한 상황에 대해 유연하게 대처할 수 있다.
* A* 알고리즘 응용
- 장애물이 있는 격자(Grid) 맵에서의 최단 경로 탐색
📌 1-2. A* 알고리즘 구현
* A* 알고리즘 구현 방법
- 오픈 셋(Open Set)과 클로즈드 셋(Closed Set)의 두 가지 컨테이너를 준비한다.
- 오픈 셋에는 가중치를 계산할 노드를 관리한다.
- 클로즈드 셋에는 앞으로 더 이상 계산하지 않는 노드를 취합한다.
* A* 알고리즘 구현 과정
1. 시작 노드를 오픈 셋에 추가
2. 오픈 셋에서 가장 낮은 값을 가지는 노드 선택 - 동일한 값을 가졌을 때 우선 순위 규칙 지정 (ex. 순서, h(n)의 값)
3. 해당 노드의 이웃 노드를 오픈 셋에 추가 - 중복 점검(클로즈드 셋), 막힌 곳 제외, g(n)과 h(n) 값 계산, 각 이웃노드에 전임자 노드 정보 포함
4. 해당 노드는 클로즈드 셋으로 이동
5. 2~3번 반복 - 이웃 노드 추가 시 값이 오픈 셋에 이미 존재할 때는 더 작은 값으로 업데이트
6. 완성된 클로즈드 셋을 뒤집으면 최단 길찾기 경로 완성
📌 1-3. A* 알고리즘 최적화
* A* 알고리즘 구현을 위한 오픈 셋에서의 활동
1. 최소값 검색
2. 최소값 제거
3. 중복 노드 확인
4. 새로운 노드 추가
5. 중복 노드 수정
* 최소값 검색 -> 우선 순위 큐(Priority Queue) 컨테이너
- 항상 가장 작은 값이 처음에 위치해 있으므로 한 번에 가장 작은 노드를 찾을 수 있다.
* 우선 순위 큐의 구현
- 두 개의 가지로만 구성된 트리 구조인 이진힙(Binary Heap) 구조로 구현
- 이진힙의 내부 데이터는 배열로 구성되어 있다.
* 부모 노드를 찾는 공식
- 특정 인덱스의 부모 인덱스
- pi = (ci - 1) / 2
* 이진힙 값 삽입 과정
1. 새로운 값을 배열의 마지막에 추가
2. 부모인덱스와 값 비교 후 위치 수정 - 위치 교체 시 새로운 부모 노드와 비교 반복
* 이진힙 값 삭제 과정
1. 맨 앞의 값을 제거
2. 맨 뒤의 값을 루트로 이동
3. 자식(둘 중 작은 자식) 인덱스와 값 비교 후 위치 수정 - 위치 교체 시 새로운 자식 노드와 비교 반복
* 리스트와 이진힙 구조의 비교
- 리스트는 분산된 메모리 블럭을 사용하고 이진힙은 메모리가 한 데로 모아진 배열로 구현 가능하다.
- 실제 성능 비교는 벤치마크 비교를 통해 검증해야 한다.
