Radar - Design & Development
Since the vehicles all have fixed handling properties in regards to turn speed etc (that are not affected by player sensitivity settings), it’s important that the player has good spatial awareness. Since I’m also supporting mods and custom map-making, the radar system has to be entirely self-contained. I don’t want any special-case setup requirements for the modders at the end, I should be able to drop into any world and everything instantly work regardless of map shape and size.
The radar was a very critical design element of the original games. I found myself using it all the time, after a while the radar ping sound would become embedded in your mind and remind you to quickly glance for an update on your surroundings - all without having to move your unit around. The radar has two modes, a ‘topographic’ radar which shows units in the vehicles radar range, on an approximation of nearby landscape geometry. Out-of-range units that have been ‘pinged’ are shown as arrows at the edge of the radar, indicating their direction.
A second ‘Global’ mode shows a colour overview of the entire playable area of the map. Despite being an RTS, the game has no fog-of-war (you have a big carrier in orbit, how could you not know what the terrain looks like ;)). Any pinged units are shown on the radar here too. Allied and Friendly units share blip information (unless that unit has it’s comms blocked), and all enemy blips face out over time. Some units have a ping delay, while others reveal units in their surrounding area continuosly. Ping timers are synced accross the network, so that all players see the same information without the need to send an RPC each time an object pings (that would be a big bottleneck with many units in-world!).
So how does it work?
Pinging Items & Fast Lookups
Luckily for me, I already had a good system for dividing up my objects in the world. The solution was a common one faced by developers - reducing the n^2 problem. As more objects are added to the world and constantly pinging other objects, the amount of distance checks to each object gets higher at an alarming rate. In my case, I have potentially large worlds with a widely varying density of objects - so it’s important to reduce this. I use the same Sparse Spatial Hash system I developed before for my ‘Game Object Manager’. The GOM keeps track of every single ‘Game object Component’ in the world, a custom actor component that almost all in-game objects will have. Initially, I used a Quadtree - but the hash system was much faster and easier to maintain and also allows for a neat math-based lookup trick (see further down)
The SSH (sorry) divides the world up into a grid of predefined size - and each cell stores a list of every ‘Game Object Component’ that is contained within it in World-Space. This list is updated every tick from the manager, but that is an N problem and relatively cheap - and also means I can do additional tick-based processing on every other object there too. Since objects are always moving around and being moved into different cells, it’s important to reduce memory allocations or you’ll end up with very fragmented memory and a slower grid system. The grid is predefined in size by the manager, and only extends in ‘blocks’ rather than for individual elements. Array elements are accessed and modified in-place, rather than adding to or removing from them.
Now rather than checking against every item in the world, I can first ask the grid to check the distance to each cell, performing a distance check to each object inside (since the cells are square!). This reduces the search complexity massively.
My next issue was reducing search complexity over world size. In an ideal world I would have a consistent search speed regardless of how many cells are in the grid. I came up with a nifty way of handling this.
Faster Spatial Hash Filtering
Since I know the top-left location of cell 0,0 - and every cell is a fixed size, and every cell is stored in a 1D array that uses a 2D accessor - there is an easy way to eliminate all cells outside of the search radius.
void ABZGame_WorldSettings::GetRadarPointInRangeIndices(int32& OutStartColumn, int32& OutStartRow, int32& OutEndColumn, int32& OutEndRow, const FVector2D& WorldXY, const float Range) const
{
// Work out an axis-aligned bounding box for this location, given the range we're looking for
const FVector2D BoundsMin = WorldXY - Range;
const FVector2D BoundsMax = WorldXY + Range;
// Clamp the bounding box to the playable area (it can be made rectangular)
const FVector2D ClampedMin = FVector2D(FMath::Clamp(BoundsMin.X, PlayAreaExtents.WorldMin.X, PlayAreaExtents.WorldMax.X), FMath::Clamp(BoundsMin.Y, PlayAreaExtents.WorldMin.Y, PlayAreaExtents.WorldMax.Y));
const FVector2D ClampedMax = FVector2D(FMath::Clamp(BoundsMax.X, PlayAreaExtents.WorldMin.X, PlayAreaExtents.WorldMax.X), FMath::Clamp(BoundsMax.Y, PlayAreaExtents.WorldMin.Y, PlayAreaExtents.WorldMax.Y));
// Difference from the ClampedMin and MinPlayArea
const FVector2D BoundsMin_Offset = ClampedMin - PlayAreaExtents.WorldMin;
const FVector2D BoundsMax_Offset = ClampedMax - PlayAreaExtents.WorldMin;
// Work out the starting indices for columns / rows
const int32 StartColumn = FMath::FloorToInt(BoundsMin_Offset.Y / RadarGrid_Spacing);
const int32 StartRow = FMath::FloorToInt(BoundsMin_Offset.X / RadarGrid_Spacing);
// Work out the ending indices for columns / rows
const int32 EndColumn = FMath::CeilToInt(BoundsMax_Offset.Y / RadarGrid_Spacing);
const int32 EndRow = FMath::CeilToInt(BoundsMax_Offset.X / RadarGrid_Spacing);
// Return the values
OutStartColumn = StartColumn;
OutStartRow = StartRow;
OutEndColumn = EndColumn;
OutEndRow = EndRow;
}
// Access 1D array as if it was 2D (one big block of memory is faster than multiple smaller blocks!)
FORCEINLINE static int32 Get2DIndex(const int32 Column, const int32 Row, const int32 NumRows) { return Row + Column * NumRows; }
Can you see what’s happening? I can get the start and end row & column for each cell in range, via a fixed math operation - rather than checking the distance to each cell. A huge speed improvement, and now consistent in speed regardless of world size!
The code above is used by the radar when gettings it’s list of draw points for the landscape (see further down) - but this same principle is also applied to the ‘GetGameObjectsInRange()’ function too! So that’s an easy way to get the draw list - now what about actually drawing the points?
Drawing
While a lot of radar system I’ve seen use render targets and black-box setups somewhere hidden on the map - I wanted to avoid this. I don’t want modders to have to set this up later, they should be able to drop into any kind of map and everything just work. So far the only thing the modder has to define is the min and max locations of the ‘playable area’, which is defined in the custom ‘World Settings’ class. Everything about the radar is drawn directly to the HUD.
– Landscape
The landscape data is stored in ‘World Settings’, and saved/serialized with the map. The modder runs a custom editor function to sample the terrain - and the results are stored in a grid fashion, just like the object list. All we store is ‘Z’ - X and Y can be determined from the data index. The radar samples points in the surrounding range, and transforms them to screen space as if they were rendered from a camera at around 35 degrees. This is a pretty simple operation:
FORCEINLINE FVector2D WorldToTopo(FVector WorldLocation, const FGeometry& AllottedGeo) const
{
// World to Radar Rot/Pos Transform
WorldLocation = Radar_TransformMatrix.TransformPosition(WorldLocation);
WorldLocation.Y *= -1.f;
const FVector2D ScreenLoc = FVector2D(WorldLocation.X, WorldLocation.Y);
return AllottedGeo.LocalToAbsolute(FVector2D(AllottedGeo.GetLocalSize() * ((ScreenLoc / 2.f) + 0.5f)));
}
The result is normalized to the radars UI geometry, so that OnPaint draws the lines in the correct position. The Radar_TransformMatrix is calculated every frame in a separate function ‘ComputeRadarProps()’ - which is called once per frame elsewhere. The landscape is then drawn column-by-column and again row-by-row, to form the grid.
– Blips
Blips rely on a new feature added to UE in 4.10 - SMeshWidget. Originally developed for Paragon, this widget is a way to draw lots of mesh-based shapes on screen in an instanced fashion. You can draw thousands without a dent in performance. You can find more information here.
Since the Radar purges and recreates all instance information every frame, theres no need to store a ‘state’ for each one. Instead, the HUD stores a list of game objects and their linked UI data, and updates each object every frame in one big loop. The radar simply pulls from this data at draw time.
USTRUCT()
struct BZGAME_API FGameObjectUIData
{
GENERATED_USTRUCT_BODY()
public:
UPROPERTY()
UBZGame_GameObjectTracker* TrackerWidget;
// Radar Blips
float Blip_ScreenSize;
// Data
float F_Opacity;
float F_Colour;
float F_Data;
bool F_CachedType;
EAffiliation LocalPlayerAffiliation;
FGameObjectUIData()
: Blip_ScreenSize(8.f)
, TrackerWidget(nullptr)
, F_Opacity(0.f)
, F_Colour(0.f)
, F_Data(0.f)
, LocalPlayerAffiliation(EAffiliation::EA_Neutral)
{}
};
Opacity, Colour and Data are all packed into instance data for each blip - and the material unpacks this later and determines how the blip should look. (See post here on how that works).](SMeshWidget - Hardware Instanced Slate Meshes Thread - Rendering - Unreal Engine Forums)
The radar compass is just a large blip - but rather than transforming the vertices for rotation, the material is instead ‘panned’ around with a single parameter. To reduce texture ‘swimming’, the texture is quite large. Maybe a vertex transform would be a better solution…
Final draw times? Pretty much spot on! (Times remain pretty much identical regardless of object count)
I hope this post was insightful!