Multiplayer FPS / RTS Hybrid - Dev Blog

What’s up devs.

For the last 2-3 years, I’ve been on-and-off working on a side project in my spare time (a rare commodity when running a studio!) - and I’ve wanted to keep some kind of blog somewhere for this project, to give some insight about my findings while hacking away at this idea as a solo dev in Unreal. I believe it’s good practice to write and keep retrospectives of your work and findings now and again - so I’m going to try and find more time to work on this during 2017 and especially to do occasional write-ups on the work. Since I don’t have blog that I regularly update and as I visit this site daily, a thread here seems like a good spot!

The end goal for the project is completely, 100% overly ambitious (like any good pet project)](Sarcasm - Wikipedia) - To develop a competitive multiplayer FPS/RTS hybrid, focused on vehicle based combat and while also trying to eliminate some of the common issues with those genres. It also needs to look awesome. The core ideas are based on probably my favourite game ever made, Battlezone II. You will likely see a lot of resemblance in the early prototype days while I’m still putting code together.

Since the game has a planned RTS element and mods will be supported - everything is being designed to be as modular and performant as I can make it. It involves Networking, AI, Technical Art, Physics Programming, Artwork Generation, Sound Creation, FX and loads more, so the hope is that somebody can learn something from it. What’s more is that as a fairly rookie programmer that is only comfortable with C++ inside Unreal, I try to use as many of UE’s built-in systems as possible, so no third-party shenanigans here.

I’ll update the title post with the latest video, useful links or reading material that I’ve found, and links to the posts as I go on. I hope this is both useful and interesting!

Latest Video - (Full Playlist)](
GOTY 2016 - Festive UE4 Hovertanks - YouTube

Radar Design, Sparse Spatial Hash Filtering

Other Threads
SMeshWidget - Hardware Instanced Slate Widgets for Radar

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?

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.

struct BZGAME_API FGameObjectUIData

	UBZGame_GameObjectTracker* TrackerWidget;

	// Radar Blips
	float Blip_ScreenSize;

	// Data
	float F_Opacity;
	float F_Colour;
	float F_Data;

	bool F_CachedType;
	EAffiliation LocalPlayerAffiliation;

		: 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!

How are you doing the ‘dividing the world into a grid’? This is something I’m interested in for my racer prototype. Do you have a way to visualize the grid?

Essentially I have a custom WorldSettings class that has a ‘PlayableArea’ struct. This is just two FVector2D’s that define the min and max boundaries in X and Y for the playable area of the world. I then have a manager that creates ‘cells’ at spaced-out intervals within this area (the cells are just TArrays, stored inside another TArray that stores them in a Row-major 1D format). Every frame the manager iterates all the registered GameObjects and moves / places them in the correct cell.

I used to use a Quadtree - but it was actually much less performant and caused big problems when two objects occupied the same space (cells would keep dividing at a crazy rate). Here’s a good bit of reading on the two methods (Quadtree and 2D Grid)

Thanks for the reply - I believe a 2D grid is better than a quadtree, too.
The cells are TArrays of what? I used TArrays of structs, is this what you use too?

In my case they are TArrays of pointers to a custom Actor Component. When the actor component is created and destroyed, it registers / unregisters itself with the Object Manager and references get cleaned up.

Quadtrees are definitely useful but probably more so when you have a high concentration of objects and they are fairly evenly distributed. In my case I tend to have high concentrations in smaller areas so it just wasn’t worth the extra processing power. Took about 3ms to update the Quadtree with about 500 or so units, whereas the hash grid is less than .1ms, so made sense for me! Always profile stuff to see which suits better!

I have been following your development on this for a long time. Are you available for freelance work to help me get my physics projectiles replicating properly? I have a custom hover vehicle I built from scratch which is quite nice, and got a freelancer in to help me with physics replication on it, but have only recently gotten to projectiles.