BOIDS (군중 알고리즘) RTS AI

스타크래프트의 하이브리드 최적 경로

마이크로 관리는 RTS 게임의 가장 중요한 기능이다. 싱글 유닛 또는 한 그룹의 유닛을 드래그해서 선택을 하여 적을 공격하게끔 하는 것이며 이러한 AI 기능은 구현하고자 할 때 큰 골치거리다.

두 가지의 구현 방법이 있다.

1. 퍼텐셜 필드 알고리즘 : 목표점으로 이끄는(attractive) 인공적인 포텐셜 필드와 장애물로부터 멀어지게 내보내는(repulsive) 인공적인 포텐셜 필드를 형상공간에 구축하는 알고리즘.
2. 군중 이동 알고리즘 : 군중 이동(새 떼라던지 물고기들의 움직임 등 여러 집단이 함께 움직이는)에 대한 알고리즘.

 

게임 유닛들의 내비게이션은 주로 A*와 같은 최단 경로 알고리즘을 사용한다. 하지만, RTS와 같이 월드가 수시로 변화하는 게임에는 적합하지가 않다. 예로 들어서) A 지점부터 B 지점까지 목표를 설정했다고 가정하고 가는 도중 갑작스럽게 무언가가 가로막는다면 최적 경로를 재설정하여 목표를 재설정 해야만 한다.

 

GLEST 현재 오픈소스 게임, 하이브리드 최단 경로 알고리즘 적용의 모습을 보여준다.

 

A* 알고리즘은 유닛을 대기시키기 위해선 매우 부적합하다 따라서 경로를 지정할 땐 A*, 어느 정도 시야의 들어왔을 때 군중 적용.

 

 

건물 피격 지점으로부터 거리가 멀기 때문에 가까이 가야한다, 따라서 유닛은 빈 공간을 찾아서 간다던지 유닛들이 살짝 움직여서 해당 위치에 들어가는지가 중요하다.

 

 

 

퍼텐셜 필드 해결 방법도 유사하다, 경로를 찾기 위해선 A*, 대기시키기 위해선 군중 대신 퍼텐셜 필드를 사용한다.
퍼텐셜 필드에는 각 오브젝트마다 자기 자신을 감싸는 필드를 생성한다 각 필드는 크기가 상이할 수 있으나 0이 아니어야 한다. 양극 필드는 유닛을 끌어당기며, 음극 필드는 밀어내고 있으며, 0은 영향을 주지 않는다. 모든 생성된 필드들은 계산된 후 합한 값이 총 퍼텐셜 필드 값이며 유닛 대기 위치 지정을 하기 위해 사용된다.

 

 

퍼텐셜 필드는 음각을 사용해 적으로부터 후퇴하기 위해 사용된다, 빨간 점이 적이고, 덜 어두운 곳이 어두운 곳보다 더 밀어내고 있다.

 

군중 알고리즘 구현

모든 유닛들은 스쿼드로 구성되어 있다, 스쿼드는 아무 수의 유닛을 가질 수가 있으며 총 6개의 원칙이 있다.

1. 응집도 (Cohesion)

스쿼드의 멤버들은 같이 있는 게 중요하다, 만약에 홀로 있다면 적에겐 쉬운 사냥감이 되고 말 것이다. 각 유닛들은 다른 유닛들의 평균 위치를 가지고서 움직인다.

function ApplyCohesion(Agent a)
{
foreach (Agent o in squad.Members())
{
if (o.ID != a.ID)
{
dX += o.Position().x();
dY += o.Position().y();
}
}
dX = dX / (squad.Size() - 1);
dY = dY / (squad.Size() - 1);
a.dX += (dX - a.Position().x()) / 100;
a.dY += (dY - a.Position().y()) / 100;
}

2. 일렬로 움직임 (Alignment)

각 그룹들은 공통적인 목표 지점으로 향해서 같은 위치로 움직여야 한다 따라서 각 유닛들은 다른 유닛들의 평균 목표 지정 값/방향 값을 가지고 움직인다. 응집도와 같이 상대적으로 중요도가 낮다.

