Make Smarter NPCs Using New Pathfinding Script Functions

July

28, 2014

by Gemlocker


Archive

Ever notice the majority of ROBLOX games are based around players competing with other players? We believe that’s partly because multiplayer games are fun, and partly because programming AI on ROBLOX has historically been a challenging — and occasionally buggy — experience. So, we’ve released new built-in pathfinding functionality that allows you to create smarter and more dynamic NPCs (non-player characters) that follow much more comprehensive paths, all by using a new set of functions exposed to Lua. I’ve made the video below to illustrate how to implement and utilize these functions in your game.


Watch full screen in HD to see the scripts!

We decided to tackle this feature because it opens up new gameplay experiences and because the scope of pathfinding has long been limited — NPCs could be programmed to seek and destroy, sure, but they were often tripped up by minor 3D objects, as well as changes to the environment. Scripting pathfinding around this can be laborious because many ROBLOX environments are dynamic — they are in a constant state of alteration, meaning it’s impossible to predict the exact state of an environment in any given game instance. The new pathfinding functions allow you to not only make smarter NPCs, but have them remain smart in levels with complex geometry.

To put it simply, ROBLOX is doing the heavy lifting for you. An NPC can request the most efficient path to reach its target, and leverage protocols for jumping over and going around obstacles of any size or shape to get there quickly. Developers who design games based around AI aren’t confined to making flat-plane environments. This dynamic system requires no pre-computations — it uses the same technology as both our voxelization system and our dynamic lighting system. As many of you know, lighting represents world voxels of fixed size (4 x 4 x 4 studs), and determines the amount of light that each point of a voxel receives dynamically. This system lent itself greatly to our pathfinding scripts, which also approximate all potential points of movement in any given 3D scene.

To picture how this works, imagine a 3D ROBLOX world simplified to cubes of the exact same size — like you’re looking at a grid of checkered squares. This system asks: what’s the least amount of cubes I need to cross to get to my target? This may sound simple, but imagine making that approximation, say, 100 times, in a hundred different starting points in 3D space (most games have more than one enemy, right?). Also keep in mind that paths can be incredibly complex — you may need to fall first, then round a corner, open a door, then go through a maze of corridors to arrive at your destination. To top it off, paths can change dynamically based on changes to the environment, which can happen at any point in time. This becomes a dynamic math problem that would be impossible to solve. We’re hoping these scripts will solve it for you.

PathfindingEverywhere

Since the release late last week, we’ve already seen some stellar uses from our community of scripters. 1waffle1 created a place that illustrates the example I mentioned earlier perfectly. The map is Crossroads, which is great because there are many different heights throughout the map. Using the pathfinding script, you can watch as over a hundred NPCs navigate the 3D world, jumping to reach higher points and navigating staircases and ramps. We can’t wait to see how other games start to utilize these scripts, and will keep an eye out for smarter NPCs in upcoming games.

For more information on pathfinding and another example, see this entry in the ROBLOX Wiki.