Massive Crowd on Assassin's Creed Unity: AI Recycling

[Music] well hello everyone so we are here to talk about crowd this talk has been uh prepared by me and at 140 thing right there so uh when you see us on the street come and say hello so uh first i've been have to remind you to turn off your cell phones and then rate me after their show or not if you didn't like it all right so let's get started so i don't know if you've played the game but on assassins unity we have been able to build these truly huge massive crowds so in this scene for example we have a 10 000 pcs that the player can interact with them so how did we do it well i'm here to answer that but first let's give a bit of backstory because everybody does it so if you remember the first ac1 e3 trailer you can see altair walking through a crowd trying to reach an execution so it has really been in our mind since

the beginning of the brand to have like these really really huge crowds that the player could actually be stealth in and we also we also thought that it would give a sense of life to our cities but we were limited actually our ais were really costly and we could never have these big big crowds the limits themselves was of 100 npcs that's really small and that's for all the possible npcs spawned at one point this means that this accounts for guards accounts for people imported for gameplay so uh if you want to have like a budget for like decorative civilians you're left with about 20 npcs out of these 20 npcs you have to spread them like across the whole loading range which leaves about four around the player so that's obviously nowhere near a crowd we were able to build some crowds before but in specific missions where we have full control over like the resources we have

but we never could do systemic big crowds so were we doomed well no in assassin's creed 3 we integrated technology from an old prototype and we were able to like display thousands freely cheap mesh that could play simple animations we used it for the rats and the birds that you've seen in ac4 and ac3 and the most memorable sequence is the bunker hill sequence of assassin's creed 3 where you see this army of thousands of people in front of the player there in the bulgarian sequence it's really only meshes uh playing as simple like a get down reload animation so there are no entities like over there and they are far away from the player the player cannot interact with them because they are only measures so is there a way to link the legacy eyes that we've had in our games and link them to the really cheap mesh that we've built on ac 3 and 4. well yes we created the new system we call it the bulk system it's called the bulk system because of

the name of an old prototype but call it the bulk system each member inside the system is called a bulk so when i talk about an individual it's a bulk so the main idea behind it all is that we have these thousands of really really cheap mesh we have a pool of uh pre-spawned npcs and as the player gets close to the cheap mesh we basically replace them with a guy from our pool so it's really based on the distance our we call it like an ai lod system and there are three possible states so i'll go over the states briefly the closest one we have is the loras bulk so this one is the furthest one he's at 40 meters away he has no entity so this guy is only a visual that can play animations and cheat animations so he has only 2 000 polygons and he has only 11 bones so his animation system is really really small and runs fast he also has a really basic

reaction system now on the other side so close to the player you have the autonomous bulk this guy is mostly a real and pc so he has an entity with all the components that a regular entity have so uh yes have a clot full ai so he's like a real npc but he is super costly so in our game we can only have 40 of these autonomous bulk so the goal is to link them with the low res so we created an intermediary state the puppet bulk state so uh this one is a bit of a mix and match between the two so he has an entity but all the components are off is he only has the visual components of this entity all the logic avoc and everything is off so he's running using the cheap animation system cheap collision system and cheap reaction system that the lores is doing so if we see them next together we see that on the left side you have the low res bulk so here

the mesh is really really ugly so it looks like a guy from an n64 game and the animation i mean it doesn't look real it's bulky it's not it doesn't feel right on the right side you see the autonomous bulb and i mean the stance looks good you can actually see uh like facial expressions but not on a steel but yeah way if you're up close you can see it so the stance is good the mesh is really good also and you can see the metal the the puppet bulk as a bit of the two so he has the visual but he has the stance of the low res so these are our three states remember them well because i will be referring to them like throughout all the presentation so uh basically the autonomous bulks are up to 12 meters from the player from 12 to 40 meters we have the puppets and then all the way back there you have the low res block at 40 meters so a bit on the cost like to explain why we use this approach the cost for low res

