AstarAlgorithm

UserPreferences

1. 개요
2. 최적화
1. 검색 공간 최적화
2. Open/Closed 리스트 최적화
3. 경로 보완
4. 기타 최적화
3. 링크

1 개요

가장 유명한 노드 방식의 길찾기 알고리즘.

일반적인 예제는 8 방향의 움직임을 기초로 한 것들이 대부분이지만, 사실 방향과는 별 관계가 없다. 임의의 노드가 이어져 있는 다른 노드를 찾을 수 있는 구조(그래프!)만 되어 있다면, 어떤 자료 구조에도 적용할 수 있다. 이에 관한 사항은 SearchSpaceRepresentation 페이지에서 다룬다.

2 최적화

2.1 검색 공간 최적화

일단 검색할 노드들의 숫자를 줄이는 것이 가장 먼저 해야할 일이다. 계층형 검색 공간을 만드는 것이 이 범주에 속한다.



2.2 Open/Closed 리스트 최적화

경로를 검색하는 동안, Open 리스트에서는 포함여부체크/삽입/삭제/베스트노드선택이 일어나고, Closed 리스트에서는 포함여부체크/삽입/삭제가 일어난다.


• 임의의 노드가 Open/Closed 리스트에 들어있는가 판단하는 포함 여부 체크 문제는 노드 자체에다 bool 변수 2개를 둠으로서 간단히 해결할 수 있다. 다만 이렇게 하면 여러 스레드에서 같은 그래프에 대해 동시에 길찾기를 수행하는 것은 어려워진다.
  
• Open 리스트에서 베스트 노드를 뽑아내는 데에는 힙을 이용한 우선 순위 큐를 이용하는 것이 좋다.
  
  

2.3 경로 보완

검색 공간이 그리드 기반인 경우, 에이전트의 움직임이 45도 단위로 제한된다. 탁 트인 공간에서, 사람 눈으로 보기에는 직선으로 이동하는 게 자연스러워 보이는데, 에이전트는 쓸데없이 방향을 바꿔가며 구불구불하게 움직인다. 이를 해결하기 위해서는 중간에 거치는 필요없는 노드들을 날려야 한다.

필요없는 노드를 판단하는 것은 비교적 간단한 일이다.


1. V0, V1, V2로 이루어지는 경로가 있다고 하자.
   
2. V0 -> V2 사이를 잇는 직선 상으로 에이전트가 움직일 수 있는지 체크한다.
   
3. 이동할 수 있다면 V1 노드를 패스에서 제거하고, V0, V2, V3를 검사한다. 직선으로 이동할 수 없다면 V1, V2, V3를 검사한다.
   
   
이런 식으로 전체 노드를 최적화하면 구불구불한 움직임을 최소화할 수 있다. "직선 상으로 바로 이동할 수 있는가"에 대한 체크는 간단하게 하자면 line of sight 문제라고 볼 수 있다. 다만 에이전트의 크기가 제각각인 경우에는 단순히 line of sight만으로는 모자라므로 추가적인 체크가 필요하다.

네트워크 게임 같은 경우에는 방향이 바뀔 때마다 주위에 이를 알려야 하는데, 방향이 바뀔 일도 적어지는 부수 효과가 있다.



2.4 기타 최적화

• 타겟의 위치가 약간 변경되었다고 해서, 매번 경로를 새로 찾을 필요는 없다. 타겟이 마지막 위치에서 별로 멀어지지 않은 경우에는 원래 경로를 통해 마지막 위치까지 이동한 다음, 새로 경로를 검색해도 된다. (물론 순간순간의 타이밍이 중요한 게임의 에이전트, 예를 들어 FPS 게임의 에이전트 같은 경우에는 무리일 수도 있다.)
  
• 목표 지점까지 가는 길을 반드시 찾아야 할 필요가 없을 수도 있다. 어느 정도 이상의 노드가 오픈 리스트에 들어갔다. 시작 지점에서 어느 정도까지 멀어졌다. 길찾기를 시작한 후 얼마만큼의 시간이 지났다. 이런 조건들을 이용해 그냥 루프에서 빠져나와 현재까지 구성한 패스를 반환하는 방법도 있다. 목표 지점까지 반드시 찾아간다는 것은 보장하기 어렵지만, 검색 공간이 엄청 복잡하지 않은 경우, 어느 정도 맞아떨어진다.
  
• 길찾기에 부여할 CPU 시간이 모자란 경우에는 시분할 방식의 알고리즘도 생각해 볼 수 있다. 다만 이렇게 되면 에이전트의 움직임 처리가 비동기 방식과 비슷해지기 때문에 코딩하는 게 좀 귀찮아진다. 또한 한번에 모든 경로를 찾는 것이 아니기 때문에 처음에는 잘못된 길로 가다가, 시간이 좀 지나서야 제대로 된 경로로 움직이는 현상이 발생할 수도 있다. 대신 반응성은 확실히 증가한다. RTS류의 게임에서 이런 방식을 많이 선택하는 걸로 알고 있다.
  
  
  

3 링크

• Amit’s Game Programming Information > Shortest Paths
  
• Micro Pather
  
• A* Pathfinding for Beginners
  
• Two-Tiered A* Pathfinding
  
• Using Binary Heaps in A* Pathfinding
  
• Heuristics and A* Pathfinding
  
• A* algorithm implementation in C#
  
  
• Gamasutra > Pawn Captures Wyvern: How Computer Chess Can Improve Your Pathfinding
  
IDA* (Iterative Deepening A*) 알고리즘에 대한 소개.
재귀 호출하면 스택 오버플로우 일어나지 않나? Transition Table은 또 어떻게 구성해야하나? 나중에 다시 한번 읽어보자.

• see also PathFinding
  

• CategoryAlgorithm, CategoryAiProgramming