Lighting the Path: Pathfinding for 60K Units in Age of Darkness | Unreal Fest Gold Coast 2024

Estimated read time: 1:20

Summary

In a presentation at Unreal Fest Gold Coast 2024, PlaySide Studios engineers Quinton Pinto and Jackell explored the complexities of pathfinding for large unit counts in the game Age of Darkness. They delved into the technical challenges and solutions surrounding unit formations, UI/UX simplicity, and pathfinding systems while ensuring smooth performance even with 65,000 units. Key topics included cache-friendly designs, data-oriented architecture, and custom pathfinding solutions like partial flow fields, providing both efficiency and player satisfaction.

Highlights

Kicking off with humor, the developers eased the crowd by addressing potential nerves on stage. 😅
Quinton and Jackell from PlaySide Studios discussed handling 65,000+ units in Age of Darkness, explaining their strategic design hurdles. 🎮
The talk covered formations for effective gameplay, emphasizing how to tackle challenges with innovative solutions. 🚀
Highlighted the use of advanced techniques like ECS for managing large scale units efficiently. 🛠️
Discussed the pathfinding system, emphasizing custom solutions to maintain performance with a large number of units. 🔍
Emphasized the smart use of partial flow fields to enhance quick pathfinding over complex terrains. 🚦

Key Takeaways

Efficiency is King: Implementing a cache-friendly design can drastically improve CPU performance when managing massive unit counts. 🧠
Think Ahead: Integrate game features like formations and pathfinding in ways that simplify and enhance player experience. 🎮
Embrace the Simple: Complex problems don't always need complex solutions; simple approaches often yield the best results. 🔑
Customize for Success: Sometimes, custom systems like Partial Flow Fields are necessary for unique game requirements, beating generic solutions. 🤓
Modular Thinking: Break down large solutions into smaller, manageable clusters to tackle challenges effectively. 🧩

Overview

At the Unreal Fest Gold Coast 2024, developers from PlaySide Studios revealed their experiences on stage about managing an impressive number of units within the game Age of Darkness. The presentation focused on solving intricate problems, in particular, the pathfinding for these massive unit counts, which is no small feat. They offered insights into their pathway of problem-solving—from leveraging cache-friendly designs to creative data-oriented solutions.

A core part of the discussion was the incorporation of unit formations in real-time strategy settings, making it simple and more intuitive for players. The team tackled the challenge of integrating formations and pathfinding seamlessly into Age of Darkness. They shared their strategies on balancing functionality with user interface simplicity, ensuring players have a smooth and engaging experience.

The second part of the talk emphasized advanced pathfinding improvements using custom solutions over standard Unreal Engine options. This included a deep dive into the efficacy of partial flow fields. By utilizing these, PlaySide Studios enhanced the gameplay's ability to handle numerous units without sacrificing performance, illustrating a successful case of opting for tailored solutions over out-of-the-box software tools.

Chapters

00:00 - 01:00: Introduction The chapter begins with the speakers expressing their nervousness as it's their first time on stage. They decide to start with an icebreaker question by asking the audience if they've played the game 'Age of Darkness.' The audience responds, and the speakers acknowledge both players and those who have wishlisted or wish to play the game later. They humorously clarify that increasing player numbers is not their immediate goal.
01:00 - 23:00: Challenges and Solutions in Formations This chapter focuses on the various challenges encountered during the development of a game and the solutions implemented to address them. It emphasizes the team's commitment to sharing as much information as possible from their experiences. Despite technical difficulties such as video sound issues, the narrative invites the audience to envision the epic battles embedded in the gameplay.
23:00 - 43:00: Challenges and Solutions in Pathfinding The chapter titled 'Challenges and Solutions in Pathfinding' appears to be a discussion-based transcript. The conversation seems informal, with a brief mention of beatboxing before quickly transitioning to the main topic of the presentation. The speaker provides a high-level overview saying the presentation will cover a survival and tower defense game, emphasizing that players will face a considerable number of units to survive against.
43:00 - 44:00: Conclusion and Key Takeaways In the conclusion, the speakers Quinton Pinto, a senior engineer, and Jackell, an engineer, from Playside Studios discuss a large number of units, around 70,000, though there is some uncertainty about the exact figure. They reassure the audience that the details are covered in their slides. The chapter likely involves summarizing their discussion on 'lighting the path,' though specific takeaways aren't detailed in the provided transcript.

