10. Tactical AI

 

지난시간

AI for an agent

• 하나의 AI를 컨트롤한다
• 센서, 메모리, 리즈닝코어(그 다음 액션 플래닝), 액션

AI for a strategy

• agent 를 위해서는 센서가 그 주변만 보면 된다
• 전략에서는 agent 전체, 전반적인 중간중간의 목적을 알아야함
• 중간중간 목표가 최종 목표에 기여하도록 짜야한다

agent 를 위한 것이 strategy 에 적용할 수 있을까?

• agent 에서는 순서적인 영향이 크지만 strategy는 순서를 설정하기 어렵다
• agent 로는 표현하기 어려운 부분을 strategy 에서 구현하는 것이다

 

---

Tactical AI

Tactic 의 정의

• 어떤 목표를 달성하기 위해 해야하는 operation 들의 순서 sequence
• 요소
  • 초기 상태(initial state)
  • 목표 상태 (goal state)
  • 전환 계획 (transition plan)
• 어떤 상태에서 어떤 상태로 갈 수 없게 되면 plan을 바꿔주어야 한다.
  • state machine 에서는 이런 것이 분기로 발생했지만, strategy 에서는 그렇지 않기때문에 FSM 같은 방법으로는 표현하기 어렵다
• plan을 어떻게 잘 짜는지가 중요하다

 

---

Plan을 만들기

상황을 이해한다

• 처음에 무엇을 할지 정해야 한다
• 적이 어떤 전략을 세우고 있는지 확인한다 → 이후 수정
• 정찰이 중요하다. 상대의 상태를 잘 파악해야 한다

실제 계획Actual Plan을 만든다

• 모든 수를 다 바라보도록 plan을 짜기는 어렵다
• 5~15 수 정도만 내다보면서 가장 좋은 plan을 택한다
• 어떤 plan이 좋은지를 판단하는 기준이 중요하다
  • 지금은 10만큼 오르지만 이후에 20만큼 내려간다면 좋은 플랜이 아니다!
• 장기적인 전략을 세워야 한다

 

---

Case by case 로 전략을 디자인하기

1. Path Finding

• 목적 : 어떤 객체를 타겟 포지션까지 이동시킨다. 장애물을 피하면서! (ex: 미로찾기)

2가지 방법

• locally : 무조건 오른쪽으로!
  • 비효율적. 단순하지만 갈 수있는 길도 못찾을 수 있다.
  • 길이 없을 때 백트래킹이 필요하다
• globally : 출발하기 전에 미리 최적의 경로를 다 찾아놓고 출발한다
  • 효율적이다
  • 계속해서 변동되는 정보가 있다면 좋지 않다
  • 실제로 맵 전체를 알고 있어야 한다 but 실제 FPS 게임 같은 것에서는 주변 정보만 알고 있다

Local Strategy : Crash and Turn

• 보일때까지 한 방향으로 계속 이동한다

단계

1. line : 목표까지 가장 짧은 경로를 찾는다
2. 그 경로 방향으로 이동한다
3. 충돌한다면 충돌한 지점에서 충돌벽면에 가장 가까운 각도 방향으로 회전한다→ 랜덤하게 방향을 정하도록 할 수도 있다!
4. → 이렇게 설정한 방향에 장애물이 있을 경우 이동하지 못한다
5. 다시 2번으로 돌아가 이동을 반복한다 or 1번으로 돌아간다

장점

• Local하게 갈 수 있다
• 서로 연결되지않은 convex 물체들 사이에서는 잘 동작한다 (미로찾기)

단점

• 더 간단하게 갈 수 있는걸 돌아갈 수도 있다.
• concave한 장애물이 있으면 제대로 동작하기 어렵다
• 초창기 게임에서 썼었다. RPG에서 맵 구석에 몬스터가 몰려있는 경우가 생길 수 있다

---

 

Global Strategy

1. Dijkstra’s Algorithm