is actually 25 microseconds so they are super super fast the puppet one is 150 microseconds it's mostly to take into account like the higher resolution mesh that needs to be computing so that's why it's a bit heavier and finally the autonomous so this guy can cost from 0.5 milliseconds to 5 milliseconds if he's doing complex reactions so that's like the idea behind this whole system is to limit the amount of autonomous because the difference in the cpu is 100 to 1 between the low res and the autonomous and to render all the similar meshes of the lores we use hardware in sensing all right so a bit on the differences between the two because they're really really different uh like how we think about them so a real npc the autonomous bulk has infinite permutation this means that when we spawn one of these guys it can be of any different uh he has you can have any different face you can have hair a beard so every time we spawn one

of those guys they are completely random using our random system from assassin's creed the low res though the lores have really specific meshes this is done to be like to optimize everything so they have really a fixed number of meshes this and this goes fast so we only have 29 and uh for example if you have a poor male civilian a rich male civilian female poor civilian so i mean you cannot go up to 29 really quickly so we don't have lots of variety of lores that's really important to know but they are far away from the player so it doesn't really matter now the difference in polygons the closest lld of a real npc is 2 20 000 polygons and on the other side you have about 2 000 so i mean obviously it's a lot faster to render the cheap ones now on the animation side you have 300 bones for the real npc so they can do full complex animations but with 11 bones the lorez cannot do much and that's why they usually have like their ends spread open

because you don't have bones for the ends themselves now the low res bulk of a specific system basically we limit the total polygons for the low res this means that if you have many many many lores in front of the camera we'll actually limit the amount of polygons to 300 000 this means that if there are many many low res we basically tone down the leds of everyone to make sure we fit in our budget so this is how even if we have 10 000 guys we still have the same cost all right so uh how do we like recycle this polygon how can we make it fast we basically have a culling system so that we basically only uh so we only display uh the bulks in front of the camera this means that if i look at the top view of when the player is turning no bulks behind them are actually drawn so this this saves us some polygons obviously and when they are not drawn they are they actually compute reactions but uh so but no animations and

obviously they are not displayed so they go pretty fast so uh i'm coming back to this slide now uh you remember the autonomous and the puppets they actually only live inside a cone in front of the camera because as we turn around we basically move them to the low res so that they are cheaper to compute all their logic and we do not display them anymore so we only have the autonomous and puppet box in front of the camera all right so the cheap animation system so it's really really stuff from the 90s so it's super fast it can support like two blending animations we play uh uncompressed animation so everything goes really really fast we basically scale animation depending on the scale of the model and their main their main thing about them is that they have stiff ends that's like the giveaway if you see defense it's always either a puppet bulk or a low res ball so here in this animation you can see them that they they have like these big spread open ends and the ends are not correctly on

the arms of the chair because uh we have only 11 bones so the calculation do not like give the correct results but this is from far away so the player does not see that ever and we also built our own collision system obviously we cannot have 10 000 npcs running evoc ava would cry so uh we created our system we basically have a partition map where we have the location of every npc on the world and then for each bulk we detect if he's ever in inside a range of another npc and if it's that's the case then we play a simple animation and we slide them so it's slides see it's not like a real physical collision and then we always clamp them on that mesh that's super important this means that if they start running since they have no capsules they could have entered a building or anything but by keeping them on navmesh we make sure that they are always at least not inside a collision and it also enables them to walk indoors all right so let's take a look at this

collision system so uh here you can see guards uh walking to the crowd so uh again when there's a collision it's we do basic sliding it's not perfect it it has interpenetration but again all this occurs far from the players so from a distance it actually looks pretty good all right so a bit on the ai now the legacy i use is like big state charts it's super complex it can and all uh every event every reaction lots of randomness and it's all even based and it's super super slow it's actually mostly running in the in single thread so i mean obviously as it scale up it's costlier and costlier so we had to build our own reaction system so we basically created really really small scripts so these scripts are simple like go to standstill animation and by like linking them together we can try to recreate more complex reactions we always try to follow what a real npc would do but it's not as good obviously so

i'll take for example the smoke bomb reaction so when a smoke bomb explodes you see the npcs and the smoke uh like moving their arms trying to navigate out of this mode now uh let's take a look at the loras version of that so uh basically they they start reacting so they stand still play animation as the animation finishes they turn around and then move away so you kind of see a glitch you kind of see that it's not perfect it's not super seamless but uh i mean when the density is right this one i cranked it up to the max it looks good so this is the real reaction so you see now they have ends and everything so this one is obviously fully realized and this is the one that occurs close to the player so uh we can get away with cheaper reaction if they always happen far from the player right so uh where did the bulks live because i mentioned earlier that the lauras don't have an entity so we need to have them somewhere so we basically created shepherds shepherds are really like containers

