{"id":935,"date":"2020-05-24T01:45:34","date_gmt":"2020-05-24T05:45:34","guid":{"rendered":"https:\/\/www.blog.dwgames.net\/?p=935"},"modified":"2020-05-24T14:54:31","modified_gmt":"2020-05-24T18:54:31","slug":"programmer-ramblings-spawning-and-runtime-performance-on-maneater","status":"publish","type":"post","link":"https:\/\/www.blog.dwgames.net\/?p=935","title":{"rendered":"Programmer Ramblings &#8211; Spawning and Runtime Performance on Maneater"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">I worked on <a href=\"https:\/\/www.tripwireinteractive.com\/#\/maneater\">Maneater<\/a> from approximately September 2018 to November 2019 when I left Tripwire Interactive.  A lot of what I tended to focus on through my time on Maneater was CPU-based performance gains on the UE4 game thread, so I wasn&#8217;t generally involved in other typical performance bottlenecks (particle cost, GPU time, etc), but there was enough work on the game thread to more than fill my time while I was on the project.  Among other things, two of the systems that I was most heavily involved in were a refactor of the spawn system, and work around handling runtime performance optimizations.  While I can&#8217;t really speak to what performance looks like on the shipping game, I can speak to some of the choices I made along the way, and how those two systems work in tandem to achieve performance gains.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"429\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-1024x429.png\" alt=\"\" class=\"wp-image-937\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-1024x429.png 1024w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-300x126.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-768x321.png 768w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-1536x643.png 1536w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC-2048x857.png 2048w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Where the hell do I start?<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">That really was the first decision to be made.  The game I started working on when brought in-house to Tripwire was much different from what Maneater became, but at its core the big problem was that the original game was made for high end PCs.  It had a ton of classic spawn points, spawned everything pretty much at once, and didn&#8217;t do any performance reduction on the actors in the world.  I knew one of our goals at the time was to see if it could get running on Switch, and I absolutely knew it needed to launch on Xbox One and PS4, all three of which are distinctly <em>not<\/em> high end PCs.  With that in mind, I had at least a rough approach planned out:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Do all my optimization work on Switch.  Any frame time gained there applied to other platforms.  If I had the game thread at ~26-28ms on Switch, the other platforms sure as hell would run fine.<\/li><li>Fix spawning first.  I needed to control how many things were in the scene at one time as a first order of business.<ul><li>This also came with refactoring the design tools.  Hand placing spawn points didn&#8217;t scale well for level designers, and at runtime iterating over hundreds of hand-placed actors didn&#8217;t make sense.  This needed to be replaced with something else.<\/li><\/ul><\/li><li>With spawning under greater control, start working on more granular framerate improvements:<ul><li>Once I could run at a stable framerate with spawning under control, start optimizing the runtime aspects of the game.<\/li><li>As the framerate improved, start spawning more things to fill the now free frame time to give higher AI density in the world.<\/li><li>Rinse and repeat.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">This formed the basis of my plan to get the game running well.  While it wasn&#8217;t the only set of systems I was involved in, it was definitely the one I spent the most time on throughout my life on the project.<\/p>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Moving to spawn volumes<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">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&#8217;s not to say the game doesn&#8217;t use spawn points &#8211; <a href=\"https:\/\/www.linkedin.com\/in\/kyle-ray-087b7159\/\">Kyle Ray<\/a> 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 &#8211; but the general ambient spawning of human and wildlife should be far easier to deal with.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In the grand scheme of things, fast generation is relatively easy &#8211; parallelize the hell out of it.  The volume types are all effectively based around fixed grids, so we can easily calculate how many points <em>could potentially<\/em> 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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This is made spectacularly simple through the use of the <code>ParallelFor<\/code> setup available in UE4.  For example, this rough code could be used to generate a basic grid-based volume:<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"godzilla\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void SpawnVolume::RegenerateGrid()\n{\n\tFBoxSphereBounds MyBounds = GetBounds();\n\n\t\/\/ Figure out the count of possible points within the AABB bounds of this volume space\n\tint32 XPoints = 1 + ((MyBounds.BoxExtent.X * 2) \/ SpacingX);\n\tint32 YPoints = 1 + ((MyBounds.BoxExtent.Y * 2) \/ SpacingY);\n\tint32 ZPoints = 1 + ((MyBounds.BoxExtent.Z * 2) \/ SpacingZ);\n\tFVector StartingPoint = MyBounds.Origin - MyBounds.BoxExtent;\n\n\t\/\/ Loop using worker threads, with each worker thread checking for validity of a single possible point\n\tFCriticalSection Mutex;\n\tParallelFor(XPoints * YPoints * ZPoints, [&amp;](int32 Index)\n\t{\n\t\t\/\/ Find current world location index\n\t\tint32 X = Index % XPoints;\n\t\tint32 Y = (Index \/ XPoints) % YPoints;\n\t\tint32 Z = (Index \/ (XPoints * YPoints));\n\n\t\t\/\/ Calculate world location of this point\n\t\tFVector CurrentPoint = StartingPoint + FVector((X * SpacingX), (Y * SpacingY), Z * SpacingZ);\n\n\t\t\/\/ 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\n\t\tif (PointIsValid(CurrentPoint))\n\t\t{\n\t\t\tMutex.Lock();\n\t\t\tGridSpawnPoints.Add(CurrentPoint);\n\t\t\tMutex.Unlock();\n\t\t}\n\t});\n}<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">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 &#8211; things like inside geometry checks, traces to find whether we&#8217;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 <em>at the very least<\/em> 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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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&#8217;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&#8217;t really care where they spawn as long as it&#8217;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&#8217;t necessarily notice it underwater when things are spawning through dense fog.  All these factors mean that a single generation type didn&#8217;t make sense, so my goal became spreading that out with simple selections to give the LDs a bunch of power with little effort.<\/p>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Generation flexibility<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Flexibility should be extremely easy to implement and extremely easy for designers to use.  To that end, our grid generation has a bunch of options around how it can change grid point generation.  <strong>Note<\/strong>: I&#8217;m going to use a hilariously dense set of volumes as examples &#8211; none of the runtime volumes are this dense, but it&#8217;s far easier to visualize this way.  Let&#8217;s start with a dead simple volume &#8211; straight axis aligned grid generation.  That gives us something like this:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"782\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGrid-1-1024x782.png\" alt=\"\" class=\"wp-image-942\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGrid-1-1024x782.png 1024w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGrid-1-300x229.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGrid-1-768x586.png 768w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGrid-1.png 1039w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Now, it&#8217;s functional, but what you aren&#8217;t seeing is that it&#8217;s also stacked in three dimensions.  Despite the underwater fog, it can still be fairly obvious that things are spawning against a grid.  To solve that, let&#8217;s give it a bit of randomization to offset the final test point from the initial location:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1018\" height=\"759\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGridRandomized.png\" alt=\"\" class=\"wp-image-943\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGridRandomized.png 1018w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGridRandomized-300x224.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_IC_SimpleGridRandomized-768x573.png 768w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">This small change made things <em>much<\/em> better.  If we drop down into 3D space, then this is definitely filling the area well:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"698\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1024x698.png\" alt=\"\" class=\"wp-image-944\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1024x698.png 1024w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-300x205.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-768x524.png 768w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image.png 1065w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">However, that only works well for wildlife that want to spawn underwater while swimming.  Boats don&#8217;t want to spawn there &#8211; they&#8217;d sink.  To solve that, I went ahead and added the concept of generation types.  For example, with boats I have a type that generates at the ground layer &#8211; either where the landscape exists, or at the water&#8217;s surface.  From our underwater perspective, that ends up looking something like this:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"652\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1-1024x652.png\" alt=\"\" class=\"wp-image-945\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1-1024x652.png 1024w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1-300x191.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1-768x489.png 768w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-1.png 1063w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s say we instead need to spawn some AI, but we only want to spawn them in areas where they can be on valid navigation.  For that, we&#8217;ve got a generation type that only uses valid spawn points projected onto a nav mesh.  That ends up giving us something like this:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"923\" height=\"690\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-2.png\" alt=\"\" class=\"wp-image-946\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-2.png 923w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-2-300x224.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/image-2-768x574.png 768w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">By implementing the concept of grid types, I was able to give the designers a lot of flexibility in laying out volumes that took advantage of the convenience and coverage of volumes, but were still a bit more special case than just simple grids.<\/p>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Visual Debugging<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Before I get too far, I want to take a quick aside to quickly mention the visual debugging tool I put in for both spawning AND performance management.  Doing full on debugging of thousands of potential spawn points is all well and good if you have a specific issue to solve, and doing log debugging at that scale is basically just log spam.  What I wanted was a way to quickly get a read on what the overall system was up to at any time.  I needed to see what possible spawn points are out there and whether they&#8217;re considered for spawning.  I needed to see where AI are running around in the scene, as well as get a rough idea of what performance bucket they&#8217;re in.  I wrapped all that into a unified top-down radar that I could toggle in non-shipping builds.<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video controls src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/2020-05-15-17-15-37.mkv\"><\/video><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">In its simplest form, the radar is simply a visual indicator of AI in the scene relative to the shark.  The color of the indicator is representative of which performance bucket they&#8217;re in.  I&#8217;ll cover those specifics a bit more later.  The next layer of the radar added information about active spawn points.<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video controls src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/2020-05-15-17-19-20.mkv\"><\/video><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Yellow points are the ones that are actively being considered for spawning, and red points are the ones that are actively valid for spawning based on a number of different factors.  Eating things will also cause a local area cooldown to go into effect for spawn locations, and I visualize that as a change to light blue points.<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video controls src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/2020-05-15-17-22-56.mkv\"><\/video><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">With these tools in place, during any normal gameplay session I could keep an eye on the general circumstances around spawning, see problem areas, and then investigate those more thoroughly, rather than simply having guesswork at places where things may be going wrong.<\/p>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Selecting the spawn point at runtime, and optimizations along the way<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Spawn location selection is filled with a whole bunch of choices, and I&#8217;ll go through that in order of roughly volume-scale down to point scale.  I&#8217;ll also describe some of the optimizations that were done along the way to keep the cost down as much as possible, as well as some of the filtering done at runtime based on the gameplay situation at hand.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">At the top, let&#8217;s start with volume combining.  Even with volumes filling a bunch of space, we didn&#8217;t necessarily want to have an entire region&#8217;s worth of volumes up at once.  It didn&#8217;t make sense to be filtering out points that were hundreds of yards from the player.  At the same time, breaking up the volumes meant we were duplicating things like spawn list validation checks for no reason.  This was fixed with two main systems &#8211; sublevel streaming and volume collections.<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video controls src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/2020-05-15-17-25-33.mkv\"><\/video><figcaption>Streaming is pretty obvious on-radar, but to the end user, it&#8217;s out of their visual range.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Sublevel streaming is pretty standard in Unreal, so I won&#8217;t go over it in detail.  For Maneater, spawn data was broken into its own sublevels with its own streaming settings so that we generally only had two or three sublevels of spawn data active at once &#8211; whatever one the player was actively in, plus the one they&#8217;re generally close to and moving in the direction of, and maybe some higher priority gameplay spaces that were always loaded.  As the sublevels activated, volumes were added to our active list to be filtered and considered for active spawning further down the process.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"872\" height=\"580\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_GrouperSpawns.png\" alt=\"\" class=\"wp-image-939\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_GrouperSpawns.png 872w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_GrouperSpawns-300x200.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_GrouperSpawns-768x511.png 768w\" sizes=\"auto, (max-width: 767px) 89vw, (max-width: 1000px) 54vw, (max-width: 1071px) 543px, 580px\" \/><figcaption>Volumes that share settings didn&#8217;t have to exist in a vaccuum &#8211; they could be effectively combined at runtime into a single virtual volume.<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">At the same time, repeating validity checks for volumes with common settings was a waste.  However, we wanted to preserve flexibility for where volumes were placed in cases where it was needed.  In the example above, we wanted groupers to spawn in areas roughly under garbage patches in this specific zone.  This meant having volumes that, while still relatively large compared to a player, were independent in placement.  By combining these at runtime, we are able to take the set of volumes that are active via sublevel streaming, and dynamically add them into a shared volume collection, combining their spawn list validation into a single pass for the entire collection, then move on to further checks from there.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">With the volume collections built, I can get to the first layer of rejection &#8211; spawn conditions.  Spawn lists aren&#8217;t really sufficient on their own as a way to figure out what kind of things we want to spawn.  There&#8217;s also gameplay reasons behind potentially rejecting a type of spawn.  Maybe we only want to let humans be on the beach during the day.  Maybe a certain type of wildlife can only spawn after hitting a progression point in the story.  I wrapped that all into a simple class called a spawn list condition.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"godzilla\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">UCLASS(BlueprintType, Blueprintable, Abstract)\nclass SpawnlistCondition : public UObject\n{\n\tGENERATED_BODY()\n\npublic:\n\t\/\/ Implementable event for native or BP.  The return value of this determines\n\t\/\/\t\twhether or not the spawn list that this is tied to can be active.\n\tUFUNCTION(BlueprintNativeEvent, Category=\"Condition\")\n\tbool ConditionIsValid(AActor* WorldContextActor);\n};<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">From a designer facing perspective, they can do whatever they need in Blueprint with this.  From a programming perspective, it means we can implement the conditions in native C++, as well as have a quick path to port things down from BP to native for performance.  On the spawn end of things, it gives me a true\/false way to trivially reject entire spawn lists, and if we end up with no valid spawn lists I can reject the entire volume collection from the more expensive filtering pass.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">So now that I have a valid set of lists of things that <em>can <\/em>be spawned, I need to figure out where they are allowed to spawn.  For that I do a quick scoring of each point to figure out if it&#8217;s valid.  The scoring that I ended up using gives me a rough validity arc like this in front of the player.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"400\" height=\"400\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_SpawnGrid.png\" alt=\"\" class=\"wp-image-953\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_SpawnGrid.png 400w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_SpawnGrid-300x300.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_SpawnGrid-150x150.png 150w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">So there&#8217;s a few things to note here:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>I know it seems <em>really <\/em>weird that nothing behind the player is valid.  I did a lot of testing on this.  Ultimately our players were moving forward in almost all cases.  On top of that, increasing spawn density in front of the player further reinforced that movement.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Spawn cycling happens very rapidly when the player does a hard rotation, so the lack of spawning in the distance behind the player is mitigated by rapid new spawns on top of existing spawns that the player has been passing by.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>There isn&#8217;t really much in the way of blockers to guarantee we can spawn things close out of sight.  Some zones have vegetation like kelp, but they also have wide open vision at or near the water&#8217;s surface.  Because of this, it became more of a priority of spawning things just out of potential vision range, but anywhere.  This became a bit of a happy accident in terms of greatly simplifying the selection process.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>The spawn band really is as narrow as it seems.  I limited this to one spawn per frame for performance, but that&#8217;s still a whole bunch of possible spawns per second, so a wide spawn band wasn&#8217;t required to fill the scene as the player moved forward.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">From a performance perspective, I was also able to go with a fairly quick approach under the mantra of &#8220;keep it simple&#8221;.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Filtering was done on the game thread just to avoid having to deal with thread concurrency problems.  We simply didn&#8217;t need to do that extra work for a small bit of gain.  This became even more obvious a choice given the thread limitations of the switch (3 core CPU, no sort of hyperthreading-like tech) where simply managing threads has the potential to introduce a crippling amount of overhead.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Each volume collection has its own delay for when it can be filtered vs using cached results.  This ended up being around half a second, with a bit of randomization to enforce filter staggering.  This minimized frames where large amount of volumes were being filtered at one time.  Because the status of a collection doesn&#8217;t really change <em>that much<\/em> frame to frame, we could get away with a lot of delay here using old info.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>The per-point validity checks were pretty simple math (distance squared, dot product, and some multiplications for stat-based modifiers) so even with potentially thousands of points in a bad frame, we weren&#8217;t spending significant time per-point.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>There&#8217;s only a couple of types of things that actually do additional work to minimize spawning on top of each other &#8211; namely ambient beachgoers and boats.  <ul><li>In the case of beachgoers, I simply put the specific spawn location on cooldown until the thing despawns or gets killed.  It tracks which location it spawned at, and shoots a callback to the volume when it goes away to place the point back into the active list.<\/li><li>Boats are a bit more obvious when they spawn on top of each other, so for those I do some additional range checks to minimize the likelihood of them spawning on top of each other, but it&#8217;s not 100%.  Going 100% prohibitive wasn&#8217;t worth the performance cost given the low chance of the edge cases occurring.<\/li><li>Otherwise, things spawn on top of each other all the time and it&#8217;s just not noticed.  As an example, fish typically spawn about 50-100% further than your max viewing distance, so by the time you get to them it&#8217;s a pretty low chance that even <em>if<\/em> the same spawn location was selected twice, that the fish won&#8217;t have swam in different enough directions to no longer be overlapping.  The performance cost of preventing overlaps simply wasn&#8217;t worth it.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Each level of filtering was a significant performance improvement. Going to streamed sublevels meant a huge reduction in <em>possible<\/em> points checked each frame. Spawn list condition rejections meant a huge reduction in points that have nothing to spawn at the current game time. Spawn volume collections meant greatly reducing overlap of spawn list condition checks, particularly expensive BP conditions.  Adding a filtering delay and using cached information meant that I might only be checking a single volume collection every few frames for new data, rather than all collections every frame.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>All told, I ended up getting spawn list condition rejection down to a goal of about 0.25ms and per-frame point filtering costs down to a goal of about another 0.25ms per frame, so doing additional heavy work to thread that out wasn&#8217;t worth further effort.<\/li><\/ul>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Runtime performance management and spawn cycling<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">So now that we&#8217;ve got things in the scene, how do we deal with active AI? We know they need to cycle in and out as they become less relevant to the player.  We know that things far off in the distance, especially things out of sight, don&#8217;t need to be doing their full behavior.  We really know things off screen can be prioritized for removal.  All of that ended up going through an implementation of the <a href=\"https:\/\/docs.unrealengine.com\/en-US\/Engine\/Performance\/SignificanceManager\/index.html\">UE4 significance manager<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">As a starting point, here&#8217;s a clip of the radar as I swim across a region.<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video controls src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/2020-05-15-19-01-23.mkv\"><\/video><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Even in this short clip, there&#8217;s a multi colored lightshow of AI going on, a lot of spawning and despawning going on, and even some different sizes going on.  To start breaking this down I&#8217;ll jump right into significance management and what it meant for the game.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">At it&#8217;s core, significance management is simple &#8211; you provide a way to score an actor, then significance management gives you a sorted list of those actors within a category.  How you score the actor is up to you, and what that list means is up to you.  For Maneater, I basically broke this into a few considerations:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Scoring is just a means to an end.  It gives me the list of actors in a sorted priority list.  Lowest scores are the things most relevant to the player.<\/li><li>Once the list is sorted, I can break those into buckets where each bucket represents a new level of overall behavior degradation (I&#8217;ll get into this a bit more in a bit).<\/li><li>Each bucket has a fixed size, and the overall system has a fixed size.  If something causes us to overflow the total size, the least relevant actors start being force despawned.<\/li><li>Importantly, these buckets can be tuned on a per-platform basis, so higher end platforms can have more active AI or more full-feature AI running at once than slower platforms, giving us some easy knobs to use to tune performance.<\/li><li>For scoring, I have two basic metrics &#8211; distance from player and whether or not they are forward\/behind in dot product.  Different classes have various modifications on the final score (ex: higher priority AI controllers can mod their score down to reduce despawn chances), but we still have the same root scoring calculation.<\/li><li>At a fixed max significance, actors will also be force despawned regardless of the system limits.<\/li><li>Like spawn point filtering, I do this largely on the game thread because there just isn&#8217;t enough data to make it worth doing additional worker threads.  There&#8217;s a threaded sort once the list is completely scored, but the stuff on the game thread was significantly under a millisecond for the actual scoring process.<\/li><li>The more expensive part of the whole process is physics state changes that happen based on spawning\/despawning, but that stuff can&#8217;t particularly be threaded, and having the state changes happen allows for better overall performance anyway.  They also typically don&#8217;t happen on most frames.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">With the basic calculation I get a rough area shape something like this (also, totally not to scale):<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"400\" height=\"400\" src=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_Significance.png\" alt=\"\" class=\"wp-image-955\" srcset=\"https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_Significance.png 400w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_Significance-300x300.png 300w, https:\/\/www.blog.dwgames.net\/wp-content\/uploads\/2020\/05\/Maneater_Significance-150x150.png 150w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">As you can see, this significantly prioritizes things in the direction of player movement to stick around, and significantly deprioritizes things behind the player to despawn.  Each color band is another bucket deeper in the system, and another set of things that happens to reduce the performance impact of an actor in that band.  Outside of the color bands, things are forcibly despawned.  If we look at the buckets in place, roughly the following happens:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Bucket 0<\/strong>: Full performance bucket, all logic on, full tick rate, full animation rate<\/li><li><strong>Bucket 1&#8230;n-1<\/strong>: Tick rate reduction for each bucket higher in the system.  At the time that I left Tripwire, this was at 0.04 seconds per bucket on PC, Xbox One, and PS4.  Switch was much more aggressive at 0.15 seconds per bucket reduction, though I expect that value to be able to be lowered by the time they ship.  Tick rate reduction applied to the AI controller, pawn, behavior tree, and animation.<\/li><li>At a configurable specified bucket, navigation is completely turned off, but other AI systems are maintained on the drastically reduced tick rate.<\/li><li>In the last bucket, the actors are put into full dormancy until they either despawn or become more relevant to the player.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">While this ends up giving us a ton of game thread time back each frame, it also introduces a high rate of spawn churn.  Spawns on slow platforms were sometimes hitting 40-50ms for a pawn\/controller pair.  While some of that could definitely be optimized away, I needed a bit more help to achieve that, and went with a spawn pool to manage these actors.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I won&#8217;t go into detail on the spawn pool since it&#8217;s not a complicated thing.  Instead of spawning an actor, look in the pool to grab one thrown into stasis.  Instead of despawning an actor, kill its tick and throw it into stasis way outside the playable area.  If there&#8217;s anything I can really draw as a conclusion here, it&#8217;s <strong>do this as early as is possible, then do it even earlier<\/strong>.  Adapting a game that has its entire actor initialization system built around new actors to something that has recycled actors was a pain in the ass.  It was just a pile of bugs of systems that needed to be reset or reinitialized or cleared.  While all those things are not free (heck, physics resets were a large part of our respawn time and mostly needed to happen), I was seeing 60%+ reduction in spawn costs by moving over to a pooled system.<\/p>\n\n\n\n<!--nextpage-->\n\n\n\n<h2 class=\"wp-block-heading\">Conclusions<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">This was an interesting project to end up working on.  It had been years since I worked on a fully single player project, as I&#8217;d generally been moving around to help out with studios doing Unreal Engine multiplayer titles.  This was also the first time I&#8217;ve helped tackle an open world game.  While there&#8217;s plenty of literature out there for more traditional open world titles, there&#8217;s really not much about ones involving <em>sharks<\/em>.  I combined some of the more interesting things I read in the genre with a lot of testing and a little bit of guessing and ended up with some systems that I was overall pretty happy with.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Getting this thing running at 30 FPS on the Switch was definitely a struggle at times, and a lot of that fell right into the spawning systems.  The hardware is good <em>for a handheld<\/em> but it&#8217;s just so thread limited, which kind of put a clamp on how crafty I could get.   This ultimately ended up being a benefit, as I tended to gravitate towards simplicity over small gains.  Rather than debugging edge cases in complicated code, I just spent time working on better implementations of other systems, and the rest of the launch platforms kinda just joined the ride.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I don&#8217;t know that I ended up getting everything totally right, but for the most part it feels at least on the right track.  The system is pretty flexible, runs pretty fast, is pretty simple, and doesn&#8217;t place impractical limits on design.  It keeps the gameplay space refreshed pretty well, while also being tuned to encourage the player to keep moving.  I don&#8217;t know that the patterns necessarily fit all open world games, but one that takes place underwater?  I think I&#8217;ve got it in a good place.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I worked on Maneater from approximately September 2018 to November 2019 when I left Tripwire Interactive. A lot of what I tended to focus on through my time on Maneater was CPU-based performance gains on the UE4 game thread, so I wasn&#8217;t generally involved in other typical performance bottlenecks (particle cost, GPU time, etc), but &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/www.blog.dwgames.net\/?p=935\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Programmer Ramblings &#8211; Spawning and Runtime Performance on Maneater&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1011,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[207],"tags":[210,211,208],"class_list":["post-935","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming","tag-game-dev","tag-maneater","tag-programming"],"_links":{"self":[{"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/posts\/935","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=935"}],"version-history":[{"count":10,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/posts\/935\/revisions"}],"predecessor-version":[{"id":1036,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/posts\/935\/revisions\/1036"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=\/wp\/v2\/media\/1011"}],"wp:attachment":[{"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=935"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=935"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blog.dwgames.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=935"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}