It might be worthwhile to explore what this blogpost is going to be about and more importantly, what it's not going to be about. If you're like me, you probably skim documents like this to see if there's anything in here that can help you with your particular problem. So I hope this here paragraph saves you some time.
I'm going to talk about pathfinding for a small squad of agents (4 agents to be precise). I'm going to assume you already have some sort of pathfinding in place for a single agent and have the means to smooth out that particular path.
When talking about group pathfinding, flocking comes to mind, and while that is certainly the desirable solution when your squad size is > 10, I find that it rarely works right out of the box and requires a LOT of manual tuning. It's also important to note that the solution I present here works reasonably well in my particular case and there is no guarantee that this is an optimal solution for your problem. It's also (like most "solutions" in game development) a bit of a hack..
Let's jump right in.
The problem
My problem is the following: I have four agents moving about in 3-Dimensional space.
Let that soak in for a moment.
What I don't have is 4 agents moving about in a 3D environment, constrained on a 2D plane. That is, of course, a big difference. Most RTS games work on a 2D level instead of the perceived 3 dimensions. Think birds flying up to a branch or a spaceship avoiding asteroids instead of little soldiers walking on a grassy meadow.
My implementation is done in Unity, and because I'm doing pathfinding in 3D (and have no money for a pro-license), I implemented my own 3D A* algorithm supported by a binary heap for speed and a path-smoothing engine to make everything look nice. If that sounds like chinese to you, go back and make sure your game allows a single agent to move smoothly through a constrained environment.
Another important detail is that the agents wil always end up "grounded". This means that an agent can not end its move midair, but can 'fly' up to its destination.
This is not supported by the code: an agent is perfectly happy ending its move midair. Instead, the user is unable to select positions that are not grounded in some way. This is a problem when selecting a pinpoint target that can only support one agent: if four agents are selected, they will flock around this pinpoint, sitting lazily on absolutely nothing. Then again, the pinpoint only supports one agent, so what do we expect to happen when we select all four agents at once and command them to go sit on the pinpoint?
As I mentioned before, I'll be moving the four agents independently using pathfinding instead of using flocking. The solution presented here doesn't solve all the problems that come with group pathfinding but I'm hoping to adress those in a later blogpost. Every agent will try to find a position close to the goal that is a valid position (i.e. the position is not midair and far enough from the other agents to avoid intercollisions).
Let's talk about how we can do that.
The solution
When solving any problem: start small and work your way up. So let's start by looking at 2 agents and work our way up from there. In the ideal case (which is going to happen the most of the time. Yay.) the agents will end side-by-side next to the intended goal (see figure 1).
 |
