Unit Movement
Before anything else, I'd like to link the resources I've used to assist me in implementing these systems. I stand on the shoulders of giants.
Maestro's Devlog on Movement/Pathfinding
This devlog has been in the works for quite some time. I wanted to share it after developing two key systems that are essential for the movement in an RTS game: Unit Avoidance and Unit Pushing.
Outline of topics for the devlog
- Navigation
- Movement States and Controller
- Group Movement
- Unit Pushing
- Unit Avoidance
1. Navigation
Let's dive in. This devlog will focus exclusively on ground units, as air units follow a different set of rules due not using a navmesh.
While there are various movement systems available for RTS games, given that we're using Unreal Engine 5, we'll leverage the tools at our disposal, particularly Unreal's Navigation Mesh. This allows us to integrate a volume into our game, covering the entire map. This volume determines the areas our units can navigate, and it provides the flexibility to dynamically adjust the navmesh when inserting actors that obstruct, such as buildings and resources.
The green sections on our map designate where our units are allowed to move. Leveraging our AIController, we can utilize built-in functions such as MoveToLocation, MoveToActor, and StopMovement. These functions will form the foundation for our custom XYZAIController.
There are numerous settings to tweak in the navmesh, including min agent radius, max agent height, size of tile grids, and more. These settings adjust the nav mesh pathing, but delving into the details is beyond the scope of this devlog.
After plopping down the navmesh and adding an AIController to our units we're freely able to move around the navmesh by calling AIController::MoveToLocation
Now that we have simple movement, the next step is to build a controller on top of these built-in functions. This controller will enable us to execute various movement actions for our units.
2. Movement States and Controller
Let's establish the states and actions that our units should be capable of performing.
enum class EXYZUnitState
IDLE,
MOVING,
ATTACKING,
ATTACK_MOVING,
FOLLOWING,
HOLD,
DEAD
I won't be covering a few more states related to our workers. If you wish to read up on those, check out Workers!
Now for our new XYZAIController
class AXYZAIController : public AAIController
void OnMoveCompleted(FAIRequestID RequestID, const FPathFollowingResult& Result);
virtual void XYZMoveToActor(class AXYZActor* Actor, float AcceptanceRadius = 1.0f);
virtual void XYZMoveToLocation(FVector TargetLocation, float AcceptanceRadius = 1.0f);
virtual void XYZFollowTarget(AXYZActor* Actor, float AcceptanceRadius = 1.0f);
virtual void XYZAttackMoveToLocation(FVector TargetLocation, float AcceptanceRadius = 1.0f);
virtual void XYZAttackMoveToTarget(AXYZActor* Actor, float AcceptanceRadius = 1.0f);
virtual void XYZStopMovement();
virtual void XYZHold();
void RecalculateMove();
Each of these functions in our controller will execute one of the built-in controller functions to move to a location or actor. Additionally, they will set our actor to be in the corresponding state.
Let's take a look at XYZMoveToActor
void AXYZAIController::XYZMoveToActor(AXYZActor* Actor, float AcceptanceRadius) {
GetXYZActor()->SetState(EXYZUnitState::MOVING);
MoveToActor(Actor, AcceptanceRadius, true, true, false); // Built in function of the base controller
I'm omitting a few lines that validate the function, but, in a nutshell, this is what all these controller functions are doing.
SetState -> MoveToActor/MoveToLocation/StopMovement
In its process function, the actor will check its current state and execute specific logic corresponding to that state.
3. Group Movement
Now, onto a trickier subject that I'm still fine-tuning: our Action system works off of the Blob System. A Blob is a group of units selected by the client and then given a common action to execute. So, imagine we have a Blob of Units, and they are all given the move command to an arbitrary location. What happens? Let's break out the paint!
As you can see, they will all move to that target spot. Since they can't all be at the exact same target location, they'll keep trying to move there and will not go idle. You may say, 'Just add some sort of check if they are stuck and then set them IDLE.' Yes, that would work, and I do have that implemented for extreme cases where something went wrong. However, we want a nicer scenario, and this will involve some simple vector math. Let's draw it out!
Instead of giving each unit in a blob the same target location, we will assign them a target location that is offset from the target location in relation to their starting center location. This way, once they reach their destination, the blob formation will be in the same relative position as when it started.
FVector ActorLocation = Agent->GetActorLocation();
FVector DirectonFromCenter = ActorLocation - CenterLocation);
FVector AgentTargetLocation = TargetLocation + DirectonFromCenter;
Much nicer than sending every unit to the same location!
However, there's a significant issue we need to address. What if the following occurs:
As you can see, if we have a bunch of spread-out units in our blob and issue them a move command, they will retain that very spread-out formation. This doesn't even include the issue that if one of the offset locations is on a different height, the unit will try to go up to that height as well.
So, what do we do? Well, we're going to do some inception here—groups inside groups!
Instead of issuing every unit in the group an offset location from the center of the entire group, the first thing we will do is group every unit in the blob. How do we find nearby units? Well, we take advantage of our MapManager. If you have read my Fog of War devlog, then you'll know I use this to keep track of all the units in the game via their position in a grid.
We will conduct a search for neighboring units that are 1 grid square away from the current one. And, of course, we will skip over any already in the group or units that are not in the blob."
void UXYZMoveAction::CreateAgentGroups(TSet<AXYZActor*> Agents)
if(Agents.IsEmpty()) return;
TSet<FIntVector2> SearchedCoords;
for (AXYZActor* Agent : Agents)
{
if (!AgentsWithGroup.Contains(Agent)
{
TSharedPtr<FAgentGroup> AgentGroup = MakeShared<FAgentGroup>();
AgentGroups.Add(AgentGroup);
TSet<AXYZActor*> ActorsToAdd;
ActorsToAdd.Add(Agent);
FindAndAddNeighbors(MapManager, Agent, AgentGroup, SearchedCoords, ActorsToAdd, Agents);
}
}
void UXYZMoveAction::FindAndAddNeighbors(UXYZMapManager* MapManager,
AXYZActor* Agent,
TSharedPtr<FAgentGroup> AgentGroup,
TSet<FIntVector2>& SearchedCoords,
TSet<AXYZActor*>& ActorsToAdd,
TSet<AXYZActor*>& AgentsInAction)
{
AgentGroup->AgentsInGroup.Add(Agent);
AgentsWithGroup.Add(Agent,AgentGroup);
FIntVector2 AgentGridCoord = Agent->GridCoord;
TSet<FIntVector2> CoordsToSearch = MapManager->GetPerimeterCoords(AgentGridCoord, FIntVector2(1, 1));
CoordsToSearch.Add(Agent->GridCoord);
for (FIntVector2 Coord : CoordsToSearch)
{
if (!SearchedCoords.Contains(Coord))
{
SearchedCoords.Add(Coord);
if (MapManager->Grid.Contains(Coord))
{
TSharedPtr<FGridCell> GridCell = MapManager->Grid[Coord];
TSet<AXYZActor*> ActorsInCell = GridCell->ActorsInCell;
for (AXYZActor* ActorInCell : ActorsInCell)
{
if (ActorInCell != Agent &&
!ActorsToAdd.Contains(ActorInCell) &&
!AgentGroup->AgentsInGroup.Contains(ActorInCell) &&
AgentsInAction.Contains(ActorInCell) &&
ActorInCell->ActorId == Agent->ActorId)
{
ActorsToAdd.Add(ActorInCell);
FindAndAddNeighbors(MapManager, ActorInCell, AgentGroup, SearchedCoords, ActorsToAdd, AgentsInAction);
}
}
}
}
}
}
So, we will recursively search for neighbors one grid tile away. Once we have all our groups, we will calculate the group center and assign each unit in the group their offset destination.
Now, you may have noticed this has led to an original issue. All these different groups will converge at the original destination. Here's an illustration.
Hmm, so we have the same issue as before. What can we do about it? Well, it's actually quite simple, and it's something I'm still working to optimize. Instead of calling our movement action just once to be processed, what if we call it at a certain rate until there are no agents to process? What will happen?
If we keep calling the process function, the groups will eventually go to the same target location. Once they converge, the group function will actually group them all together. This will give us one big group at the end that is all packed together.
Check it out!
It's not perfect, but it's a good start! I think I will need to add some logic to consider the distance from the center when checking if a unit should be added to the group.
4. Unit Pushing
Okay, on to the fun stuff! Now, this is a system that I had to reference from StarCraft. When you are moving units around, and they come into contact with other units, some different logic should happen. Unit Pushing happens when the following occurs:
The pushing unit is in the following states:
MOVING, ATTACKING, ATTACK_MOVING, FOLLOWING, PLACING
The pushed unit is in the following state:
IDLE
Okay, so how do we do this? It took me two iterations.
My first attempt at this was a bit brute-force. Whenever one of my units was in the state where it could push, it would constantly shoot rays from its forward direction, +/- 30 degrees in 10-degree intervals. If any of these rays hit a friendly unit, it would move in the direction of the ray. I scrapped it for the following reasons:
- Shooting a bunch of rays all the time from my units seemed not very optimal.
- Rays were going forward from the height of the owning unit. This didn't take into account height differences, which I did not like.
- The ray would sometimes miss a unit, and it would act like I never found the unit to push.
So, I scrapped it all and went with a more vector approach.
Given our unit can push, it will create four vectors rotated off its forward direction vector.
float MaxPushAngleDegrees = 60.0f;
float MinPushAngleDegrees = -60.0f;
float MaxInnerPushAngle = 15.0f;
float MinInnerPushAngle = -15.0f;
We then search for nearby units using our MapManager
Then calculate the direction vector from our unit to the unit that might be pushed.
FVector DirectionToUnit = TargetUnit - GetActorLocation();
DirectionToUnit.Z = 0.0f;
DirectoinToUnit.Normalize();
Now, to figure out if this actor is inside the range of -60 to 60 degrees of our forward direction, we calculate the dot product and make sure it's within the threshold.
float DotProductValue = FVector::DotProduct(DirectionToActor, ForwardDirection);
float MaxAngleThreshold = FMath::DegreesToRadians(PushAngle);
float MinAngleThreshold = -MaxAngleThreshold;
if (FMath::Acos(DotProductValue) >= MinAngleThreshold && FMath::Acos(DotProductValue) <= MaxAngleThreshold)
{
//Unit should be pushed
}
It will then check if it's inside the left or right cone and push it away in that direction.
Now, let's check out the results!
Not perfect, but there are quite a few values I need to fiddle with, such as the distance it should start to push, how big of a radius to find units, etc.
Oh, and I forgot to mention, when a unit is pushed, it will then be able to push others as well. To stop an infinite chain of pushing, if the original pusher is far enough away or has stopped moving, it will tell the unit it pushed that it can stop.
5. Unit Avoidance
Last but certainly not least is our unit avoidance! Much like the rules for pushing avoidance has some rules it needs to follow.
The unit avoiding is in the following states
MOVING, ATTACKING, ATTACK_MOVING, FOLLOWING, PLACING
The pushed unit is in the following state and it can be either an enemy or friendly
MOVING,
HOLD,
ATTACKING,
ATTACK_MOVING
So, what is avoidance, and how can we achieve it? Since other units are dynamically moving, our static mesh does not account for them when generating a path. Of course, Unreal has an avoidance feature, and I've tried to use and mess around with it, but it did not give me the control or results I wanted.
There are two specific scenarios I wanted to hash out before writing this, so we will go over them. As for the rest of the cases, I either haven't tried to break them or haven't thought of them.
First, let's define avoidance. If our unit is able to avoid, and there is a unit to avoid, it should steer away from it until it's free to go on its original path.
So much like how we do our unit pushing, we will detect units around us that are able to be avoided. However, instead of just a cone in front of us, we will perform a circular sweep around our unit every X amount of degrees and check if that angle is blocked by a unit. The closest direction that is not blocked will be the direction in which we move until we can go back on our original path.
The code is currently quite extensive and not very clean. Once I clean it up, I'll update this section.
Anyways, after thoroughly testing it, let's see the results in a simple test.
Perfect! The line of units is in a hold position, so our unit goes around! However, there is a special case for which we need to implement some additional logic.
In this illustration, our unit (the triangle) is inside a concave formation of units in a hold position and wants to go to the other side. The issue arises when it starts traveling up and over the concave; it realizes that going backward is a shorter distance to the target because it doesn't recognize the units further ahead blocking its path. It ends up oscillating between going back and forth.
So, what's the solution? My fix is that once we start avoiding units, we will not go back in the direction we started avoiding, within a range of 180 degrees. This means that we will continue avoiding and moving in a similar direction, even if that direction is further away from the target point.
And after implementing this simple logic, it can now successfully avoid concave formations!
Now, let's showcase my favorite part of this system. In Starcraft, a classic move is commanding Zerglings to attack a unit, and because of the avoidance in Starcraft, the Zerglings quickly surround the unit. Let's see if our system achieves a similar effect!
so freaking cooooooooooooooooooooooooooooooooooooooooooooooooooooool!!!
Well, that's it! If you made it this far, thank you so much for reading! Feel free to reach out to me at jandro@xyzrts.com.