Bolt Storm

Bolt Storm is a semi-procedurally generated roguelike game with RTS elements. It is developed by students of the NHTV university in Breda (The Netherlands) for a company called Kuality Games. Development started as pre-production in September 2016 and the game is meant to be released on both PC and Xbox One late 2017.

The game is played in a generated dungeon in which the player has to leverage his army to find his way to the surface.

Bolt Storm in short:

  • Dungeon crawler with RTS elements made in Unreal Engine 4; local co-op
  • My participation: September 2016 – present
  • Approved on Steam Greenlight
  • Developer team size varied from around 15 in pre-production to 31 in production

My main contributions

Being the AI programming lead for Bolt Storm means I am involved in most of the project’s AI related code. My main contributions however are related to the army formations, group AI and targeting systems (for which I am all fully responsible). As the AI are generally the main bottleneck of the game, a lot of my time is and was spent on optimizing the implemented systems for better performance.

  • Projectile physics with movement prediction
  • Army formations:
    • Following player in configurable army formation
    • Dynamic group formations (line, circle or spearhead)
    • Dynamic position reassignment of units in groups (to make the turning of groups smoother)
  • Group AI:
    • Behavior trees
    • Targeting
    • General awareness and patrolling
    • Player commands (override normal behavior)
    • Pathing through and around barricades
  • Individual AI:
    • Behavior trees
    • Targeting
    • General awareness
    • Implementation of pawn and obstacle avoidance

Projectile Physics

For the ranged AI we needed a way for the individual units to know how they can reach a target with their projectiles, and if it would not get blocked by a mesh in the level. To that end I implemented a custom class to handle the projectile physics, which also enables other programmers to make effective aim assist for the player.

The system works with only a couple of variables: the gravity affecting the projectile, the target locations and either a desired starting angle or a launch speed. When an angle is given, it will calculate the necessary speed to reach the target; when a speed is given, it will find the possible launch angles.

Available functions:

  • 2D, assumes target height is equal to starting point (cheaper than 3D)
    • Speed: returns launch speed with given angle
    • Angle: returns launch angle with given speed
    • Height: returns launch angle and speed to reach a given peak height
  • 3D, assumes target can be at any relative position (more expensive than 2D)
    • Speed: returns launch speed with given angle
    • Angle: returns launch angle with given speed

Projectile Physics: Code Snippet

//Returns true if the projectile can reach the target; member variables give you the angle at which you can fire and whether arc is obstructed
bool FBsWpProjectilePhysicsController::PrepareProjectileWithSpeed3D(float aStartSpeed, FVector aStartPosition, FVector aTargetPosition, float &aAngleDegAtStart, bool &aIsArcObstructed, const FVector aVelocityOfTarget, const float aMaxSecondaryAngle, const int32 aObstructionPrecision, const bool aDrawDebug)
{
	//Make sure gravity is not 0 and calculate/store mHalfGravity
	CacheGravity();

	if (aVelocityOfTarget.SizeSquared() > 0) {
		//Travel time in perfect circumstances (0 degree firing arc)
		float tDistanceToTarget = FVector::Dist(aStartPosition, aTargetPosition);
		float tTravelTime = tDistanceToTarget / aStartSpeed;

		//Rough movement prediction; doesn't need to be fully accurate because of desired random deviation
		aTargetPosition += aVelocityOfTarget * FMath::FRandRange(tTravelTime, tTravelTime * 1.35);
	}
		
	//For distance only consider the floor plane; the height is used seperately
	FVector tTargetDirection = (aTargetPosition - aStartPosition).GetSafeNormal2D();
	float tDistance2D = FMath::Sqrt(FVector::DistSquaredXY(aStartPosition, aTargetPosition));
	float tHeight = (aTargetPosition.Z - aStartPosition.Z);

	//StartSpeed^2 gets used often, so we cache it
	float tStartSpeedSquared = aStartSpeed * aStartSpeed;
		
	//The RootSqInCalc has to be real (positive), otherwise the target cannot be reached with the set projectile speed
	float tRootSqInCalc = tStartSpeedSquared * tStartSpeedSquared - mGravity * (mGravity * tDistance2D * tDistance2D + 2 * tHeight * tStartSpeedSquared);
	if (tRootSqInCalc < 0)
		return false;

	//tRootSqInCalc is >=0, so no possibility for complex values here
	float tRootInCalc = FMath::Sqrt(tRootSqInCalc);
		
	//Always two possible solutions:
	float tAngleRad1 = FMath::Atan((tStartSpeedSquared - tRootInCalc) / (mGravity * tDistance2D));
	float tAngleRad2 = FMath::Atan((tStartSpeedSquared + tRootInCalc) / (mGravity * tDistance2D));
	if (aDrawDebug) GEngine->AddOnScreenDebugMessage(-1, 2.0f, FColor::Green, FString::Printf(TEXT("Possible Angles: (%f and %f)"), FMath::RadiansToDegrees(tAngleRad1), FMath::RadiansToDegrees(tAngleRad2)));

	float tSelectedAngleRad = 0;
	bool tIsAngleValid1 = true;
	bool tIsAngleValid2 = true;

	//Do raycasts to check if the firing arc is clear
	if (IsFiringArcObstructed3D(aStartPosition, tTargetDirection, tDistance2D, aStartSpeed, tAngleRad1, aObstructionPrecision, aDrawDebug)) {
		if (aDrawDebug) print("Angle 1 is obstructed");
		tIsAngleValid1 = false;

		//Only check Angle 2 (the slow path) if Angle 1 (the fast path) is obstructed or above the limit
		if (FMath::RadiansToDegrees(tAngleRad2) > aMaxSecondaryAngle) {
			if (aDrawDebug) print("Angle 2 is too steep");
			tIsAngleValid2 = false;
		}
		else if (IsFiringArcObstructed3D(aStartPosition, tTargetDirection, tDistance2D, aStartSpeed, tAngleRad2, aObstructionPrecision, aDrawDebug)) {
			if (aDrawDebug) print("Angle 2 is obstructed");
			tIsAngleValid2 = false;
		}
	}
	
	//Use the narrowest Angle (always 1) when it isn't obstructed, otherwise check/use Angle2
	if (tIsAngleValid1)
		tSelectedAngleRad = tAngleRad1;
	else if (tIsAngleValid2)
		tSelectedAngleRad = tAngleRad2;
	else {
		//Just set the narrowest Angle (always 1), in case we want to shoot regardless of both firing arcs being obstructed
		aIsArcObstructed = true;
		tSelectedAngleRad = tAngleRad1;
	}

	//Get the projectile's horizontal starting velocity
	float tStartSpeedHorizontal = FMath::Cos(tSelectedAngleRad) * aStartSpeed;
	
	//Calculate starting speeds for each axis
	mProjectileVelocity = FVector::ZeroVector;
	mProjectileVelocity.X = tTargetDirection.X * tStartSpeedHorizontal;
	mProjectileVelocity.Y = tTargetDirection.Y * tStartSpeedHorizontal;
	mProjectileVelocity.Z = FMath::Sin(tSelectedAngleRad) * aStartSpeed;

	//Returning values for Blueprints
	aAngleDegAtStart = FMath::RadiansToDegrees(tSelectedAngleRad);

	return true;
}

