NPC Navigation - A* Pathfinding

Navigating creatures around Starlab's complex 2D platformer worlds posed significant design and technical challenges. My initial rough draft for enemies used simple local sensors to move enemies around like an old Roomba naively bumping into stuff, getting stuck on obstacles, and falling into holes it couldn't escape.

I needed a complete solution and decided to tackle integrating a full A* navmesh based pathfinding solution. I found a nicely optimized asset on the Unity store 'A* Pathfinding Project Pro' to manage enemy navigation. However, the out-of-the-box features required extensive customization to meet the game's unique demands.

Check out enemy navigation in action, then read on to learn about what it took to make it work!

Custom NavMesh Generation

I began by developing a custom navmesh generator, specifically tailored to create a point graph representing navigable surfaces. This system scans all surface tiles, creating nodes at each tile corner. Once generated, it analyzes the topology of these nodes, identifying cliff edges crucial to allow enemies to platform their way around worlds.

[Debug moon showing walkable nodes of the point graph. Color coded to indicate floor, ceiling, and walls.]

This works to navigate around the surface of worlds but doesn't handle platforming. For that I introduced custom navigation links called JumpLink. Each JumpLink contains precomputed data about all feasible jumps from cliff edges, ensuring navigation could jump between platforms, across gaps, and over obstacles seamlessly.

When encountering a link in a path, the navigation agent fires off an event and waits for another script to handle the link and return control when finished. For a JumpLink this applies a force and a torque to the agent to launch it through the air so it lands at the destination position and orientation.

Optimizing the NavMesh

Initially, the generated jump links were numerous and redundant.

[All valid jump links.]

This negatively affects performance and readability. To tackle this, I implemented a post-processing reduction step, which removes jumps that were too close together to be useful.

[Reduced set of jump links.]

Swimming and Water Bodies

Soon, I encountered another complication—water. Bodies of water would float enemies away from the walkable surface navmesh. To address this, I developed a second navmesh generator for bodies of water. I generate new triangulated meshes for the interior of each body of water and use it to build a triangulated navmesh. With this and a special path modifier, this provides direct navigation through water.

[Swimmable navmesh with SwimWalkLink's at each edge.]

Transitioning between swimming and walking posed its own challenge. I resolved this by adding SwimWalkLink, a specialized two-way node link allowing fluid movement between land and water states. These special links enable creatures to transition naturally between the two types of navmesh graphs.

Flying Navigation

Flying creatures then needed their own navmesh. I was able to use a provided graph generator for this which generates a new triangulated mesh across a specified area that fits around world and water colliders.

[Flyable navmesh.]

Navigation Agent Composition

With these various navmeshes and special links established, the next step was crafting the enemy navigation logic. I went with a composition strategy, so I can add and replace movement strategies for each type of movement and link.

Next I'm looking forward to putting this system to the test with new Enemy AI behaviors!