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 for Starlab's navigable surfaces. Getting around the surface was a start, but enemies also needed to recognize where they could jump.
[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 to let enemies jump between platforms, across gaps, and over obstacles.
Each jump needs to get the enemy to the destination position and orientation. Landing on the other side of a gap gets a bit more complicated when the ground curves around a world.
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 navigation through bodies of water so enemies could swim to their destination.
[Swimmable navmesh with connections to land at each edge.]
Transitioning between swimming and walking posed its own challenge. Getting through the water was only part of the problem. Enemies also needed to get into and out of it naturally so they could keep going.
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!