Army formations

Dynamic group formations:

My first task in Bolt Storm was to make a system which would put groups of soldiers into a formation. To give maximum flexibility to designers I ended up implementing four different types: the classic line formation, a single circle, multiple stacking circles with varying size, and last not but least the good old spearhead.

Dynamic position reassignment:

Turning of groups was problematic both visually and in terms of performance: the units would trigger an excessive amount of overlap events. To fix this I let the groups dynamically reassign each of its units. For example: when a 180 degree turn is made, the front row will become the back row and vice versa (meaning the units won’t cross paths)

The technical implementation is a brute-force which finds the closest unit for each formation position, starting from from the center front and working towards the back. The amount of calculations is given by 0.5 * units^2, which results in 50 DistanceSquared calculations for 10 units, 200 calculations for 20 units and 800 calculations for 40 units. The groups in Bolt Storm usually stay under a size of 20 though, meaning it is quite cheap to do.

Reassignment concept:

  1. Copy the array of unit pointers
  2. For each formation position, find the closest unit
  3. Assign closest unit to that point, then remove it from the array

The order of unit assignment

Group AI

Group AI was my main task and responsibility, and has become the centerpiece of Bolt Storm: the groups are linked to almost every piece of code in the game. They act as invisible characters which follow the player around and direct their member units.

The groups really have become a command center, as they essentially govern the individual AI: the group tells them where to go, who to attack and when they are allowed to perform certain queries. For example, per frame only 1 unit per group is allowed to do a targeting or environment query (to balance the load equally and increase performance).

Behavior Trees

Groups run a simple but flexible behavior tree, with an improvised finite state machine. When the player gives no input, it runs its normal behavior. The behavior states can be manually altered with commands though, either given by a player or invoked by a different piece of code. This makes it really simple for other programmers to work with the group system, especially since I made a function library to query the groups.

The group behavior trees have a finite state machine built in. While this is not an ideal implementation, it allows any code in the game to directly alter a group’s behavior.
With the way the group behavior trees are abstracted, any specific group’s behavior can be directly altered from both C++ and Blueprint code. This overrides their normal behavior, and once the group is done with a given command it will automatically continue normal behavior.

Barricades

A late addition to Bolt Storm are the barricades, which can block paths to give ranged enemies an advantage. To make them function well in the game, it was imperative that groups would be able to detect relevant barricades by themselves and make the best decisions to bypass them.

Several implementations were considered, the first being predefined zones in each level which the barricades would have manually set links to. This seemed too much of a burden on the level designers though; things needed to work well dynamically, in any scenario.