• 거리를 edge들로 표현해야 한다
• 미리 계산한다
  • 내가 갈 수 있는 경로를 각 오브젝트의 Edge들을 생성해서 맵을 만든다
  • Room (Position) , Corriors(path) 로 나누어 표현한다
• 실시간에서는
  • 이 다익스트라 알고리즘으로 계산된 값만을 기반으로 경로를 짠다

구현방법

• 각 노드의 정보들을 저장한다
  • 가장 가까운 노드에 대한 정보를 저장한다. 그 직전 노드의 값도 저장한다
• 모든 노드들을 정렬된 리스트에서 빼낸다
• 하나씩 빼서 업데이트한다
• 장점
  • 최적의 경로를 구할 수 있다
  • 가능한 경로를 모두 계산할 수 있는 상황에서 좋다
• 단점
  • 계산량이 많다
  • 시작점, 끝점간의 관계만 계산하고 싶은 경우에는 비효율적이다
  • Exhaustive Search
    • 모든 가능한 경로를 다 봐야한다
    • 각 노드의 거리를 다 기록해야 한다
    • 그 중에서 최적 경로를 찾아서 선택해야 한다
    • 엄청 케이스가 많은 경우에는 서치할게 너무많다. 계산량이 너무많다. 억, 조단위로 가게되면 가짓수가 너무많아진다
  → 전체를 다 보는 것이 문제인 것!

2. A* Algorithm

• 시작점 - 골까지 갈 때 , 안보이는 곳에서 goal까지의 거리중에서 비교한다
• 특정 지점을 선택했을 때 다른 선택보다 좋아야 한다. 항상 짧아야 한다
• 가장 좋은 노드를 선택해가면서 노드들을 순회traverse한다
• 점수 매기는 기준
  • f노드까지 = g노드까지 + h노드
• 조건
  • h(node) ≤ g(decendent) - g(node) + h(desendent)
  • A→C 바로 가는게(1) A→B→C로 다른 노드를 추가로 들렀을 때(2) 보다 짧아야 한다
  • Express way : 2가 사실 지름길이다! 라는 경우는 있으면 안된다

→ 이 조건을 만족한다면 Admissible 하고 Optimal 하다고 할 수 있다!

• 많은 게임에서는 아직도 A* 를 쓴다. Express way 가 존재하면 어떡하지?

 

어떻게 구현할까?

• 얼마나 남았는지를 유클리드로는 예측하기 어렵다.(장애물때문에)
• 맨하튼 Manhattan distance 로 단계별로 목적지까지의 거리를 계산한다! 도로로
• 실제구현
  • 스타트 노드부터 연결된 노드들로 expand한다
  • 그때의 heuristic 과 거리를 갱신한다
  • 더 짧은게 존재하면 더 짧은 거리로 정렬해서 노드를 넣는다
• 장점 : 일반적인 알고리즘
• 단점
  • 장애물이 동적으로 변하는 경우
  • optimal 방법으로는 부자연스러워보일 수 있다
    • 휴리스틱, 골을 잘 잡는것이 중요하다
  • 계산량이 많다
    • 우선순위, 거리 값들을 계산해야한다
    • 업데이트될때마다 다 갱신해야한다
• A* 를 잘라내서 일부 노드에 대해서만 쓰는 방법을 많이쓴다
• → Region-based A*

+heuristic

• 예측하기에 정보가 부족할 때 그 상황에서 간편하게 추리하도록 하는 방법

 

Region-based A*

• 장애물이 많은 지점 등을 피해서 큰 틀에서 갈 공간을 정한다간
• 해당 공간에서 local알고리즘으로 이동한다 (공간 안은 좁기 때문에 A* 등을 쓸 수 있다)

Iterative-Deepening A*

• 전체 노드를 보지않고 다음 노드만 본다
• 무조건 최적이진 않지만 메모리를 적절히 쓰면서 그럴듯하게 만들 수 있다

 

---

Final Notes