| Figure 1: 2 Agent position relative to the goal position |
You know what? Let's implement that right away:
public void moveGroup(Agent[] agents, Vector3 position)
{
//No agents? what are we doing in this method?!
if(n == 0)
return;
if(n == 1)
{
//Just walk to the intended point
agents[0].walkTo(point);
}
else if(n == 2)
{
Vector3 direction = position - agents[0].transform.position;
//We want a vector that is constrained to the x,z plane
direction.y = 0;
direction.Normalize();
//Apply vector magic
direction = Vector3.Cross(Vector3.up, direction);
Vector3 goalPoint1 = position + direction * 5;
Vector3 goalPoint2 = position + direction * -5;
agents[0].walkTo(goalPoint1);
agents[1[.walkTo(goalPoint2);
}
By using some vector magic, we end with a vector that is somewhat perpendicular to the direction the agents came from. We use this vector to calculate the goal position for each agent. That's great, we have what we want, but now there are a lot of additional cases that aren't covered by this code. The agents are assigned a position without checking if that position is valid. So let's add a check for that:
private bool isValidPosition(Agent agent, Vector3 position, Vector3[] takenPositions)
{
for(int j = 0; j < takenPositions.Length; j++)
{
float dist = Vector3.Distance(position, takenPositions[j]);
//Not to close to a position taken by another agent?
if(dist < agent.maxProximityToOtherAgents)
return false;
}
return agent.isGrounded(position);
}
isGrounded(Vector3 postion) checks to see if the position is close enough to some sort of floor. For the pseudo code, this function is part of the agent because we base our decision on the dimensions of the agent. We also need to keep a minimum distance from other agents, so we supply the function with an array of goal positions that are already assigned to different agents. Note that these are not the positions currently taken by the agents but rather the goal positions that have been assigned to different agents.So what do we do if one of the positions is invalid? Simple: we're going to try and find another one that is close to the goal, yet valid. The algorithm used iteratively checks to see if there's a better alternative. Let's go over it in detail:
public void moveGroup(Agent[] agents, Vector3 point)
{
//Determine the goalPoint based on the number of agents
int n = agents.Length;
if(n == 0)
return;
else if(n == 1)
{
//goalPoint == point
agents[0].walkTo(point);
}
else if(n == 2)
{
Vector3 direction = point - agents[0].transform.position;
direction.y = 0;
direction.Normalize();
direction = Vector3.Cross(Vector3.up, direction);
Vector3 goalPoint1 = findPosition(agents[0], point, direction, 5, 10, new Vector3[0]);
Vector3[] takenPositions = {goalPoint1};
Vector3 goalPoint2 = findPosition(agents[1], point, -direction, 5, 10, takenPositions);
agents[0].walkTo(goalPoint1);
if(goalPoint2 != Vector3.zero)
{
agents[1].walkTo(goalPoint2);
}
}
}
private Vector3 improvePosition(Agent agent, Vector3 position, Vector3 direction, float length, int iterations, Vector3[] takenPositions, float proximity)
{
Quaternion quat = Quaternion.AngleAxis(360/iterations, Vector3.up);
for(int i = 0; i < iterations; i++)
{
direction = quat * direction;
Vector3 goalPos = position + (direction * length);
if(isValidPosition(agent, goalPos, takenPositions))
return goalPos;
}
return position;
}
private Vector3 findPosition(Agent agent, Vector3 goal, Vector3 direction, float length, int iterations, Vector3[] takenPositions)
{
float prox = agent. maxProximityToOtherAgents;
//PLAN A
Vector3 goalPosition = goal + direction * length;
if(isValidPosition(agent, goalPosition, takenPositions))
return goalPosition;
goalPosition = improvePosition(agent, goal, direction, length, iterations, takenPositions, prox);
if(isValidPosition(agent, goalPosition, takenPositions))
return goalPosition;
//PLAN B
foreach(Vector3 v in takenPositions)
{
goalPosition = v + direction * length;
if(isValidPosition(agent, goalPosition, takenPositions))
return goalPosition;
goalPosition = improvePosition(agent, v, direction, length, iterations, takenPositions, prox);
if(isValidPosition(agent, goalPosition, takenPositions))
return goalPosition;
}
return Vector3.zero;
}
For the first agent this algorithm works as follows:
The first step is to see if the initial position is a valid one, If it is, we can stop and return the result.
If not, we use the direction vector used to calculate the original position and rotate it around the goal position in small increments until we do find a valid position. If no such position exists, we are shit out of luck and return the intended goal position instead (we are certain this is a valid position because the user can only target valid positions to begin with). This is for example the case with the pinpoint position: it only supports one agent on the intended position. An unanswered question so far is what to do with the second (or third, or fourth) agent int that case.
For the second agent the algorithm works exactly the same but also checks against the goal position awarded to the first agent to see if they don't overlap. In case no valid position is found, we repeat the process but instead of checking against the intended goal, we repeat the check against the first agent's goal position. This makes sure the agents can maneuver into a corner (see figure 2).
 |
| Figure 2: No valid position can be found for the second agent, so we attempt to find one based on the position of the first agent rather than the goal position. Even then, our first attempt at a position fails before finding a valid position. |
We can extend this algorithm to deal with three, four or even five or six agents. Any higher and you're probably better off with flocking. Let's look at the ideal case again, this time for three agents:
 |
| Figure 3: The ideal case for 3 agents. |
public void moveGroup(Agent[] agents, Vector3 position)
[
...
else if(n == 3)
{
Vector3 direction = point - agents[0].transform.position;
direction.y = 0;
direction.Normalize();
Vector3 normalDirection = new Vector3(direction.x, direction.y, direction.z);
Vector3 goalPoint1 = findPosition(agents[0], point, direction, 5, 10, new Vector3[0]);
Vector3[] takenPositions = {goalPoint1};
direction = Vector3.Cross(Vector3.up, direction);
Vector3 goalPoint2 = findPosition(agents[1], point, direction - normalDirection, 5, 10, takenPositions);
Vector3[] takenPositions2 = {goalPoint1, goalPoint2};
Vector3 goalPoint3 = findPosition(agents[2], point, -direction - normalDirection, 5, 10, takenPositions2);
agents[0].walkTo(goalPoint1);
if(goalPoint2 != Vector3.zero)
{
agents[1].walkTo(goalPoint2);
}
if(goalPoint3 != Vector3.zero)
{
agents[2].walkTo(goalPoint3);
}
}
}
The code works exactly the same as before, only this time, there's a possibility that the third agent will check against the goal positions assigned to the first and second agent in order to improve its position. Again, the issue regarding what to do when no valid position can be found, remains unanswered, and indeed, is even more prevalent here (and even more so in the case of four agents). One possible solution can be to try again with a higher number of iterations or increase the distance from the goal. However, this is only a good idea if you're certain such a valid position exists, if not, this can slow down your game quite a bit.
We can extend to four agents in a straightforward manner.
Conclusion
The solution presented here attempts to iteratively improve the position of the agent until a valid position is found. What exactly constitutes a valid position is entirely up to you. I also doubt this solution is the best when all you want is squads moving in a certain formation all the time in a 2D plane. We're not trying to preserve any kind of formation, we just use a formation as a starting position to determine the ultimate goal positions for each agent.
A few open issues remain that I hope to solve in the future:
- What do we do if no valid position can be found?
- How do we fit each agent to the best goal positon that is found so that the agents don't cross each other's paths when trying to reach that goal?
- In my current system, there is a high probability of inter-agent collision. I need to fix that at some point
Geen opmerkingen:
Een reactie posten