holders so the bulbs themselves we never spawn them but we spawn shepherds shepherds will contain all the ai it's them that run the logic script i talked about they will push the animation on each individual so the other one controlling the box so uh each bulk uh inside a shepherd has a unique id so uh it can actually be referenced from inside the code but uh usually we work the shepherds themselves so we don't spawn balls we spawn shepherd and when a shepherd spawn it allocates the memory for all its members so uh i mean the spawning is really fast and when for example the shepherds bounce you can see thousands of people appearing in one frame so uh typically in paris we have 2 000 bulks and counting all the shepherds it's about 30 megabytes so it's really really cheap and all the shippers are placed by level designers so this is how the level designers can actually interact with our system they play shepherds and it

creates a bunch of people so every time a level is on your place as a shepherd they can select a count and a density when they do we basically randomly generate the positions to feel like the bounding volume of the shepherd they can actually and manually edit the position of each bulk but i mean doing so obviously takes a long time but they can do it if they want to uh we also give tools to script shepherds so for example the mission designer could have all the members of a shepherd start rioting or they can have all the members flee so the mission designers can play with the shepherds they can never play with the individual we didn't give this power so uh for a scene in a mission for example you can see that the mission design replaced lots and lots of shepherds on the left for example you can actually see them like separated they are like these big squares of people on the right you can see that the density of some separate change so it's really end place by level designers

so uh to see a bit how it looks so this on the left you can see a shepherd but on the right you can see that you can actually and go and manually exit all the position of the bulk inside the shepherd and the cool thing is that when we save a shepherd we save all the position and every time a shepherd spawns all the members are at the same position so and this is the basis of all our networking so when two client spawner shepherds all the members will add the same position and will have the same id so our system is deterministic now uh we only have like i talked about static people but it would suck to have a city full of static people so we need wandering people so we created something different for the wandering people we have a unique shepherd that we call the wandering shepherd and basically what we do is we randomly generate closed paths so that bulks can walk around these paths always staying in the map and the way we create our determinism is that for a fixed time

we know the position of every bulk on each path this means that if you're over the network and you think that the net time which is easy to do then you you think the position of every bulk using this system so this is again how we do our replication for this system also every path is generated in a region of paris and depending on the region you'll have different models on those paths all right so this is what the paths look like so it's a bunch of lines where the bulk walk around in circle this is done in a test map but in paris those paths are super huge and uh you don't really see uh you you cannot like see a loop unless you play like 20 minutes following a guy so i talked about the lores now i'm gonna transition to like ugly link with the real npcs so the link comes from a pool so uh this is where we hold all our pre-spawn npcs so basically inside each lores we store

a tag and the pool takes all the lorries around the player and then counts the tag so uh for example if there's 50 poor male civilian and 50 rich male civilian then the pool will try to have 50 percent of each mesh inside its pool so it's very statistically based and it's changes every time every frame depending on the position of the player and uh obviously the more models you have the the more that the pool will be spread so it's going to be a lot harder to have like the right mesh when when trying to change low res from the top for example so i'm going to show it a bit in action so i'm going to show you the game running with the bug display so on the display you can see two pie charts the one on the left you'll see that it represents what the composition should be so a model is a different color and on the right side you you'll see what the pool actually is so i'll show it in action uh this is done

in the debug mode so it's gonna not gonna run will you need but actually but you can see the pipe charts so uh when you we run it you see that the pie chart on the left is actually always computing what the density should be around the players and the one on the right is trying to adjust the one on the left now in our engine we are limited to only uh spawning one npc per frame so the pool will take time to adjust so you can see that the pie chart on the right takes time a bit to adjust to the left all right so now we have our pool of written pcs and now we can build our puppet bulk state only to refresh your memory the puppet ball state is the one where we have a high quality visual but it's still behaving as a low res so uh basically what we do is a way we the pool looks for the loras it asks for the best matching uh like npc it has in its pool and then makes the swap we try to get the best one in our pool but it's not always the case i mean it's

