NavPower from Babelflux is a path finding middleware used for dynamic obstacle avoidance and streaming in video games. It’s often a overlooked aspect in video games development scene but it’s one of the most important elements while building the game nonetheless. Just imagine how you will react when NPCs in role playing or open world games have no intelligence in their independent path finding abilities. They will just bump into each other!
GamingBolt recently got in touch with David Miles who is the company’s CTO and we were able to ask a whole lot of questions regarding the new consoles and how they are taking path finding to the next level.
Rashid Sayed: To begin with, tell us about yourself and Navpower?
David Miles: I actually got into pathfinding originally from robotics which is what I’d been working on in school. After graduating, I worked at Crystal Dynamics for 8 years developing pathfinding, physics, etc. on Tomb Raider and other games.
Then in 2005 I founded NavPower, which happened to be great timing because it was just as pathfinding middleware started to get big so we were totally in the market at the right time. These days NavPower is one of the most widely used pathfinding middleware packages for AAA titles with most of the 10 top publishers and quite a few independent developers licensing NavPower.
Rashid Sayed: With the advent of new consoles, the PS4 and Xbox One, what kind of upgrades have you implemented in the middleware?
David Miles: The biggest advantage of the new consoles for a middleware package like NavPower is that the new machines are much faster running algorithms which inherently have a lot of branching and nonlinear memory traversal. Most of our systems run at least 3 times faster on the new machines and some of them are 10 times faster.
So from very early on in our PS4 and Xbox one development we realized that a range of techniques which had previously been too expensive were now going to be pretty reasonable. One of these is automatic jump connection generation which analyzes the world geometry and automatically adds jump connections so enemies can automatically jump down off of cliffs, pull-up on low ledges, etc.
"Even though the memory bandwidth on both the PS4 and the Xbox One is fabulous, the critical thing for us is that both machines feature very modern processor designs which include features such as out of order execution. "
Rashid Sayed: Navpower is essentially a CPU based process. Granted that the PS4 and Xbox One have 8 cores but does their slower clock speed pose any challenges while automatically generating navmesh for all of the walkable surfaces in a level?
David Miles: Actually the performance on the new machines has been quite good. There’s also a lot more memory available, which is great. The NavPower runtime typically uses just a few megabytes, but once you start building NavGraphs at runtime, that increases the memory requirements significantly. Even more than CPU, this is why NavGraphs are traditionally built off-line.
Rashid Sayed: Tell us about NavGraph and how does it work when the path is dynamic i.e. affected by any sorts of physics or destruction.
David Miles: Many games use NavPower in environments that change due to destruction, or in games like The Sims Medieval, due to player creation. If you have simple changes like some rubble which falls down and blocks off an area then it’s easy to use dynamic obstacles to block off or penalize that section of the NavGraph.
If you have a bigger change where a section of the world is completely transformed into a new configuration then you can load in a new NavGraph to replace that section of the world. Of course if the geometry for the new section of the world is known ahead of time then you can build the NavGraph for that geometry ahead of time, but in some cases the new geometry is unpredictable because it’s based on the gameplay or the physics system, in which case you can build a new section of the NavGraph at runtime.
Rashid Sayed: How does the middleware take advantage of specific features of the new consoles? A. The unified GDDR5 Memory of the PS4 B. The extremely fast memory eSRAM of the Xbox One which has a bandwidth of 204 Gb/s
David Miles: Even though the memory bandwidth on both the PS4 and the Xbox One is fabulous, the critical thing for us is that both machines feature very modern processor designs which include features such as out of order execution. That’s critical for anyone writing path-finding or AI systems, because it’s rare to be able to execute any significant portion of code without having to make a decision based on the data you’re traversing, and conditionally go off to execute a different piece of code. So having the fastest memory in the world isn’t useful if the processor stalls whenever you have to branch to another part of the code.
Rashid Sayed: Are there any plans to integrate the middleware for mobile/tablet gaming?
David Miles: That’s a good question. Although NavPower isn’t well known as a mobile pathfinding solution, it’s actually been used on a number of mobile games and we’ve worked with AAA developers to optimize key portions of the code for mobile platforms. So yes, it’s already available and works quite well.
"Although the new console machines have a lot of memory and CPU horsepower compared to previous generations of consoles, most of those resources are continuously in use rendering and simulating the world. Being able to leverage cloud resources would let you temporarily run processes which might consume a lot more memory or a lot more CPU."
Rashid Sayed: Microsoft will be launching DirectX 12 next year for PC and Xbox One in 2015. According to reports, the new API will reduce CPU overhead by 50% and will allow developers to code close to the metal. What kind of benefits do you think this could potentially provide to Navpower?
David Miles: Obviously this is great for us because it frees up a lot more CPU resources that can be used for a variety of things including AI. Most clients only allocate a few percent of the total CPU available to the game for AI processing, including things such as dynamic obstacles, pathfinding, and character steering.
Rashid Sayed: A month ago, Microsoft showcased their cloud technology [link here]. Do you think this could probably be used for improving the AI in your pathfinding package?
David Miles: That’s definitely something that we’ve considered. Although the new console machines have a lot of memory and CPU horsepower compared to previous generations of consoles, most of those resources are continuously in use rendering and simulating the world. Being able to leverage cloud resources would let you temporarily run processes which might consume a lot more memory or a lot more CPU.
For example, we already have clients who are using the NavPower build process on PC games, both locally on the client machine and on MMO server machines to dynamically rebuild sections of the world. Of course you can do that directly on consoles and we’ve had people do that in more limited situations but by leveraging the resources available on the cloud you could do that for a much larger section of the world.
Rashid Sayed: What kind of parameters does the middleware provide for multi-platform games development? For example cross gen games which are coming out on PS4, PS4, Xbox 360 and Xbox One, how easily does the middleware scale?
David Miles: As far as parameters go, here’s an interesting example of one that we have. Basically if a character gets pushed too far away from its original path, for example by large crowd of characters passing by in the other direction, you may want it to start doing new pathfinding queries to see if instead of trying to get back on its original path that it should now detour and take a different route. It’s the type of thing your GPS does in a car as soon as you leave the original path. But of course making those additional queries would consume additional CPU so we make it optional and it is controlled by a parameter called m_allowDetour.
There are a lot of other options to control quality/performance trade-offs, but actually most of the work that we’ve done on scaling is just ensuring that all of our algorithms are highly scalable. That’s critical because we need to support machines ranging from the PlayStation Vita to the PS4 and Xbox One. But actually the biggest driving factor on the upper end was supporting MMO’s since in that case NavPower is typically running on the server and you can have 1000 times more navmesh data loaded. So the bottom line is that NavPower needs to operate efficiently whether you’ve got just a few enemies in a small dungeon or thousands of characters in a large open world.
Rashid Sayed: NavPower FlightPak adds 3D volumetric path which can be used for a character which is flying or swimming. Given there is some sort of GPU involvement with regards to rendering the accurate the physics, how does the middleware behaves dynamically according to the direction of wind while flying or the waves of the sea while swimming?
David Miles: We actually have that type of functionality for the surface walking creatures, but not for the flying creatures. Now that you mention it, I’m surprised that we haven’t had a request for that. Most likely, that’s because NavPower is used for creatures which are critical to the game play instead of ambient creatures.
So you would use the NavPower flightpak for something like a security drone or a shark which is chasing the player, and you wouldn’t want a sudden gust of wind or a sudden current knocking the AI character out of the way as it was trying to do something like an attack run.
"I think the new generation of gaming consoles will define the industry for years. It’s partly that the console makers, by providing a well defined platform, allow the middleware teams and the game teams to do a lot of optimization knowing exactly what hardware they’re going to be running on."
Rashid Sayed: How flexible is the middleware in integrating with licenses engines like Unreal Engine 4 compared to a proprietary one?
David Miles: Excellent question. NavPower has been used on a large number of engines both licensed and proprietary, including Unreal. In fact, specifically for UE4, we have sample code under development which demonstrates the integration fundamentals. At the most basic level, NavPower integrates in the same way that Recast (the UE4 default pathfinder) does where you just feed the collision primitives to the NavGraph build process and then take the binary image that that produces and feed it to the runtime planner module. So it’s pretty straightforward.
Rashid Sayed: In the next 3-5 years, where do you see the technology of path finding AI evolving to?
David Miles: I think the goal that everyone has is for characters to skillfully navigate through whatever kind of worlds that the designers and artists envision, whether it’s running, jumping, wall climbing, or flying, without requiring a lot of additional work from the design team. And we are a huge way from where we were 10 years ago with designers hand placing navigation nodes and characters getting stuck all over the place.
But there is still a surprising amount of capability that is needed and I think with the new generation of machines the CPU will be available and new technologies are being developed we will get us a lot further towards that goal. Some specific things are dealing with dynamically changing worlds, crowded situations, and even just better techniques for coordinating animation with motion planning.
Rashid Sayed: Tell us about some of the projects you are working on and the challenges you are facing. If this is something you can’t comment on, will you be able to let us know what is the number one demand from developers these days regarding the middleware?
David Miles: Well, I can definitely tell you about the most requested feature over the past couple years, which was the automatic jump/climb link generation. This was requested by nine different teams and basically the design folks want to be able to have characters that can automatically jump down from ledges or jump across chasms and to be able to control that so that nimble characters can jump across large gaps or climb up pretty tall ledges, but larger characters would have to go around.
And all of that needs to be automatic because the worlds are often really huge or the design team wants to be able to iterate quickly and not have to worry about manually marking up where these jump connections should be. So we are just now putting the finishing touches on it for NavPower 5.0 and the response from teams beta testing it has been really positive.
Rashid Sayed: With more and more powerful gaming CPU hitting the retail market, is it safe to assume that the new consoles will lag when compared to these high end CPUs in terms of middleware performance?
David Miles: Not so much. I think the new generation of gaming consoles will define the industry for years. It’s partly that the console makers, by providing a well defined platform, allow the middleware teams and the game teams to do a lot of optimization knowing exactly what hardware they’re going to be running on.
There’s also the factor, at least for pathfinding middleware and the AI systems that use it, that even if there are some PCs that are higher performance than the new generation of consoles, it’s hard to scale an AI system because it’s so integral to the game play. Therefore, I think the new generation of console machines really is going to provide the standard by which games are developed for many years.
Rashid Sayed: As a closing note, is there anything else you want to tell us about the middleware that we haven’t asked?
David Miles: Well whenever someone asks me an open-ended question like that I have to tell them first of all that, “NavPower is awesome”, because otherwise I’ll get in trouble with marketing over here. But seriously, you’ve done an excellent job of hitting a lot of the key technology points with all of your questions.
I expect that most of your readers are already playing several games using NavPower and obviously for any developers out there who aren’t using NavPower, they should head over to our website and check it out.