Introducing Polaris-Nav

What would happen if zombies stopped running around in circles chasing players and instead surrounded them, intentionally trapped them, or even used a tank to break down the walls to reach them? Suddenly, the game becomes much more challenging like the difficulty of competing against other players. When we integrate game AI, we make the world more immersive, real, and “alive.”

The Foundation of AI

Designing Immersive Worlds

As a 14-year old developer, I occasionally dreamed of creating worlds with my friends. The most important characteristic of these worlds was that they were “alive”. For example, when I engage in PvP near guards, they should attempt to stop us, there would be consequences, and they would remember us when we came back later. The civilizations would have a functioning trade and resource collection, like RTS games. As a naive developer, I began crafting the AI to make this happen.

The Stumbling Block

While I was busy implementing what I would now term an expert system, I noticed that many rules depended on having a reliable method to search the game world, and navigate. Obviously, this challenge isn’t unique to expert systems though. Any form of game AI either needs to have information about their environment provided to them or given a method to search the environment. Likewise, game agents are limited to what actions they can perform in their immediate vicinity. Indeed, as general principles, all AI and robotics are limited by the places they can safely reach and the environment they can sense.

As general principles, all AI and robotics are limited by the places they can safely reach and the environment they can sense.

Solutions

Rolling your Own

When I was 14 years old I was most familiar with the Roblox game engine, which hadn’t added pathfinding yet. So, as my first experience with data structures and algorithms I researched and implemented the A* search algorithm. I recorded my creation and later posted it on YouTube.

It wasn’t perfect and was too slow due to the performance of being written in a scripting language, Lua, and performing an unoptimized AABB search for each grid cell. It would search roughly 50 cells the size of a character per second, while bringing the game loop to a grinding halt.

Roblox eventually saw the need and published their own pathfinding service. When I worked there a few years later, I was told this took lots of development resources and complicated their code base. So just before I arrived they decided to swap out their solution and use the Recast and Detour library under the hood.

Nowadays, most 3D game engines do not create their own pathfinder. The reasons are simple:

• Good, general pathfinding systems are large and complicated
• Creating these systems take huge amounts of development time that could be spent elsewhere
• Pathfinders can be resource-intensive, requiring careful design
• A good-enough solution already exists

Although for 2D games, engines like GameMaker usually provide a generic and efficient A* implementation.

Many authors like Amit Patel frequently publish A* tutorials for those looking to create their own simple solution.

Recast & Detour

Roblox, Unity, and Unreal Engine all use Recast and Detour under the hood. This library was written over roughly 5 years by Mikko Mononen, and published under the zlib license. Later, other developers stepped in to help push development forward, but the project hasn’t changed much over the years despite powering all the latest and greatest game engines.

[Recast & Detour] hasn’t changed much over the years despite powering all the latest and greatest game engines.

Recast works by generating navigation meshes instead of running on a grid. This enables map designers to more accurately describe walkable regions, and for Detour, the pathfinder, to generate more realistic paths. In addition, pathfinders run faster on navigation meshes. However, these navigation meshes take a long time to create by hand so Recast automatically generates them.

However, the navigation mesh generated by Recast is inaccurate due to the voxelization process map geometry undergoes before generation. This process was introduced to deliberately and automatically simplify the mesh due to limited computer resources available at the time. The result is that many AIs are unable to find paths obvious to players and sometimes find paths where non exist. The same issues exist for pathfinders than run on grids (unless the game world and obstacles are defined as a grid too).

These inaccuracies, along with a lack of higher-order pathing intelligence for tasks like chasing and trapping a target or fleeing from a target, break immersion. Ark: Survival Evolved would be a much more difficult and immersive game if the dinosaurs didn’t get stuck on the terrain all the time.

Polaris-Nav

In addition to navigation mesh accuracy, Roblox’s integration of Recast and Detour does allow game developers to access generation parameters. The result is a lot of developers on the platform are forced to attempt to tweak their maps to accommodate, and even roll their own solutions. Thus, I continued to develop pathfinders for over a decade. When the opportunity recently presented itself, I decided to take the time to start a business building a pathfinding solution to overcome the limitations of Recast & Detour and reimagine what we expect from our pathfinders.

I decided to take the time to start a business building a pathfinding solution to overcome the limitations of Recast & Detour and reimagine what we expect from our pathfinders.

Features

Exact Navigation Meshes