function ApplyAlignment(Agent a)
{
foreach (Agent o in squad.Members())
{
if (o.ID != a.ID)
{
//Heading is in radians
dX += cos(o.Heading());
dY += sin(o.Heading());
}
}
dX = dX / (squad.Size() - 1);
dY = dY / (squad.Size() - 1);
a.dX += (dX - cos(a.Heading()) / 5;
a.dY += (dY - sin(a.Heading()) / 5;
}

3. 목표 (Goal)

각 유닛들은 어디로 이동할지 총괄하는 유닛이 있다. 각 유닛들은 목표 지점으로 향하며 이는 대부분 A* 알고리즘으로 구현이 되어있다.

function ApplyGoal(Agent a)
{
int goalX = squad.Goal().x();
int goalY = squad.Goal().y();
a.dX += (goalX - a.Position().x()) / 100;
a.dY += (goalY - a.Position().y()) / 100;
}

4. 흩어짐 (Separation - Own Agents) 현재 쓰여지는 유닛들

유닛들은 다른 유닛들과 충돌하지 말아야 하며 짧은 거리를 유지해야 한다, 최대 충돌 감지 거리는 유닛의 반경과 피하고자 하는 유닛의 반경+2로 구한다. 만약에, 그룹이라면 이 거리를 늘리기만 하면 된다.

function ApplySeparationAgents(Agent a)
{
foreach (Agent o in squad.Members())
{
float detectionLimit = a.Radius() +
o.Radius() + 2;
if (o.ID != a.ID)
{
float distance = a.DistanceTo(o);
if (distance <= detectionLimit)
{
dX -= (o.Position().x() -
a.Position().x());
dY -= (o.Position().y() -
a.Position().y());
}
}
}
a.dX += dX / 5;
a.dY += dY / 5;
}

5. 흩어짐 (Separation - Enemy Units) 적 유닛들

가장 중요한 사안이다, 목표는 타깃이랑 피격 판정 거리를 일정하게 유지하는 것이다. 이를 계산하는 것은 상황마다 달라진다.

• 만약에 유닛이 적 공격이 가능하다면, 유닛의 무기 반경 거리 또는 사거리로 계산한다.
• 만약에 유닛이 적 공격이 불가능하고, 반대로 적이 가능하다면 적의 무기 반경 거리 또는 사거리 + 유닛의 반경으로 계산한다.
• 만약에 유닛이 적 공격이 불가능하고 또한 적이 유닛 공격이 불가능하다면, 유닛의 반경 + 10만큼 계산한다.

function ApplySeparationEnemy(Agent a)
{
foreach (Unit e in Enemies())
{
float detectionLimit = a.ShootDist(e);
if (a.IsSupport())
{
detectionLimit = e.ShootDist(a) + 5;
}
float distance = a.DistanceTo(e);
if (distance <= detectionLimit)
{
dX -= (e.Position().x() -
a.Position().x());
dY -= (e.Position().y() -
a.Position().y());
}
}
a.dX += dX;
a.dY += dY;
}

6. 흩어짐 (Separation - Terrain) 지형

유닛들은 또한 지형과의 충돌을 피해야 한다.

function ApplySeparationTerrain(Agent a)
{
WalkTile aWT = a.WalkTilePosition();
foreach (WalkTile tWT in aWT.Adjacent())
{
if (!tWT.IsWalkable())
{
float detectionLimit = a.Radius() + tWT.Width() / 2;if (distance <= detectionLimit)
{
dX -= (tWT.Position().x() -
a.Position().x());
dY -= (tWT.Position().y() -
a.Position().y());
}
}
a.dX += dX / 10;
a.dY += dY / 10;
}

실험 결과) 퍼텐셜 필드 알고리즘과 군중 알고리즘간에 차이

두 알고리즘간에 승률 차이는 별로 없다.

 

메소드 호출 차이는 유의미하게 나서 퍼포먼스에 영향을 끼친다.

 

맵이 커지고 플레이어 인원 수가 많을수록 퍼텐셜 필드의 퍼포먼스 저하는 더더욱 커진다.

 

https://www.youtube.com/watch?v=QbUPfMXXQIY 

 

관련 코드 : https://processing.org/examples/flocking.html

Flocking / Examples

참고 자료 : https://www.researchgate.net/publication/276906579_Hybrid_Pathfinding_in_StarCraft

https://drehzr.tistory.com/m/201