The Simplest AI Trick in the Book

all right we have achieved a quorum up here for this for those of you who have not are not familiar with our short form sessions we have three of them this year one of them of course being the rant session which is a perennial favorite and tomorrow we also have a new one that we're introducing a I disaster stories that should be entertaining but this is one that we started a few years ago that has gotten a lot of good feedback over the years basically what we're saying is what is the simplest AI trick in the book that you have used and gotten a lot of mileage out of so let me change the slide decks and I'm going to turn it over to our five guys they have about five minutes each don't blink don't bother taking notes because these things go quickly let's go okay my name is Steve Rabin and for my simplest AI trick in the book I actually have two tricks I'm going to cheat here my first trick is agent reaction time and I kind of just wanted I asked the question if an anti sees the player how long should it be before the AI reacts I mean we intuitively we know there should be like more than zero seconds and less than one but should it be a quarter of a second should be a half a second what should we really choose is our reaction time well psychologists and neuroscientists have been studying this for over a hundred years and we do have some answers so there are several different types of reaction time so there's two I'm going to talk about one is a simple reaction time and this one distort with is just you're looking at a stimulus and the moment you see the stimulus you say hit a button so in an AI context imagine that we have the AI and they're aiming at a doorway and the moment anything comes to that doorway they're going to pull the trigger how long does that take how does it long does it take in a human so we're told by psychologists takes about 0.2 seconds for that simple reaction time if you want to try this yourself you can go to human benchmark comm and they've had millions of people try this and we see that the median time for them is a point two five seconds interesting lean enough this is for vision audio you have a faster reaction time of about 0.15 seconds and fastest of all is touch and it's probably just due to the amount of cognitive processing that has to occur for it for each of those so the other type of reaction time we want to look at is go no-go reaction time so this side let's go back to the scenario with the AI he's aiming at the doorway now through the doorway humans going to appear now they could be a fellow teammate or an enemy so the AI is going to make the go no-go decision do I pull the trigger right anyone who plays first person shooters games make this decision all the time how long does it take takes more time than 0.2 seconds doesn't it you don't want to make a mistake and shoot your two teammate so psychologists tell us 0.4 seconds for the go/no-go so now of course these are baseline numbers and it's always worse than that so if you want to model being distracted you're going to add time sometimes the stimulus is hard to identify and maybe you want to model that you need to add some time maybe you're also kind of the AI agent also needs to aim and you know and that's that takes time too so we just talked about kind of a simplest cases so you probably want to add time in addition to that okay for my second trick it's just a simple C++ trick to correlate in neumes and strings so sometimes we have these enumeration say these messages that the AI is going to deal with and we want to be able to not have numbers in our debug logs or on the screen for debugging information watch strings but we don't have to maintain these two tables right this is a problematic and stuff and and yet and then we don't want to just use strings because you know if you have a string compared in your game I'm going to I'm going to find you and I'm going to shoot you and it's going to be a simple reaction time okay so how are we going to do this we're going to create a file called names H and we're going to put our Anu min here we're going to put the special register a new thing and then put our Anu met and notice that this file has no semicolons so a compile time we're going to read this file in twice one time to create the enumerations and another time to create the strings we're going to use macros and let me show you how it's done so to create the enumeration we're going to do text replacement macros to replace whatever is that X is with X and a comma after it and so we can create the ANU mand it just actually just reads in the whole thing at compile time does all the text replacement and boom we have our enumeration then a second time we define that register new mat something else this time we have this hash mark X comma that's going to take the thing put double quotes around it and then a comma after it and we could read it in create our string table and now boom they match exactly and it will never be out of sync so those are my two tricks if that was too fast you can go to gaming I pro comm and I put these slides up here at the site you can get them and they'll be there for about a week thank you good afternoon my name is Jonathan Adam chef ski I'm a core programmer at insomniac games responsible for our navigation tools and engine systems and my simplest trick today is to do is cleaning up navigation mesh for sunset overdrive so sunset city is the setting of the game sunset overdrive it's a big detailed place there's a lot of buildings a lot of geometry we take all those triangles we feed them into our navigation mesh that the navigation mesh generator we use racast and it gives us back a great big mesh for the entire city one of the problems with this or one of the details of this that becomes a problem is that this is made up of a number of separate islands so to illustrate that as clearly as I can in this view of a building there is an island on the awning here there are three islands on the roof and the ground that big green area is one great big island of navmesh that spans the entire city the problem comes not with those islands which we expect lots to be able to climb over to get up and down off the building but inside the building there are two more islands contained in there and it's these type of islands that are a continuous source of bugs we don't want these islands to illustrate again really quickly shipping container island on the top another island inside it so the sorts of bugs that come from this include performance problems where a bot is trying to find a path from a connected Island so an island to which there is no link a disconnected island and so we spend CPU time doing a path search for something that can never possibly succeed we can there there any number of game breaking bugs that can come as a result of these so say for example an enemies blown up flies through a window on a building which somehow ended up without collision on it ends up inside checks to say am I on navmesh yes I am tries to find paths out can't find paths out the player can't see the bots I can't kill it can't finish the mission unhappy player it's a bug so to clean up this problem in the past what has happened is the design team has had to go through and by hand identify islands that were not connected and try to mark them up and to have them excluded that's a tedious process that's buggy it's something we'd love to do automatically and we were able to do it by saying what do we know about the game world what do we know about the game environment what can we reason about to automate this process what we could reason about was markup we have so take for example what I tried to start with which was spawnvolume so a spawnvolume is a volume place that will find a random location on navmesh inside the spawn volume and put about there and of course you want that that navmesh to be there and so you can use that as a starting point and flood-fill throughout the islands from one to one following the links which you can see that the purple lines in the image there show links between islands and you can find the reachable parts of the game the problem with that is that spawn volumes are sometimes really really big 100 meters or more depending on the sort of setup you have and by the time you get that big there's a really good chance you're going to capture some disconnected Island and accidentally market as being connected and something to keep and so we used less in some ways well a more crude approach rather than looking where enemies or when where bots can come from just saying what's been marked up as being connected and keep those things and that's a simple trick a simple tool for marking this up it's something that's easy to explain and to understand it's something that's easy to reason about and it meant that across all of Sunset City we had a big improvement in quality with a small amount of extra work we were able to get rid of about 25% of the triangles in disconnected mesh reducing it from about 400,000 to about 300,000 so if you're using an automated tool like recast I would highly encourage you to spend the time looking at what you know about your game and what you can apply to that to improve the quality of it save time for your designers so to give better information for your AAA programmers to reason about and overall end up with better games thank you so my trick is a generic way to contain all types of data hopefully everybody's familiar with blackboards as we use them in games I'm not thinking traditional blackboard architectures here but but the kinds of blackboards we have in games if you're not there's a fantastic master class on a game dev comm with Tommy on Isla and Alex on Pandora go look it up and by the way small trick I keep two blackboards what really lots of blackboards right so I have the global blackboard that all the entities can look at to share information but then each entity has its own blackboard where they can keep entity specific information like the list of all the other entities that they can see for instance but that's not really what I wanted to dig into today why is that not advancing there we go all of my blackboards and also my entities so I started out with blackboards that were sort of messy right I just had lots of hand selected values that were written on there and over time I wanted to be able to put things on them much more easily so I came up with this idea of a generic datastore which is really just a hash table that stores key value pairs my blackboards inherit from it my entities also inherit from it now I have the standard way to store data things that want to look up data or want to store data don't have to care where they're supposed to store it up so in the configuration I can say go look up the value name such-and-such and look for it on the entity that you're going to shoot at right see if that entity is an enemy for instance or whatever other value you need to look for the keys are just strings so I've gone a different route from Steve instead of using a news I hash all of my strings and then my string compares are just integer compares so that's another simplest trick to figure out the value can be anything and this is the real power power of it right I can store in so I can store billions I can store floats I can store pointers to objects I can store collections of objects whatever needs to get stored and shared and passed around I can store it the trick is that I need to make a custom data element all of my data elements need to inherit from the same base class so that I can put them in my container together because C++ is strongly typed so I just have a generic base class it has two functions on it I get datatype lets me check that the data type is what I think it is just runtime type checking and get is bool I didn't have this at first but it turns out that it's really useful to be able to check a boolean value for anything because often I don't you know I have some consideration that doesn't want to look up an object or know what type of object it is it just wants to treat it as a boolean and know if it exists or not so if I can get a boolean for anything that turns out to be really powerful inheriting from that is a templated based class that just takes the type of object as a template argument and has the functions to get the data value it also has some functions that you can implement to set the data value some things may be implemented so that you can't set them some so that you can some can only be set when you construct it so there's a can set function that by default returns false and a set data value that by assault by default asserts inheriting from that is the simple data element which just implements all of those functions so it stores the value when you set it it just over writes the value that it stores and then I can store integers for instance by just inheriting from that and setting the template argument to integer and implementing the get data type function so that I know what type of data element it is object pointers are a little more complicated but really not much when I do object put pointers often I want to be able to have both storage for pointers that owns the object and will delete it when it gets taken out of the store and also storage for things that are known because both of those turn out to be useful so I'll have a base class that specifies the data type and then I'll have two different subclasses for onda nomes and that's really kind of all there is to it hi everyone my name is rice gram yes thank you so I'm gonna start by introducing the master of ceremonies seize her let's see if the sound is playing sounds not playing the ideas not even playing no audio is playing imagine amazing audio happening we just creamy every day I'm not gonna sing there you go look this is nice it's moving that's all it's doing postman my wonderful see a helper here who's going to Shepherd him along he may do sad and terrible things he's a very very simple little robot that I decided to build and maybe about a week can you hold them up and then set him down maybe going off in that direction it's very very simple here we'll send that so at the end of yeah I just let him go somewhere somewhere not too complicated so at the end of The Sims 4 I was like well what do I want to do I don't really want to work on another side project that's like another game I want to do something completely different so I decided I was going to try my hand at a little bit of robotics this is incredibly simple I use the Arduino Uno it has a 16 megahertz clock and 2k of SRAM for those who don't know what it is and this is what he looks like if you were to see him nice and up-close that's going to be a sad corner for him over there what he has is to continuous motion servos that's what lets him move he has two infrared LEDs along with two sensors if you completely explodes you can turn them off by pressing the little back thing what happens is the IR sensors will or the IR LEDs will send out infrared light signals what that does is it reflects off of something and gets hit by these sensors right here if he detects it there's something there he'll turn now things love to soak infrared light so we have whisker switches as well the whisker switches when he hits something he'll hit it he'll back up you might be doing that right now he'll stop back up go around because he's hit something particularly bad a slight spoiler alert in order to get him to even work in this room I had to put tape over these IR sensors because there's a hell of a lot of infrared signal happening in this room so he just freaked out he just was afraid and alone this is an incredibly simple robot oh I have to D to have three debug LEDs he has a blue light on right now which is his move forward State this is this is your debugger if you've ever done anything in robotics you're lucky that you have that so I want to show you just the software side which is it's 1,100 lines of basic C++ style code he has a simple state machine this is an incredibly reveal robot from anyone who's ever done anything with robotics this is like stupidly simple I did this in maybe a week including all the hardware so that's really all that he is but why am I talking about this because for me it helped me learn what it's like to program in what I call the real world the actual world that we live in today which is a very much harder problem to solve there are in fact entire tracts of academia and in in the real world about how to solve some of the particularly hard problems of navigating a room such as this he's probably exploded there's a switch that you can pull back and he's completely dead so for example this is his view this is all I get I basically get what is effectively the same as two rate races and two collision detectors those are on pins 13 12 4 and 3 which are either 5 volts or 0 volts which means I have a 4-bit world representation at this point very very simple the key here is that there's no easy way to call get position we are all very spoiled by get position get orientation any of those things and that is one thing that creating this little robot taught me where am i I have no idea I could very well be here and there'd be no way that I would be able to detect that that's there except that oh my left pin is up is 5 volts so that's a like I said there's hole tracks to kind of do this so his performance in a beautiful specially designed room which is my kitchen with all the doors closed is 100% he happily navigates because there's no errant infrared signals such as there are in this room and all of the obstacles happily reflect infrared light so he navigates perfectly he never really hits collision his whiskers at all in the real world he has maybe a one to two minute success rate is he still going back there that surprises me he usually reaches some point of massive sadness by now because he's very very simple this is a here let me show you some of his mortal enemies here's one these are my girlfriend's shoes they're low enough that his sensors can't detect it so he'll happily go over and then hold and he'll flip over and then life is just terrible for him when he flips over there are many ways to solve this of course here's the route here's his real like the worst one this is my dining room table that beam there is high enough that his sensors don't see it but low enough that all that if you guys saw the picture all those electronics that are sitting there on that breadboard gets scraped off ha ha ha so that's not fun I've every time he's gone under there twice now and the first time I lost one of the infrared LEDs because it shorted in blue the LED the other time I lost his sensor so fun times so where am I going with this well let's take a let's take a counter example here which is a Sims 4 on the Sims 4 I have a sim sitting here at a computer and there's a guitar to her right if I want to run an interaction that causes her to get up and use that guitar is actually really trivial to do that because I know what my position is now and I know how to walk all the way over to the guitar where it is I know the exact offset of where I need to stand to play the animation to get up and start playing the guitar I have my robot has no clue where he is he's wandering through the grace of this wonderful CA who is watching him go that's really the only reason that he knows where he's going someone's going to hit the little whisker probably it looks like you're about to test him Oh God this is going to go well yep there he goes see and he does that he keeps going he's going to freak out oh no he's still going so that's really it what am I to our characters live in this perfect digital world and so what I'm saying is that you should go out and try and build an autonomous robot and try and see what it's like to solve this type of problem which I have quite unsuccessfully solved in my little 1 week of playing around experience programming the real world and except for designing the room you don't really get to cheat like we get to do in games thank hi warframe is synonymous with space ninjas and nothing is more ninja than acrobatic parkour moves and wall running bull running was added for the players quite early on in the closed meter of warframe and it changed the game up dramatically players can will run on pretty much any near surface any near vertical service in the game and we support this through dynamic run time sweeps and calculations to keep them glued to the walls defying gravity however this is still one of the more challenging maneuvers for new players to pull off last year we added spectres to the game spectres are NPC controlled bots that are kind of duplicates of players warframes they have the same loadout and weapons and equipment and abilities that the players have initially they were limited to just a single type of mission in the game where they would be the opposition for the players but soon enough this feature evolved and now players can actually craft their own spectres to take with them as allies into any mission in the game so these spectres have to be able to do everything the players can do and they have to be able to keep up with the player as the player moves through the environment and that includes running on walls but how would you get an NPC to run on a wall well the animation and physics side is already taken care of for our players so the big challenge comes with identifying where the NPC's can wall run and this means having either specific bridge actions placed in the level by level 2 by level designers to identify where these actions can be performed or having some kind of navigation on the walls and these either need to be placed manually or you have to come up with some smart algorithm to automatically detect these areas for you our levels in warframe are all procedurally generated and we combine level chunks together at runtime to create the runtime level and we have a huge amount of level chunks already released for our game we've got hundreds of these things and they're all just got their own special characteristics so it would take ages for level designers to have to go through and manually mark up all these level blocks and that would also be very error-prone our level geometry is also quite complex with the collision mesh and coming up with a foolproof algorithm would have taken much more time than we really had to spend on it however we do have thousands of active players playing the game every day and they are managing to wall run just fine well most of them are anyway so what if we could leverage our player base to teach our AI where it can wall run so that's exactly what we do every time the player performs a wall run we drop breadcrumbs from where he jumps off the ground where he connects with the wall where he jumped off the wall and where he landed back on the ground again since players can jump all over the place we need to validate that we get a good sequence when you know that a jump off the ground connect with the wall move along the wall jump off the wall land back on the ground again we need to then validate that our kind of initial jump point and our final landing point are both on navmesh and not in some weird part of the level once we've got the valid sequence we can dynamically create an average for the npcs to follow that map's that onto that wall run action so we only need to do just some clustering and filtering to ensure that we don't add many multiple variants of the same link with just very slightly different offsets and now the players can follow the the NPC's can follow the player currently we keep the C's bridges around for the remainder of the current session and we have a pool around the players so that the ones closer to the players we keep alive longer and the ones that are further away we discard so that we don't waste our memory too much but since we're an online game this feature will improve and evolve over time and we can then upload these these links to a database and then we can either manually patch our maps afterwards and release them in the next update or we could just pull those links down dynamically from the database at runtime and make these links persistent across multiple sessions so in the future we could potentially have players teaching NPCs where to wall run so that NPCs can teach new players way to ball run and how awesome is that concept

