2D Navigation Mesh & Behavior Trees

This project was completed as part of a university course, where our team was given a minimal 2D C# game engine and tasked with extending its functionality and creating a small demo game to showcase the added features. I focused on implementing two core systems related to game AI: a Behaviour Tree framework and a 2D Navigation Mesh for pathfinding.

My goal was to equip the engine with foundational AI tooling that would allow for reusable, modular NPC behaviour and efficient navigation—features typically taken for granted in modern engines like Unity, but absent from the provided framework.

Behaviour Tree System

I implemented an inheritance-based Behaviour Tree system that included standard composite, decorator, and leaf nodes, along with a blackboard for shared data. Compared to my more advanced Unity implementation, this version did not require serialization or editor tooling, making it simpler but still fully functional for expressing complex behaviour.

Since editor tooling was outside the project scope, visual debugging and node creation had to be approached differently. To streamline Behaviour Tree design, I created an import system that reads Behaviour Trees from draw.io flowcharts exported as XML. The engine maps the diagram structure to node classes through name matching, automatically generating the tree. This allowed for visual planning without writing the tree structure by hand, reducing errors and speeding up iterative development.

Navigation Mesh

To enable AI navigation, I implemented a 2D Navigation Mesh system from scratch. Instead of triangle-based tessellation (common in 3D engines but unnecessary for this scope), the environment was subdivided into a grid of squares. Each square was tested against scene colliders to determine if it was walkable.

To reduce the number of nodes and improve performance, the system performs two node optimization passes:

• Square Merging: Adjacent walkable tiles merge into larger squares where possible, significantly reducing node count.

• Edge Merging into rectangles: Neighboring regions with matching edges are further merged into rectangles to remove redundancy and create a more efficient graph.

These steps reduced the navigation mesh to a compact set of quadrilateral polygons suitable for real-time pathfinding, without sacrificing movement fidelity.

Pathfinding

Pathfinding was implemented using A*. The system determines which navigation nodes contain the agent and the destination; if both lie on the same node, a direct path is used. Otherwise, A* finds an efficient path across nodes using a distance-to-target heuristic.

After determining the sequence of nodes, the system generates a set of waypoints by finding optimal transition points between node boundaries, ensuring smooth agent movement. Path recalculation is budgeted per frame to prevent excessive CPU usage, pausing and resuming when needed to stay within performance limits.

Results & Takeaways

These additions significantly expanded the engine's capabilities, enabling the creation of more intelligent and reactive NPCs despite the engine's limited initial feature set. The Behaviour Tree import system provided an effective lightweight alternative to a native editor, and the navigation system allowed multiple agents to move efficiently through the map.

• Engine-Level AI Systems: Building core AI architecture from scratch deepened my understanding of Behaviour Trees and Navigation Meshes beyond engine-provided tools.

• Practical Workarounds: The draw.io import pipeline proved an effective substitute for missing editor tooling.

• Performance Awareness: Designing the navmesh and pathfinding with performance budgets in mind highlighted the importance of scalability in custom engines.

This project strengthened my experience in AI systems for custom engines, data-driven behaviour authoring, and pathfinding implementation—skills, and developing with performance and scalability in mind.

See More

The code can be found in this GitHub Repository.

Please note that the code in this repository is a mere showcase of my implementations. It does not include the actual engine, and thus is not executable.