• 사람은 길을 어떻게 찾을까?
  • 큰 글로벌한 경로를 설정한다 (역으로가서 2호선타고, 내려서 건물까지 걷는다!)
  • 상황에 맞게 로컬한 경로로 이동한다 (세부적인 장애물을 피한다)
• 사람의 방식에 맞게 알고리즘을 짤 수 있다
• Limitied view (A* 변형해서 쓴다)
  • 크게 경로를 잡았을 때 현재 보이는 부분에 대해서만 경로를 짠다
• Group moving
  • 전략 게임에서 유닛들이 서로 부딛히지 않도록 움직이게 한다
  • (애니메이션 파트에서 좀더 다뤄보자)

 

---

Group Dynamics

• 그룹이 있을 때 각 유닛이 움직일 때 서로 부딛히거나 장애물을 피하는 경우들을 처리해줘야 한다
• 컴퓨터 애니메이션 방면에서 많이 연구된다
• 집단이 있을 때 잘 움직이게 하기 위함

Boids algorithm

• 새,물고기의 움직임을 기반

Agent 들의 행동 경향 Force

• 그룹 내의 각 에이전트는 3가지 경향을 가진다

1. separation : 다른 유닛이랑 너무 가까우면 좀 멀어지려고 한다. 거리를 균등하게 하려고한다
2. alignment : 다른 유닛들이 움직이는 방향을 따라 회전하는 경향이 있다 (속도나 이런건 다르게 할 수 있다)
3. cohesion : 혼자떨어져있으면 다른 유닛들이 많은 방향으로 붙으려고 한다

• 타겟으로 가기 위한 velocitiy 는 아래 요소들의 합으로 구성된다
  • 목표로 가기 위한 방향의 힘
  • 3가지 규칙에 의해 결정되는 velocities

---

Analyzing the Scenario

• 지금까지는 지능을 가진 경우였다. 이제는 어떤 시나리오에 따라 다르게 행동하는 전략을 짜보자
• 지금 우리 팀이 지고있는지, 이기고 있는지에 따라 행동하게 한다

Influence map

• 하나의 개체가 가지는 영향력을 표현한다. 개체의 속도, 힘과 범위 등을 표현한다.
• 어떤 범위 내에 들어갔을 때 나의 힘이 3, 지금 영역 개체의 힘이 1이라면 나는 유리하다고 판단한다
• 방법
  • 0인 경우가 전선이라고 하는 zeropoints. boundary 가 생긴다
  • maxima : 가장 숫자가 높은 곳에 몬스터가 많을 것이다
    • 내가 높은 숫자라면 나보단 낮은 가장 높은 적을 공격하는 것이 이득이다!
  • 따로 떨어진 개체들을 먼저 잡는다
• 값을 가진 2차원 배열

알 수 있는 경우 Possible Test

• 경계점을 찾아낸다. 그를 통해 누가 유리한지
• 포위된 컴포넌트가 많으면 빠르게 연결해서 구출한다
• 적이 가장 약한 지점을 찾는다. (또는 나의 약한 지점)
• maxima 가 튀어나오면 거기로 공격하고 있다는 것을 꺠달을 수 있다
• minima가 있다면 그 지역을 안전하다고 판정한다

활용법

• 이런 맵을 기반으로 공격할 때, 내가 세다면 본진을 공격한다
• 적이 공격해올 때 나의 본진, 약한 지점을 보호한다
• 상대의 약한 지점을 판단하고 그 방향으로 공격한다

→ 이런 판단을 위한 근거가 된다

 

 

---

Tactics

• 시나리오를 모두 analyze 햇으면 이제 plan을 짜야한다
• two layer approach
  • Rule-based / FSM
• 예시
  • time counted → rule
    • 상대의 타임이 얼마 남지 않았다면?
    • 내가 유리할 때 → 적이 고립되어있는지 등등

 

---

정리

• tactical AI 는 전체적인 게임의 상황을 변화시킬 수 있는 전략을 짜야 한다
• Global AI
• path finding
• situation analysis
• tactics