How Many AI Agents can JavaScript Handle?

in this project we're tackling pathfinding a star optimization and just getting a crapload of Units onto the screen and moving around all at once I ran across this cool video from brackets who stressed tested the limits of unities pass binding system was able to get around 10,000 agents running simultaneously and I wondered how many could I get going in a single simulation in JavaScript now I have a few things working against me unity is heavily optimized and I'm working in JavaScript but I have a whole bunch of ideas on what to do and I'm granting myself permission to bend the rules a bit so that if things aren't doing things strictly correctly no big deal in general path fighting is pretty neat because it's pretty much at the heart of any game AI you almost certainly need a strong a-star implementation I've never done much game AI worked before so this is all pretty new to me it was really a chance to fiddle around with parts of the code I've never done anything professionally with a while back I already did a basic a-star implementation which walks you through the basics of the algorithm how and why it works and how to implement it today we're taking that a bit further so let's mess around a bit concentrate on a star optimization and see just how many AI units I can have running around on a reasonably complex map sound good like always codes available check the description below for kit do whatever what we're gonna go over today is I'll show you how I got from one little guy wandering around the map to many little guys wandering around the map so let's start first we need a map now I can just model it and blender but then I got to do that every single time I want to try out a bigger or smaller maze so that's no good luckily we happen to have one or at least a way to get one since I already wrote a maze generator using recursive backtracking a little while ago the only problem is that it's 2d no worries let's just import the code and we'll screw around a bit and turn it into a 3d mesh here's where that magic happens on the left you have the original two map drawing code what this did was that it traversed the graph looking at each nodes neighbors and whether or not there were edges between the nodes and then drawing a line to represent a wall in the 3d version you traverse the graph looking at each node neighbors and whether or not there are any edges between the nodes and then you create a rectangle afterwards when this is all done we merge them into one massive static mesh and add some ground underneath now we don't want strictly a maze since that's typically one entrance one the exit type of deal so afterwards we'll go over the maze and make a whole bunch of openings everywhere making it easier to find multiple paths from the top to the bottom is this the most efficient solution ever conceived not really but it works and it's fine so let's just move on so we have a map next we have to make a unit move and luckily again I implemented Boyd's a while back voids is just a term for a loose collection of steering behaviors that you can apply to an individual agent or Boyd I'm gonna repurpose that code but strip out all but one of the behaviors the seek behavior will keep that one and will add a path following behavior which is given a list of nodes representing the path and the Boyd will seek from one node to the next following that path and that'll give us a working path following a a guy see watch and walk along and no matter how complex the past this little guy will find a path through and then navigate the paths were these alright so we're all set up we have some procedurally generated mazes we have an AI agent navigating the maze now let's make this fast first we need to do some ace tower optimization work to improve performance I already covered a basic a-star implementation going over the core of the algorithm and its implementation how and why it works and how the heuristic guides the expansion of nodes that basic implementation works but there's some room for improvement the first thing I did was create a separation between a running instance of an a-star search and appending one so we create this a-star management class that creates proxy clients the job of the a-star client is to serve as a thin client between the manager and AI agents that need a search to be performed what they do is wait for the manager to pass them a running instance of a star and clients can check if their search is pending active or finished and get to build paths all this serves to gate the number of running instances of a star since if we have say 10,000 AI agents running through the scene we don't want to try and run 10,000 instances of a star all at once next I tweak the heuristic normally when you're shown how to do a star it's with the distance to goal function or what's called an admissible heuristic I'm changing this over to use Manhattan distance since this is a grid and Manhattan distance is more correct and also cheaper to perform I've also made a very slight change here and added a multiplier on the heuristic this means that the heuristic we're using is no longer admissible but this has the effect of making a star run in fewer steps the trade-off is that the paths it chooses are no longer guaranteed to be optimal but that's fine for our purpose now that's all enabled looks like I can bump this up to around 4,000 units or so before the frame rate begins to drop here there are 4,000 separate units all doing path bindings through a fairly massive scene and we're comfortably running at 30 fps there are still more a-star optimization ideas and tricks I could try out but at this point will render bound due to the enormous number of meshes so let's fix that what we're going to do now is move our meshes over to use instancing which is just a way of drawing large batches of the same object quickly what it does is reduces the number of draw calls and thus material changes and that stuff that the API and driver need to handle that's reducing the overall CPU usage you can see the second we switched to instancing we can bump up our agent count and it looks like we can now support around 15,000 AI agents or so wandering around through the maze at a comfortable 30fps bumping it up much beyond that tanks the frame rate so we're gonna have to try and fix other things now taking a quick profile using dev tools a few easy things pop out we're spending a lot of time updating the matrix and we're also encouraged some garbage collections from JavaScript most likely due to allocations let's go and fix those managing the world matrix ourselves instead of having we gs2 it and pre allocating some vectors and matrices to work with and suddenly our framerate shoots up even higher here's 60,000 and still at a comfortable 30fps which is pretty good they're all navigating the mesh independently and doing a full a-star search for their path so there's no pre-computation of paths or anything of that sort no funny stuff here and that's where we'll end this this was really just for fun and kind of screwing around maybe you can use some of the ideas in your own projects in the future who knows I'm pretty sure I can get into the hundreds of thousands but that'll require some more work and planning move things into other threads or even push work onto the GPU I've got some ideas and if I decide to act on them I'll make a video about it thanks for watching everyone I hope you learned something remember to hit like and subscribe and also comment and let me know what you thought until next time cheers everyone you

Channel: SimonDev

Views: 11,122

Rating: 4.9792027 out of 5

Keywords: pathfinding, ai pathfinding, stress test, how many ai agents, game development, 3d game development, javascript game development, a* javascript, a* implementation, a* optimization, javascript optimization, a* search algorithm, a star optimization, a star implementation, javascript pathfinding algorithm, boids, javascript boids, path following, pathfinding javascript, javascript tutorial, simondev, maze generator javascript, maze generation javascript, maze generation

Id: kuy17LVDESk

Length: 7min 47sec (467 seconds)

Published: Tue Mar 24 2020

Reddit Comments

[u/123_bou]

Awesome work! This is good news all around as I'm often looking how high we can push webgl applications.

Thank you a lot for this.