statistics it could fail so for example if we need a poor male civilian and we only have a rich male civilian we might do the we might do the swap anyway and you will see like visual popping but i mean if if it needs to be uh uh if the bolts need to interact for example then we actually need to do the swap so we don't care that we see a visual popping but usually when the regions are well set up you don't see this popping so we swap we take the mesh on the pool place it on the low res we change color we disable the components to make sure that only the visual of the entity is still there we match the apps i'll come back to coloring hats in a bit and then we do some remapping of the bones because if you remember our real entities have 300 bones but we are gonna play eleven bones animations on them so you're gonna see this ugly mess on the left so uh here we we had problems where for example we have only one torso bone so we didn't have enough bones to do the full curvature of the torso but the neck was

at the right place so that's why it's super stretch so we needed to do some remapping of some bones to make sure for example that our torso bone always look at the neck so that you can see that on the right it's looking good so uh let's take a look at this conversion i talked a bit but the videos are better so uh here you can see it in action so uh again the conversion happens at 40 meters from the player so this is far away and i mean you don't really see any visual popping because it's so far so these are perfect condition and it works really really well so i'll come closer and then you'll start to see to see it more in action so now you can see the visual popping so every time we replace the low res mesh with a real npc you see that the shape changes a bit the color changes a bit so it's not perfect but everything is based on distance and from far away it's good enough so now when we

do this matching we match colors also because our low-res models have a different shader than the like real npcs we needed to develop a specific color matching tool so that character modelers can see the cheap mesh the real mesh and then manually select which transformation it needs to do to measure colors so it's obviously really long it came at the end of the project and uh you can definitely improve this obviously and then finally ads apps are like how we cheat basically as i mentioned we don't have many models so uh how do we create variety but we found that uh if you have like lots and lots of people inside a crowd you actually only see their ads and by having a variety of ads you can actually fake that you don't have a huge variety of models so we developed a system that to have like different ads on bulks the way we do it without having to respawn an npc from our pool is that every time we spawn an npc in the pool it spawns with all possible ads so that when we apply it on the low res we only uh display the right ad

so now our final state the autonomous state so for the bulk puppet state at the entity with the components up so obviously to create the other one you turn them on so that's the autonomous bulk so that guy has all its component on so it has full avoc clocked ai so it's a really legacy npc from that point on it's still part of a shepherd so it still has an id but it's not controlled by it it's fully autonomous and why we call it that so this the eye is easy i mean only one slide but it's not the case this one is the trickiest because basically when we turn it on you need to remember that it came from a pool so it has been recycled it had been it has moved around a bit so you need to reset everything that's everything so if the bulk was jumping in the air giving back to the pool and put on a fleeing bulk then this entity needs to have all the variables set up properly so we needed to go into all the legacy

system and make sure this was supported obviously i mean we add some glitches but we managed to do most of it we also need to start the ai in the correct state so for example i'll i'll come back to the smoke bomb so if the the reactions start by moving their ends and trying to get out of the smoke so if you come near a low-res ball that's leaving the smoke area and then it starts its real logic it must it must skip the moving ends part because it's already out of the smoke so it needs to start the reaction after the ends and start at the correct place so all our ais our reaction need to support uh jumping in the middle of everything so again that's a huge task and you need to like refactor a lot of old systems and obviously it needs to be fast resetting everything restarting all ai is costly in some systems but i mean we needed to do it really really fast because this can be done like five six times in one frame

all right so let's take a look at it a bit so uh now we see this conversion it happens at 12 meters so uh don't look for visual popping now it's uh not a visual transition it's a behavior transition so look for a b of your differences uh what i mentioned earlier the giveaway is the ends so uh on the right side you can see that people walk with these open ends and they have like a not an as good white cycle but when they transition you see that them oh they start using their hands they start using their heads so uh when they transition they are like real npcs from that point on i'll show it in slow motion because that's easier to see so and now he has these open hands he's a puppet bulk and then he's walking he's walking he's walking and then uh when he transitions actually you see his end coming together he'll start moving the arms moving the head you see that he doesn't have the blank stare anymore it has a full facial expression so now that guy is is like a real npc