The main feature of Polaris-Nav is that is generates exact navigation meshes directly from geometry, without a voxelization process. Designers can choose what objects are processed, and pathfinding on the resulting mesh is guaranteed to return a valid path if one exists and never return an invalid path. It nicely handles dirty mesh data, such as non-coplanar, non-convex, or overlapping surfaces. It detects when low surfaces, like a fallen tree, prevent walking on surfaces below. The result is navigation meshes that work in nearly every case, resulting in higher quality paths and a more immersive experience for games.

This was surprisingly difficulty to do, and catching every edge case took time. While it doesn’t appear so on the tip, this problem is an iceberg that I’ll write about later. Handling degraded meshes and floating-point errors have sunk many-a-developer.

Tozour’s algorithm, and Sanchez’s algorithm from 2021 use exact navigation meshes from triangle geometry, but Polaris-Nav is the only solution that uses quads to my knowledge. Below is a comparison between Sanchez’s algorithm and Recast.

Physics-based Jump Detection

Recast, surprisingly, does not automatically generate jump connections.

Recast, surprisingly, does not automatically generate jump connections. Roblox and Unity wrote their own jump detection algorithms, however they only detect jumps in the four cardinal directions. And even so, the searched trajectories are not parabolic. I put great effort into Polaris-Nav to craft formulas for search areas which will detect objects in a continuous parabola from the edges and corners of surfaces. The result is that every possible jump location is found, and that jump connections are not placed where they should not be. The result is traversing complicated terrain and long-distance jumps are calculated precisely. Below is a picture of Polaris-Nav’s automatic jump detection from August of 2021.

Chasing, Trapping, Fleeing

Trapping a target goes beyond what any current pathfinder is designed to do. It also requires intimate knowledge of traversable areas. The search to trap a target (move an avoiding target into a state with less degrees of freedom) is also non-convex, having local minima. Fortunately the value of a global minima is known: zero degrees of freedom. Likewise, fleeing one or multiple targets requires avoiding positions which would lead to a loss of degrees of freedom in the future. These problems require a chess-like minimax search or reinforcement learning.

Adding these and similar behaviors into a game greatly increases realism. A pack of zombies that know how to trap you is a much more impressive challenge.

A pack of zombies that know how to trap you is a much more impressive challenge.

Map Searching

Finally, again going beyond most current pathfinding solutions, map-searching is critical to AI. Kythera AI recently built upon the Recast library to add limited support for this functionality (mainly finding cover). AIs need to know what is around them, what is reachable, and what is not. Using this information, they can perform higher-order planning. Polaris-Nav will provide capabilities to search and make decisions that are easily integrable in any algorithm. By providing customizable callbacks into the search function, custom behavior like trapping or fleeing can be designed without getting into the weeds of map storage and nav mesh features.

Cloud Hosting

Game servers generally try to avoid doing heavy processing because it easily bogs down time-critical networking operations. Polaris-Nav gives developers the option to run pathfinding in the cloud. The in-engine library handles all the required networking, making the process smooth and the transition easy.

RRT*

Finally, have you ever seen cars move strangely in games? That’s because the A* and Dijkstra’s algorithms that all game pathfinders use don’t handle constraints on movement. In fact, they don’t take any agent constraints or state into account besides position, width, height, and possibly seen/unseen areas. A rectangular vehicle that can only move forward and backward and uses Ackermann steering is not possible with A*, but game developers sometimes fake it behind the scenes or roll their own solution. This leads to sometimes bizarre movements. Likewise, all vehicles, side stepping, sliding, mid-air maneuvers, swinging, bouncing, and much more are also not possible with A*. Instead, a more powerful algorithm like RRT* is required. Usually reserved for robotics applications, RRT* has the capability to search a high dimensional state-space created by all the configurations an agent can take. However, searching these larger state spaces and checking which states are valid (i.e., enforcing constraints; e.g., not walking through walls) requires more time than A*. Thus, the RRT* algorithm is only possible for use in games when hosted on another server.

Conclusion

All of these features are not present in existing pathfinding solutions. Polaris-Nav is a pathfinding system unlike any developed before. It goes beyond just finding a way from point A to point B and focuses on becoming the foundation for AI to interact with their world. The purpose of Polaris-Nav is to empower AI by providing them with a solid foundation to build upon. This mission goes beyond games and one day will extend into robotics and perhaps into vehicle navigation.

The purpose of Polaris-Nav is to empower AI by providing them with a solid foundation to build upon.

If you want to keep up on the progress of Polaris-Nav you can subscribe to my RSS feed or join the community on Discord.