Over the past few weeks, I’ve made significant progress on the navigation mesh system for my map editing mode, a core feature for creating interactive game levels. This post dives into why I chose navigation meshes, the details of what I’ve built, the challenges I’ve faced, and the next steps I’m tackling. For those unfamiliar, the map editing mode in my game engine allows users to design game environments, including ground tiles, entity placement, and navigation meshes. My current focus is on navigation meshes, which are critical for enabling entities to move intelligently within the environment. Let’s explore the motivation behind this choice and my recent progress.

Why Navigation Meshes?

The decision to use navigation meshes was inspired by games like DOTA 2, where players use right-click to move, freeing their left hand to cast spells or perform other actions. My game heavily emphasizes spell-casting, requiring players to use their left hand to select and combine elements into spells. To mirror this fluid interaction, I needed a pathfinding system that allows natural, intuitive movement with minimal input. Initially, I used grid-based pathfinding, but it resulted in unnatural entity movement and clunky player navigation. Navigation meshes solve this by enabling smooth, organic paths. Additionally, they simplify collision detection: entities can only move within the mesh’s polygons, and anything outside is considered a collision. For interactions like spells hitting monsters, I use simple collision boxes, keeping the system efficient and straightforward.

What Are Navigation Meshes?

A navigation mesh, or navmesh, is a set of polygons that defines the walkable areas in a game environment. These polygons are convex, meaning any two points within a polygon (including its edges) can be connected by a straight line without leaving the polygon. This property simplifies pathfinding, making it faster and more efficient. The process of creating and using a navmesh involves several key steps:

  1. Define or generate polygons representing walkable spaces.
  2. Partition these polygons into convex shapes for optimal pathfinding.
  3. Build a connectivity graph to identify which polygons are adjacent.
  4. Find a path from a start point (A) to an end point (B) using the A* algorithm or a similar method.
  5. Apply the funnel algorithm to straighten the path for smoother movement.

The result is an array of points that an entity can follow to reach its destination.

Current Progress

Ground Tile Design

The map editing mode already supports designing ground tiles. Users can select and edit tile textures and specify their rendering level (height) to ensure the correct rendering order. This feature is complete and works seamlessly.

Navigation meshes and entity placement are interdependent. Entities rely on the navmesh to simulate movement, while static entities’ collision polygons help define the walkable space by marking non-walkable areas. To address this, I prioritized building the navigation mesh system.

I’ve implemented a feature to draw and save polygons, which serve as the foundation for the navmesh. The next step was partitioning these polygons into convex shapes. The simplest approach is triangulation, where polygons are split into triangles. However, this creates many small polygons, resulting in a large connectivity graph that slows down pathfinding. To optimize performance, I merge triangles into larger convex shapes where possible, reducing the number of polygons while maintaining convexity.

Building the Connectivity Graph

For the connectivity graph, I took a straightforward approach: I check all edges of each polygon and mark polygons as neighbors if they share an edge. This graph is used by the A* algorithm to find paths between polygons.

Implementing A* Pathfinding

I previously wrote an A* algorithm for a demo where nodes were the center points of tiles. For the navmesh, I adapted this algorithm to use polygons as nodes. To calculate the heuristic (an estimate of the distance to the goal), I compute the center point of each polygon during graph creation and store it within the node. The heuristic is then the distance between polygon centers. With a few tweaks, the A* algorithm now works reliably with the navmesh.

Funnel Algorithm

I integrated a funnel algorithm (based on a C implementation) to straighten paths generated by A*. While it works, it requires simplification to make it more user-friendly. I’ll refine this in the coming weeks.

Point-in-Polygon Testing

A critical feature I need to implement is determining whether a given point lies within a polygon and identifying which polygon it belongs to. This is essential for mapping start and end points to the correct polygons for pathfinding. I’m considering two approaches:

  1. Ray Casting: Cast a ray (typically along the positive x-axis) from the point and count the number of edge intersections. If the number is odd, the point is inside; if even, it’s outside. I’ll need to handle edge cases like vertex intersections. The time complexity is O(n), where n is the number of polygon edges.

  2. Triangulation-Based Testing: Triangulate the convex polygon (a fast process since it’s already convex) and perform an “in-triangle” test for each triangle using basic math operations. This approach also has O(n) complexity but may involve fewer operations depending on the polygon’s structure.

I haven’t decided which method to use yet. My next step is to implement and benchmark both approaches to determine which is faster and more reliable.

Next Steps

My immediate focus is to finalize the point-in-polygon testing by comparing the ray-casting and triangulation-based methods. Once that’s resolved, I’ll integrate the navigation mesh system into the simulation to test entity movement. After that, I plan to polish the funnel algorithm and create a detailed post with visual explanations and a demo showcasing each step of the process.