but when that happens from 12 meters and up we found that the player really does notice the difference so now you're stuck with all these autonomous bulk near the player so the player needs to be able to interact with them and the guards also and other real npcs so easy but not really the thing is again this entity is apart from a pool and it will change all the time if you remember like my in my first slides when a camera moves around all the autonomous bulbs are shifting away so the entities are giving back to the pool and assign on another so we cannot store pointers to those entity so that's a big trick i mean when you do the reaction you can never store a pointer to an entity on a ball so we have to develop our own smart pointer system that uses the bulk id so that when you actually uh query an entity using the bulk id it gives you the entity on top of the bulk at this moment so it's obviously we needed again to go into all our old reactions and re-edit them to make sure it supports

having the entity change in some cases we judged it to be impossible i'll talk about one of our gameplay loops the accusation loop where if you kill somebody there's a possibility that a civilian will start yelling it will attract the guard talk to the guard point the player and then after guard chase the player all this long reaction does not support like changing the entity super well so we had to develop a fallback system so our fallback is pretty simple if there's ever a need to have a really really complex reaction we spawn right there on this frame a real npc and we replace the ball so after this fallback happens this bulk is not a bulk anymore it's not even the same entity it's a new guy doing a real reaction it works but it's super super costly when we do that it's a five millisecond hit minimum and then uh on assistance with unity we have a limit of 60 real npcs so you're basically pushing

one more in pc on top of that so it can unbalance your resources so let's take a look at this fallback in action this one is really really hard to explain i saw i tried my best here you'll see i put some spheres on top of my bulk so as long as he has those fear he's a bulk and when i will kill the guard you'll see the sphere disappear this will mean that he will have changed so now it goes pretty fast this transition is totally seamless because we take an autonomous bulk which is basically a real npc and replace it with another real npc so we can swap things really easily so uh looking at it in slow motion so now i kill the guard and now he has changed this guy is not the same one as the guy that had the spheres this is a completely real npc and he has replaced the ball completely and this guy can now do the full complex reaction it looks good but it's super costly every time this occurs again it takes a five minutes to get it so we tried to avoid this reaction like

when possible the cool thing though is that now these guys are real in pc and it is fully replicated so let's talk a bit about replication because i mentioned i mentioned it a bit so the networking uh the the things we did is use the deterministic system so all the all the shippers have bulks in them so their positions are all deterministic as i mentioned before so it's all good but then when they react it all goes to hell when they react they move away and then we don't we cannot keep the determinism and we did not want to replicate thousands of position logic and everything so we basically replicated only the reactions themselves because we assume that if a bulk starts uh i mean they all start at the same position so if we can only replicate the reaction element then they should mostly do the same thing which worked actually uh the bulks i mean at a certain position

would all flee with all react i mean the our reaction system is not deterministic so we could have uh discrepancies between position but i mean since the bulks themselves are mostly decorative civilians we don't really interact with them then it's not a problem if we ever need to interact with them and they're offset too much then we use our fallback that i mentioned earlier and then it becomes a real npc fully replicated if you ever want to learn more about the replication of real npcs you can see a charla 5 stock on friday all right so let's talk about performances because we like that so we basically use 20 of the cpu as you can see on our left back chart so that's for an average of uh 2000 bulbs so uh that's not huge if you think about it that's 2 000 pc on screen and only 20 of the cpu so uh i mean we worked a lot to have like these good results on the right side you can see this is like our most uh

craziest mission where we have 10 000 npcs there we actually use half the cpu now it gets a little big but remember that this is a mission and we have full control over the resources so uh we can have like less guards less of other things so that it can always so we can keep it running good all right so let's break this down a bit on the left you can see that for a typical crowd what uses the most cpu is actually the 4d autonomous ball so this is like the basis of all our system this is why we did all that it's because real npcs are super costly so having only 40 of them takes 70 percent of all the cpu time used to render 2 000 bulbs on the right side you can see that for 10 000 pcs then i mean the autonomous bulk do get crowded a bit and it's mostly the shepherds now that take the most amount of cpu time on memory this is where our system shines so uh all the cost is fixed in the system so

