Programmer Ramblings – Spawning and Runtime Performance on Maneater

Moving to spawn volumes

Even without talking to the designers, I knew that my core goal was to move to something better than spawn points. Filling an area with common spawn types using spawn points means making one spawn point, copying it a whole bunch of times, and then being miserable when you want to make a change. Volumes solve some problems there. That’s not to say the game doesn’t use spawn points – Kyle Ray helped me out there with a great spawn point refactor that is used in a bunch of spots to fill out detailed spawning, particularly on the beaches – but the general ambient spawning of human and wildlife should be far easier to deal with.

Volumes do a great job of filling out a bunch of space all at once to allow spawning over a wide area with common settings, and one of my first goals with the system was to make this as flexible as possible. To that end, I wanted to make the generation fast, but also allow for a bunch of prefab-style selections to make volumes based around general types of spawns.

In the grand scheme of things, fast generation is relatively easy – parallelize the hell out of it. The volume types are all effectively based around fixed grids, so we can easily calculate how many points could potentially fit in it, spawn a whole bunch of worker threads, and validate each of those points one at a time. Each point is an independent process operating on memory-safe data, so the only place I really needed to worry about any sort of thread lock was at the point where I was taking a validated point and adding it to the final serialized list. Even at this point, write accesses to the member were pretty small, and without the thread lock I could go through dozens of generations without ever hitting memory access violations (seriously, I tried it). Throw the thing at a 4 or 8 thread CPU, and I was getting level generation times for 20,000+ possible spawn locations down to within a few seconds.

This is made spectacularly simple through the use of the ParallelFor setup available in UE4. For example, this rough code could be used to generate a basic grid-based volume:

void SpawnVolume::RegenerateGrid()
{
	FBoxSphereBounds MyBounds = GetBounds();

	// Figure out the count of possible points within the AABB bounds of this volume space
	int32 XPoints = 1 + ((MyBounds.BoxExtent.X * 2) / SpacingX);
	int32 YPoints = 1 + ((MyBounds.BoxExtent.Y * 2) / SpacingY);
	int32 ZPoints = 1 + ((MyBounds.BoxExtent.Z * 2) / SpacingZ);
	FVector StartingPoint = MyBounds.Origin - MyBounds.BoxExtent;

	// Loop using worker threads, with each worker thread checking for validity of a single possible point
	FCriticalSection Mutex;
	ParallelFor(XPoints * YPoints * ZPoints, [&](int32 Index)
	{
		// Find current world location index
		int32 X = Index % XPoints;
		int32 Y = (Index / XPoints) % YPoints;
		int32 Z = (Index / (XPoints * YPoints));

		// Calculate world location of this point
		FVector CurrentPoint = StartingPoint + FVector((X * SpacingX), (Y * SpacingY), Z * SpacingZ);

		// Check for validity of this point.  This can include things like whether it's inside other geometry, whether it's within the actual defined volume space, whether it's under landscape, etc
		if (PointIsValid(CurrentPoint))
		{
			Mutex.Lock();
			GridSpawnPoints.Add(CurrentPoint);
			Mutex.Unlock();
		}
	});
}

It simply checks all potential points within the volume boundaries with configurable randomization, rejects invalid points, and adds it to the list. Importantly, this is where the expensive tests are done – things like inside geometry checks, traces to find whether we’re under landscape, inside all planes that make up the volumes, etc. Those types of things are prohibitively expensive to do at runtime, so we make sure that the points that make the final list are already going to be at the very least valid for spawning any one thing within the spawn lists of the volume. It creates as many worker threads as the computer allows, and goes about its business.

Flexibility is a different beast though. At its core, any volume-based type is probably going to have some rough grid for potential spawn locations, but some spawn types don’t make sense to be in a 3d grid. Boats only want to spawn at the surface of the water, which for our gameplay space is effectively a flat plane. Humans want to spawn on something solid under their feet, or if they spawn swimming, near the surface so they at least start life by not needing to hold their breath. Wildlife don’t really care where they spawn as long as it’s not inside of geometry. A fully fixed grid also looks like garbage for types on-land like beachgoers that spawn and lay in place, but you wouldn’t necessarily notice it underwater when things are spawning through dense fog. All these factors mean that a single generation type didn’t make sense, so my goal became spreading that out with simple selections to give the LDs a bunch of power with little effort.