Channel: GDC

Views: 268,005

Keywords: gdc, talk, panel, game, games, gaming, development, hd, design

Id: iVBCBcEANBc

Length: 25min 19sec (1519 seconds)

Published: Mon Nov 07 2016

Reddit Comments

[u/supertraveler]

Very interesting stuff. The biggest disclaimer here though is that this is pre-parkour 2.0.

I wonder if this system is still being used

[u/7grims]

That is why loot/ayatan stars and enemies spawn behind walls, cause we arent teaching them.

[u/PitmanE957]

I like the implication this has. Maybe we could by just playing the game teach the AI how to become more effective against us.

[u/triforce-of-power]

If he can pull this off then why are so many of the game's enemies still so brain-dead?

[u/FTC_Publik]

I was at that talk :) I love DE's talks, though I'm not sure if I can make time for GDC next year.

[u/moosecatlol]

It would have been possible had it simply been just wall running, but expecting an AI to be able to bullet jump and and bullet jump cancel. If they could ever even come remote close recognizing and utilizing half as many paths as a player could take, the stalker fight itself would be insane.

If Warframe had one good boss fight, I'd be so happy.

[u/RzdAkira]

This is a cool find. Using multiple inputs from thousands of players to serve as learning tools for the bot. Allowing them to learn pattern and making their own judgements on how the bots can position themselves and traverse the terrains

[u/severed13]

Hundred of varied tiles!

HUNDRED

TILES

Literally unplayable.

[u/Rock3tPunch]

NPC should learn from players how to T-bag, so NPCs can teach new players how.