To make that happen, I ended up leveraging the ‘Partial Path’ flag in UE4’s path finding: when the path to a target is incomplete, the group should look if any barricades will make the path complete. When a partial path occurs, groups will therefore find the nearest few barricades and perform a few checks on them. We also want to avoid any excessively long paths, so we need to also check whether a path through a barricade is significantly faster than the way around it:

The behavior flowchart with barricades
The management function which checks for any blocking barricade (click to enlarge)
The pathfinding loop to determine whether breaking a barricade will make the path to a target possible (click to enlarge)

The result:

Individual AI

Targeting

The main problem the project had during pre-producten was the terrible performance, which was caused mostly by the individual targeting systems (Unreal’s own PawnSensing). When entering production, I set out to delegate all targeting to the groups to have better control over the overall performance.

Different units called for different targeting algorithms though. For the melee it is important to be aware of the surroundings; what group a specific target belongs to is mostly irrelevant. They therefore use sphere traces in a given radius to look for targets. To make sure the performance is kept consistent, the units queue up before they are allowed to do a sphere trace: per frame each group will only allow one unit to run its targeting code.

Ranged on the other hand care deeply about what group their target belongs to. Therefore the easiest and cheapest way was to just let the group assign targets based on indexes in the unit arrays. The initial implementation worked well, but didn’t look pretty because of arrows crossing paths (in a hourglass pattern towards the enemy). To fix this, I adjusted the targeting to select the most ‘parallel’ target: the relative position of a unit to its group is added to the enemy group, and then the closest enemy to that position is found.

Parallel Targeting: Code Snippet


void ABsGroupFormation::SelectTargets_RangedParallel(ABsGroupFormation* aGroupToAttack)
{
	//Don't attack groups that are on the ignore list
	if (mGroupsToIgnore.Contains(aGroupToAttack))
		return;

	int32 tMyUnits = mUnitArray.Num();
	int32 tTheirUnits = aGroupToAttack->mUnitArray.Num();
 
	//Calculate average position of the groups
	FVector tThisGroupPosition = FVector::ZeroVector;
		for (auto funit : mUnitArray){
	 		tThisGroupPosition += funit->GetActorLocation();
	 	}
	FVector tThatGroupPosition = FVector::ZeroVector;
	 	for (auto eunit : aGroupToAttack->mUnitArray) {
	 		tThatGroupPosition += eunit->GetActorLocation();
		}
	
	tThisGroupPosition = tThisGroupPosition / tMyUnits;
	tThatGroupPosition = tThatGroupPosition / tTheirUnits;

	//Instead of giving units their target directly, we create an array with target indices
	TArray tTargetIndexes;
	tTargetIndexes.Init(0, tMyUnits);

	//Find the closest enemy around the enemy group with the friendly's local offset 
	//This has the effect of the ranged units shooting parallel to each other
	for (int32 friendly = 0; friendly < tMyUnits; friendly++)
	{
		FVector tOffsetToGroup = tThisGroupPosition - mUnitArray[friendly]->GetActorLocation();		
		FVector tAttackLocation = tThatGroupPosition - tOffsetToGroup;

		int32 tClosestEnemyIndex = 0;
		float tClosestDistanceSq = 8388608; //max attack range

		for (int32 enemy = 0; enemy < tTheirUnits; enemy++)
		{
			float tDistSq = FVector::DistSquared(aGroupToAttack->mUnitArray[enemy]->GetActorLocation(), tAttackLocation);

			if (tDistSq < tClosestDistanceSq) {
				tClosestDistanceSq = tDistSq;
				tClosestEnemyIndex = enemy;
			}
		}
		
		tTargetIndexes[friendly] = tClosestEnemyIndex;
	}

	//Pass the targeting array to Blueprints
	//This way we don't have to jump between C++ code and the Blueprint VM multiple times
	SetTargets(aGroupToAttack, tTargetIndexes);
}

Avoidance

Unreal Engine 4 has both the Reciprocal Velocity Obstacle (RVO) avoidance and its own Crowd Avoidance built in. Neither of these systems were made for RTS types of unit movement, so I had to improvise on the implementation. RVO performs well at high speeds and its operations are exceptionally cheap. In melee combat however, it still makes the units overlap too much.

Crowd Avoidance, unlike RVO, actually affects the navigation path of the unit. This inherently means it is significantly more expensive, so the upper limit of units is constrained. It does relatively well at preventing the units from overlapping, but only at lower speeds; when following the player in closely packed formations, it would make the whole army stutter significantly.

To get the best of both worlds, I decided to dynamically switch between these two types of avoidance algorithms. When following the player, units in Bolt Storm will only use RVO to avoid one another. Then once a melee unit enters combat, it will enable Crowd Avoidance for itself. Ranged units never use it to give the melee units more budget; it is much more important for the melee after all.