uh again the pool has a fixed size the shepherds do not take much memory and when they do spawn they allocate everything so it's super cheap actually for 2000 bulks we only use 230 megabytes of data and when we ever increase that to 10 000 it's only a 20 megabyte increase so uh we end up actually using only five percent of the total ram of our budget so that that's really really good and uh you see that on the right that it's mostly used for the uh graphics of the low res box all right so how did we get like these good cpu results how is it running good well we use a lot of men's trading it's like the best situation possible right you have thousands of guys doing single stuff so everything is super uh easy to illustrate but it's i mean there are so many of them that you need to be careful so we we we did a lot of work to on our profiling tools

and we did a lot on our task scheduling to remove every possible idle times so you can see in my image that our big bulk update task actually has no idle time from the previous task and to the next one so you don't miss any cpu cycles so that's mean that's perfect for us because we didn't waste time we used a lot of luck less coding mechanisms when we could and if we did have to use locks we kept them like really really short so it's a bold world bold words but let's give some concrete example so uh one thing i talked about when i talked about the collision stuff is that to do our collision system we use a map to that keeps all the position of every piece in the world so uh basically we use that map for a collision as i mentioned we keep two maps it's double buffered so for on a given frame we insert all the position of every piece in the world and when we need to do some queries we use the map from the

previous frame so we do have a fast insert method but we don't need a remove method and removing from a map is what's the most costly operation so we can actually have only 1.5 microseconds operation for a 1.5 meter radius query so all that is super fast and this is done by 10 000 people every frame all right so let's it's quick code only to show you that for example on the left well in our big loops we use the intrinsic operation to make it run super fast and on the right when we add elements we use a atomic operation to make sure that we don't actually need luck so all this makes it run super fast all right so what is left to do well lots of things uh obviously the transition the transition is the most probable problematic part of this system either from low rest puppet or from puppet to autonomous on the two sides we can actually do more to improve it in our game we only swap the mesh so

when going from low-res puppet so you see visual popping occurring if we could use our deterring system and do stuff like we do for the building lods to make it if you can like not have it so aggressive in the eyes of the player it it would like help like reduce it like a lot and it would be better better for the enjoyment of the player then we went going from puppet to autonomous i mentioned that we needed to go into all possible behavior you need to start everybody if you're at the right place so that's uh super hard and not like really manageable in the future so a good way to go around that would be to have a unified reaction system so if we could have like a really really cheap script maybe running at the core of the real ais and when they when we turn them on we basically can swap the scripts around and it can go pretty fast then on the networking side i mentioned that when they start reacting it goes a bit to hell

well if we could have deterministic reaction this means that i mean we start with the good positions right all the positions are the same on each client so is there a way to make the reactions themselves deterministic to have them always flee the same way and everything when we do it if we could do it then the position would stay a lot closer to what this should be and then if we can have like better these better reactions synced over the network and we could actually make them a bit more trickier for example all are the reactions in our systems are done like on the individual so a bulk will always react on himself basically he'll flee he'll do some animation go out of the smoke area but he's always doing it on himself if we could actually have interaction so maybe the shepherd could have a reaction running that and those two bulks may be fighting each other then we could have fight in the bulk system and we could like put all our guard npcs inside the system so that more npcs are actually using our pool

and this will help to have even more npcs in our game and if we can ever have fighting between bulks then it would be my personal favorite thing to see two armies fighting each other and be in the middle of 10 000 people fully rendered fully interactable and slicing everywhere that's what i would like to see so uh what is the end result well if you played the game you've probably seen the video i'm gonna show i'm actually kind of scared now because when i rehearsed yesterday i had some glitches in my video so let's let's hoping it works and that the compression worked and let's hope also that okay all right so this is like our big uh looks so uh this is our big uh big mission the king's execution mission where we have 10 000 npcs on screen at the same time so all these guys are bulks and the main thing i want to say is if you ever want to build this system in your own engine because i showed a

lot of stuff about ac but if you want to do it you only need a key simple things so some things to to have lots and lots of really cheap mesh so and that can play simple animation so go cheap go back to your old ps1 code your all the gamecube code and then have lots and lots and lots of really cheap mesh then you need a pool a pool with real npcs and as the player gets close to the cheap ones you basically replace them and then you can have the intermediate state that we have the bulk puppet state if you want to so this was it for me and i hope you enjoyed the presentation [Music] i will sadly not be having questions but if you ever see me or anyone walking around please come and see us and talk to us