Lighting the Path: Pathfinding for 60K Units in Age of Darkness | Unreal Fest Gold Coast 2024 Transcription

00:00 - 00:30 it's our first time on stage so we're a little bit nervous but we better try our best So let's go Um let's start with an icebreaker Who's um who's played Age of Darkness the game oh yeah And who hasn't played but maybe has wishlisted or want to play it at a later stage okay we can increase those numbers but that's not the goal Don't worry it's
00:30 - 01:00 about uh giving as much information as we can from what we learned working on this game So if you haven't played the game we have a little snippet So let's have a look Where is the sound oh no Can we try that again all right No sound video Let's go Just imagine the epic battles in your
01:00 - 01:30 head Can you beat box Jack no I cannot The one thing I haven't specked into Yeah All right don't worry about it Uh so long story short we have lots to cover in the presentation So it's an survival RDS slash tower defense where you survive against lots of units And when I say lots I mean lots and lots
01:30 - 02:00 of units About 70,000 of them Really 70,000 Is that the exact number well marketing told me it was 70,000 Marketing likes to round up a fair bit 65 70 I don't know what it is But don't worry guys we got it covered in the slides My name is Quinton Pinto I'm a senior engineer at Playside Studios My name is Jackell I'm an engineer 3 at Playside Studios And our talk is on lighting the path There's so much we
02:00 - 02:30 want to talk about but there's so much we can fit in the slots So I'm going to talk about formations in the first half and then I'm going to cover path finding in the second We got no time So let's dive straight in Uh I'm going to start with what the problem is and the challenges of solving the problem how we solved it because there's many ways to solve it and then end with some key takeaways before we go make it spicy with path findings All right So what is
02:30 - 03:00 the problem right in the game to fight the nightmares you need an army and that army contains um different agents You need like a front line and a back line like soldiers and archers and you want to keep the archers safe behind the back line But in the game the problem is there isn't an effective way to do that right your backline is always unsafe And to keep your backline safe
03:00 - 03:30 you would have to select the archers you got to move it back and then that's very tedious And every time you move your army you got to have to do that all all over again And that's that isn't fun right and why do we play games we play it for fun So we need to fix that Now one thing to keep in mind our game is in early access People are playing it People are accustomed to
03:30 - 04:00 the features like they're used to the tools and they also have ideas of how to solve this problem right and yeah so interesting idea how hard how how does it fit our game so there's two scenarios we can think of in terms of design One is when we get ready for battle we want our units to go from A to B really quickly and then form up into a formation Uh because you want to get
04:00 - 04:30 ready for battle right the second scenario where this could fit is when we are expanding our base We want to fight into the fog Want to kill enemies in the way while keeping our backline safe So that's another scenario In the second scenario you want to keep that formation going right in the first scenario you just want to go A to B and then form up So different two different ways of using formations And now I can say how hard
04:30 - 05:00 can it be right so yeah we never planned for formations So and the game is live Well it's got to first thing it's got to do is support 65,535 units Now you know the exact number as I promised If you go to a party you can bring this out And if you're a programmer you get a bonus points because it's a maximum of an unsigned 16 bit
05:00 - 05:30 integer And technically we could do more but at that point it doesn't really matter It's just too many units on screen What other problems are there well it has to work with the game that's already live I mentioned that twice It has to fit with the existing architecture It has to be compatible with the existing UI And if you remember the problem at the start it has to be simple You need to simplify the UI and UX How do we do that
05:30 - 06:00 and how do you handle units spread across the map like in other games you could select a set amount of units but in our game you can select them all Imagine selecting all 65 units 65,000 units and giving them a formation command How is the game going to handle that and the map's not empty There's water terrain trees lots of random obstacles in the way So let's make uh let's go
06:00 - 06:30 through them Same challenges in a checklist We'll start with the first one Uh supporting lots of units I'm going to talk about three principles which can be an entire presentation on each of them but we don't have the time So first principle is cach friendly design Usually when you try to access a variable multiple times they may be in
06:30 - 07:00 different parts of memory That isn't very efficient for your CPU So another way to do it is to have the memory contiguous You can get all three at once This is more cage friendly Again I'm just skimming through it because there's an entire presentation we could do on it Now for the second principle let's take it take that array and maybe add another one for target Maybe you want to add the damage to target every update We add
07:00 - 07:30 some helper functions add uh update and remove and we can wrap that into an attack table and then you can have multiple tables You can have a move table You can have a idle hold and that could be part of an agent database And the same principle you could have multiple databases So you can have buildings you can have paths you can have
07:30 - 08:00 commands and you can certainly have formations So that's where formations can fit in This is a form form of an ECS design and basically it's an array of data inside a table which is a feature inside a database which is a concept So another form of data oriented design Cool And the third principle is passing the minimal amount of information between systems It's not efficient to send
08:00 - 08:30 65,000 units in an array It's it's going to be too much So one example of this is say a position command uh formations for example you want to get units from A to B all you need is a destination and a formation ID And if you want to know what units are selected that's in the selection table If you want to know like we have queuing commands shift commands so you can do one command of the other uh
08:30 - 09:00 that's handled by the command table uh if you want to know where the units are on the map formation table So nothing is in one piece of information but you can get it easily um with minimal information So three principles which is all I'm going to talk about for supporting lots of units right that's the first challenge sorted our second challenge is how does it fit with
09:00 - 09:30 the existing architecture that's live in our game uh we have a game state which produces inputs user clicks a mouse creates inputs and that that goes into the input system and that creates a state So that's handled by the state system and you might have multiple states You might have attack move and so on And I might build this formation system somewhere as an orthogonal
09:30 - 10:00 design and I might read that state and then inject commands to the input system This is good where we can just cut off the blue line and the game is still iterable because this blue line if you cut it off it means formation doesn't exist in the game but we can still work on it on the back end Once we decided formation is something we are really going to do We
10:00 - 10:30 figured this design is very kind of slow because if you look at the loop it's reading the states going to the formation system injecting into the input system and then have to go all the way down before it's right again And that's too slow right so we do some dependency inversion Same same systems we talked about Now the formation system is underneath Doesn't matter how it's implemented but basically we switch who
10:30 - 11:00 reads what So the all the states now know what the formation is what the formation data is and it is responsible for its state So it handles like the formation in that context and it's yeah you just read and do the thing that's it and you might have a starting thing at the start but it does doesn't matter that's the principle Cool That solves fitting into the existing architecture how you could iterate on
11:00 - 11:30 design right so next problem How do we interface with formations now if you look at some games you might see you might have formation as a state like we already have move hold petrol all these commands working in the game But now how does formation fit into this it has to be compatible with all of these commands And we got to think about what if you
11:30 - 12:00 select a group of units in a form in a formation state and one that's not and you give it a move command Do they form up or turn it off so what we ended up with was formation as a command And when you have it as a command you don't have to worry about dependencies You just select a group give it a formation and it's going to be information It's it's a separate command Cool That's another way of doing it We went with the simpler
12:00 - 12:30 approach All right Now we're halfway through How do we simplify the UI and UX how do you implement this and actually solve the three problems we have and is there a simple intuitive approach what we ended up with was a resizable grid something unique So what we do is we start with a position and then we drag the mouse we
12:30 - 13:00 get a direction and that gives us a width and using these three values we can make a formation out of it We know roughly the number of units that are selected and where they fit in the each row And we have an additional thing where we have a scroll wheel which we can move handle unit spacing like make it bigger or smaller So click drag
13:00 - 13:30 scroll wheel you're done Very simple Now programmatically how does a unit fit into a slot well we're going to go a little bit technical on this So three things you need to know Projection in X projection Y and row priority So let's say we have uh someone drags a formation Your x-axis is your forward axis and you might draw a vector from
13:30 - 14:00 the origin to the unit And now we can do a projection a.x We can do a projection y And what about draw priority it's based on agent type Um say soldiers can be one archers can be two but soldiers and pikemen can be in the same row So we give them the same row pri priority So they are one and archers are two So keep these three variables in mind and let's run through
14:00 - 14:30 the algorithm So first thing we do is sort by row priority then sort by vertical projection and then by horizontal projections So when we do a sort by row priority we get all the melee units the soldiers and the pikeman And now this three slots So we do a vertical projection of all of them We get the first three which can fit in our first row and we can do a horizontal
14:30 - 15:00 projection and we know where they go Right now we can do that again So we get go through the next list of vertical projection get the next three units do a horizontal projection and we know where they fit Once that's done the next row priority which is the arches and we do the same thing and voila every unit can fit in a
15:00 - 15:30 slot Cool Now we go into a little bit of code So same principle actually this code is not age of darkness code is heavily modified for the for the um presentation and people that worked on age of darkness is like what the hell is this I never worked on this way too clean so same principles well not principles uh algorithm priority number one we sort by
15:30 - 16:00 priority and then we sort by vertical projection Then we have a middle step We create rows and add agents into those rows So the agents are sorted and we try to put agents If if they have a different row priority they're probably going to the next row priority So we move them we create a row for them and you chuck it at the end If they do fit in that row priority we try
16:00 - 16:30 to put them in If they fit they fit If not we do the same thing again create a new row and chuck them at the end And then finally we do another sort the final sort which is horizontal projection on each of those rows And you get the idea you saw before the last few slides Cool That solves 60 80% Right so all of this works from get
16:30 - 17:00 getting units A to B and then forming up Now if you want units to move in formations there are few other challenges So one of them is units spread across the map I hope I'm not going over time for you Jack Should be fun All right So imagine units all over the map You select them all and you give them a muk map Do they form up and then move to the destination or do they form up while
17:00 - 17:30 going to the destination lots of questions What we ended up with after iterating is clusters So clusters are smaller formations part of a bigger formation and each cluster has a leader So the cluster follows the leader and we try to choose the centermost unit for as a leader because it works better in corners and
17:30 - 18:00 turns and the nearest clusters merge And if a unit can't keep up with a cluster we take them out and they can become another cluster And the cluster generally follows the leader It has its own move speed It has it own rotation And we can tweak those to make it smooth and whatnot Add some juice And we have a simple rule The
18:00 - 18:30 clusters move at the slowest unit speed but not slower than some of the units or we have a speed cap basically So the reason we have this is some units don't have animations to walk as slow For example Edwin can't walk as slow as a catapult and it doesn't feel good It's not great in ter when we play it So we have a speed cap Another problem is there with uh moving in information is say Jack is a a
18:30 - 19:00 monster or an army of monsters and I'm a soldier I'm a formation attacking him and the player decides oh this is risky There's too many jacks I need to go back So what happens is the soldier moves back right the archer wants to be behind the soldier and decides to walk behind the soldier while Jack is killing him or
19:00 - 19:30 her That's not good So how do we solve this really simple You check the direction of the soldier Check the direction of the archer If they're going towards each other then you get the uh get the back line to wait for the front line So that's a simple dot product That's it We solve all the challenges almost Last one's a tricky one Very tricky The map's not empty It's got
19:30 - 20:00 stuff Design put a lot of stuff in there Well how do we juggle formations without handling all the edge cases with water and terrain and so on so what obstacles are we talking about well one is a narrow passageway You have a formation that's going together It has to squish down and then come out the other end How do we how do you do that another sort of obstacle is a giant
20:00 - 20:30 boulder in the middle Do I go left do I go right do do I split into two many answers And another form of obstacle is at the destination We give a formation but then half the positions are cut off Right for the last one we could probably think of moving the units a little bit outwards And that probably solves the
20:30 - 21:00 last obstacle But what about the first two um there was a few thoughts about signed distance field Uh very hard problem and we just solved it with removing units that can't position and we just give them a cool down before they merge again That's it And this pretty much solved the first two If you had more time we could definitely
21:00 - 21:30 try sounded distanceful flow field But uh yeah something to think about We solved all our problems all our challenges Now have you guys ever shipped a feature that you're really proud about and you hear crickets that means you've done really well because if you haven't done it well you would probably they'll make sure you
21:30 - 22:00 know about it But luckily we had good feedback and so we end with some key takeaways Um so you can support lots of units with ECS Again there can be a whole presentation We don't have the time and I'm cutting to Jack's time a little bit You can use mass uh that was made after we were iterating on the system So it's already too late but you guys can try it Um architect based on your use case
22:00 - 22:30 like don't just architect Think about your production like what works for you and then switch if you need to Um solve problems that are specific to your game Like you might see other games do certain things we may not fit your style right think about how it solves your problem Dot products are awesome Entire formations solved by dot products Doesn't have to be complex Solutions can be
22:30 - 23:00 simple It doesn't have to be complex And formations wouldn't be possible without a strong path finding system under it And that's that brings us to our second section of the talk Very exciting Let's go Well you can't arrive in style if you don't know where you're going Which is
23:00 - 23:30 why I'm going to talk to you about the custom path finding in Age of Darkness But why custom path finding why didn't we just use Unreal's built-in nav mesh system why not well unfortunately it has bad performance Uh Nav Mesh runs fine for sub 10,000 unit counts but once you start going over a thousand units you'll notice the frame start to dip a bit It's also very hard to save and load which is key for a multiplayer game when you're trying to sync up data across different
23:30 - 24:00 players But the most crucial to us making a multiplayer game is that it's not deterministic Determinism if you've ever made a lockstep game is crucial and something that Unreal does not support yet So what did we use instead we used partial flow fields So what is a partial flow field why did we choose them and what are their limitations well just a quick overview Uh partial flow field is a
24:00 - 24:30 layered path finding technique We use a lowresolution node graph that creates a cheap lowdetail path and then we layer on top of that a high resolution flow field to do the unit steering around complex geometry So what is a a lowresolution node graph well it's a collection of nodes which represent space in the world and then connections between those nodes creating a graph indicating that you can
24:30 - 25:00 travel from one area of the world to another What's a flow field well a flow field is a grid of tiles where each tile contains a direction or a flow that agents can follow to get to a destination So that's an overview of what partial flow fields are But why did we choose them well they scale a lot better than nav mesh and aar for large unit counts They have less overhead than a full map flow field That's where you build a flow field for every tile
25:00 - 25:30 instead of just local to the character And they've got a lower first frame cost than other pathfinding solutions They can also share their flow fields between agents traveling to similar destinations But sounds amazing Why isn't everyone using them well they come with a few limitations First up they have a higher single agent cost than AAR or Nav Mesh or almost any other pathfinding solution which is why Unreal doesn't use them They also have a higher total cost
25:30 - 26:00 than other flowfield methods For example if you build a full map flow field you only have to build that once whereas if you build a partial flow field that has to be rebuilt regularly as agents move through the world And finally and probably most importantly they're less accurate than almost every other form of path finding but we'll get into that later They also can't share their flow fields as agents get closer to their destination which is a crucial problem with a lot of path path finding
26:00 - 26:30 solutions So that's an overview Uh let's talk about how they actually work under the hood So partial flow fields are a collection of systems As I said before a layered path finding approach One layer is a low resolution node graph the other the flow fields Then we have a cing system to share the flow fields and paths between agents And finally a short path solver to help get around the issue of not being able to share flow fields for short distance movement So starting with a low
26:30 - 27:00 resolution node graph uh it creates a low resolution low detail estimated path with an estimated length It's not quite accurate but near enough So how do we make it first we need to split the map up into sectors In Age of Darkness we used 16 by 16 tile sectors which if you do your maths gives you a nice 256 tile count which fits inside a bite And once we've broken the map up into nice bite-sized chunk sectors we then
27:00 - 27:30 need to discover the traversible islands inside each sector We do that by looping through all the tiles in a sector until we find a traversible tile and we assign an island number to it and then we flood fill out from that island filling all the traversible spaces attached to it We repeat this process until all the traversible space in a sector has been given an island number So now we've got a traversible island
27:30 - 28:00 graph We need to find the portals to go from one sector to the next To do that we loop through all the tiles on the edge of the sector And if there's nothing blocking the movement to the neighboring sector we start a portal And then we keep on growing that portal provided there's nothing blocking it And once we do find a blocker then we finish that portal and store it in our portal list So now we've got our uh islands we've got our portals we just need to
28:00 - 28:30 tie them all together to create our low resolution node graph So first we take each portal and find the island that it links to and then we add it to a list of per island portals Once we've done that we measure the distance between all the portals attached to an island and build a connection set and then we're done We have created all the data for our low resolution node graph So how do we use this to find a
28:30 - 29:00 path well it's very similar to just a stock standard uh reverse AAR search We start at our destination and use our island number to get all the available portals Then we just use standard AARistic to pick the portal that's most likely to be used We expand that portal uh and add all the portals in the neighboring sector And then we just repeat this process over and over until we found a path from our destination to our start
29:00 - 29:30 point So that's our low resolution node graph Next up the high resolution flow field The flow field provides a high resolution highdetail path that agents can follow Uh an important note is the closer the transition from the low resolution to the high resolution node graph the lower the quality of the path is And for that reason age of darkness uses a 3x3 sector flow field region
29:30 - 30:00 where only the central sector is actually used for steering agents whereas the surrounding sectors are used to add accuracy to the path that we create So how do we make these flow fields well it's two-step process We need to do distance flooding and then a direction calculation So starting with distance flooding first uh similar to flooding a maze with water we seed a tile with a distance and mark
30:00 - 30:30 it as active Then for each tile attached to the active tile if it's got a neighbor that has a distance that's plus one to the tile we're looking at we set that tile to the active tile plus one distance And then we add the neighbor to the active tile list And then we repeat this process over and over flooding through the sector and setting the distance from the C tile to all the other tiles So once we've done our distance
30:30 - 31:00 calculation we need to turn that into a direction that the agents can follow And that's where we do our direction calculation To do that uh we just need to take our distance field that we've already calculated and convert it to a flow field or direction field So we loop over all the tiles And then for each tile we find the neighbor with the lowest distance store the direction and that's it We've now creation created our flow field So yeah that's flow field creation
31:00 - 31:30 But just creating them isn't enough We need them to be fast And that's why we need to do multi-threading on our flow fields So how do we multi multi-thread our flow field creation well the first key is to split our flow field up into a bunch of smaller flow fields and then flood each of them in parallel and then transfer the distances between those sectors until we've finished our flooding process So going
31:30 - 32:00 deeper into the algorithm first we seed our first flow field with the distance Then for all the active sectors we flood them out in parallel We check the distances along the edge of a sector to see if they've changed And if they have we mark the neighboring sectors as active Then we loop through all the active sectors copy the distances from its neighbors into them And then we repeat the process flooding all the active sectors flagging the
32:00 - 32:30 boundaries transferring the distances And we just repeat that over and over until we flooded all the sectors in our flow region Once we've done that we take the central sector which is the one we're actually going to use for pathing and do our direction calculation and then store that in our cache or use it for steering So yeah that's the high resolution node graph Next up our path c It's a lot faster to reuse a path than it is to recalculate it And for that
32:30 - 33:00 reason age of darkness uses two layers of cing First we've got the full path cach which ces a path from start to end And second we've got the flow c which just ces the flow fields that the agents use to steer So starting with a full path cache each path we calculate uh calculates a hash based on the start sector and end sector that it's going to Any future path can calculate its own
33:00 - 33:30 hash and check with the past past paths to see if it has a matching hash And if it does fantastic We can just use the pre-existing data and skip all that work If it doesn't well this will be a unique path that we haven't seen before The second type of cing is flowfield cing The flow field stores each uh flow field based on the portal that we flooded out from So each portal along the edge of a
33:30 - 34:00 flowfield region is given a number and then for each sector we store an array of all the flow fields indexed based on that number So if you have two paths that are traveling through the same portal they can share the same flow field which saves us a whole host of calculation Uh a good way to think about this is if you were traveling let's say from the Gold Coast at Brisbane most of your path is going to be the same traveling along the same highways going around the same corners And for that reason you can
34:00 - 34:30 share the same path with a whole bunch of other cars even though the end destinations are vastly different So that's our path c The last thing on our list is our short path solver So short paths uh the short path solver handles paths that are smaller than that 3x3 flowfield region And that's because paths inside that space aren't going through portals and can't be ced and
34:30 - 35:00 shared And if we're not sharing them then they're very expensive Flow fields are only efficient when they're shared between many agents which is their one strength For that reason if we can't share the flow field we'll try and switch back to line of sight if we can or AAR which are significantly faster for single agents So starting with line of sight most paths are short If you think about your standard RTS game you're doing small micromanagement moving units
35:00 - 35:30 sometimes fractions of tiles And this is especially true with formations which are often steering units less than a tile away to keep them in line with the other soldiers Standard 2D raycast algorithm works perfectly fine for the majority of paths AAR well I'm hoping you all know AAR It's a pretty common algorithm at this point uh AAR paths in Age of Darkness only happen within that 3x3 sector
35:30 - 36:00 region which is really helpful because we already know the worst case memory usage and each AAR path search can be very easily multi-threaded and that's it We've gone through all the different tech stack We've gone through all the different techniques Let's bring it all together We use our lowresolution node graph to find a general path from our end point to our start point We use our flow fields to do the actual steering around obstacles A path c lets us share paths
36:00 - 36:30 between multiple agents And if we've got line of sight we can just switch back to our shore path solver for terminal guidance as we get close to the enemy So yeah 10 out of 10 work first time No issues Well unfortunately no There was tons and tons of problems with the partial flow fields in age of darkness So just a brief list definitely not an exhaustive list of the problems we faced We had poor path selection agent splitting up and constant
36:30 - 37:00 conflicts between the high and low quality pathing So starting with poor path selection we'd often find agents would take less efficient paths either through complex terrain or swinging right around corners Just they seemed lost So what was the cause well the primary driver is the low resolution node path It just doesn't know what's inside a sector It only knows the line of sight distance from portal to portal So from
37:00 - 37:30 its perspective uh the design the path up ahead in green seems perfectly reasonable The other issue we came across was flow fields not having accurate start point So starting with the low resolution issues Unfortunately this is just part of the technique The whole reason partial flow fields are as fast as they are is because we're using rough estimations to generate our paths But we can hide some of this low
37:30 - 38:00 information path error by expanding our flow field from the original one by one sector which we had at the start to a larger 3x3 sector This allows the terrain detail like that maze-like structure to be captured in the high resolution flow field and allow the steering to steer around it instead of through it as we would be forced to with a smaller flowfield region The next problem the flow field
38:00 - 38:30 start errors The low resolution node graph only knows what portals you're going through not where on the portal you should be going through And that causes unfortunately a lot of problems By increasing the flow fields again to a 3x3 it helped move those errors further away from the agent you're trying to steer and hide them completely in cases where we're going around corners And that helped us significantly with our poor paths
38:30 - 39:00 problems Next up agent splitting which was an issue we never fully solved unfortunately So what's the problem groups of units would split up and take different paths around blockers Small groups would be easy to die and agents would get uh players would be very angry as a result So what was the cause of this well agent groups that were set on uh sector boundaries were seem to be the primary cause And the two reasons this was happening was again the low
39:00 - 39:30 resolution path finding and how it picked its start and end points as well as the flow field start tile again So what was the problem with a low resolution path start and end when we were doing our low resolution path calculation we would snap the start and end locations to the center of the sector not to the agent or the destination we're going to This meant that two agents that might just be a single tile apart will be doing their
39:30 - 40:00 low resolution search from as much as a sector distance away from each other This caused a lot of the paths to pick different uh paths around blockers and caused lots of issues as you can imagine So what was our fix well we divided each sector up into four start and end regions Then agents would pick the closest start and end region uh when they were doing their path finding search That reduced the difference for the start and end search from a full sector to half a sector in most
40:00 - 40:30 cases We could divide it more but unfortunately the more you divide it down the more it splits up your path finding searches and breaks your cing making the whole process less and less efficient The other cause uh the flow field start tile As I said before the flow field only knows what portal to go from not where on the portal to go from And this would cause agents to steer to the center of the portal So if
40:30 - 41:00 two agents were in two neighboring sectors they'd be steered away from each other when they were going to the portal at the edges of those sectors which is what you can see in that diagram So even without any train blockers units would be splitting up just on their own which was very frustrating So our fix uh kind of was we changed where we started our flow field flood from to the tile that was closest to our destination This helped steer agents
41:00 - 41:30 closer together and reduce the splitting although didn't solve it fully unfortunately And by doing those two things we managed to reduce the amount of agent splitting quite a bit Now on to the final issue the conflicts between the low resolution and the high resolution pathf finding systems So what is a conflict between a low resolution and high resolution pathf finding system well the low resolution pathfinder would pick one path through terrain and then
41:30 - 42:00 as an agent gets closer to that terrain object it would switch from the low resolution to the high resolution We depending on where on the map is and how far away from the destination it might be the flowfield system or it might be the AAR system that gets used Once it switches to this high resolution system the high-res system would pick a completely different path to the destination Because it captures the complexity of terrain it would often pick a path going around the blocker instead of through it as the low
42:00 - 42:30 resolution pathfinder does As the agent follows this new path it backtracks the way it can switching back to the low resolution pathfinding system This would cause the agents to spaz out and get stuck on the edge of the sector switching continually backwards and forwards between the high res and the low res path finding Fortunately these conflicts are rare You need very specific train like the image I have here for it to happen And they're also relatively easy to detect If an agent is getting polar
42:30 - 43:00 opposite movement commands one after the other then there's a good chance it's stuck on a sector boundary When this happens we just switch to AAR and force it to steer to the next low resolution portal and that solves our problem And with that we fixed all the major problems Were there more issues yes Do we have to time to discuss them all definitely no So finally some key takeaways Unreal
43:00 - 43:30 is not a solution to everything I know it's tempting to think about you know what off-the-shelf Unreal tool can I use to solve this problem but sometimes there just isn't one Partial flow fields are a great pathfinding solution if you need to support large unit counts and a very dynamic rapid game And you can combine different layers of pathf finding techniques to create a partial flowfield system like we have relatively easy But combining different layers and especially
43:30 - 44:00 different levels of accuracy in your path finding is very prone to error and we'll have many edge cases you'll have to cover And with that that brings us to the end of my talk If you'd like more information uh here are our contact details our LinkedIn So if you want to take a photo now is the time And we also have uh some slides available online if you want to go through them at your own time Thank you
44:00 - 44:30 [Applause]