Navigation Meshes Are Back, Now With Levels

This is the last of three posts, after the renderer and the map editor. A year and a half ago I wrote about why I want navigation meshes and how I built them. That code went dormant along with the old map editor. Now they’re back, with height, and with the polygon library I wrote for them and then put on a shelf.

Movement Comes Only From the Mesh

The rule in the new design is simple. A map has a set of polygons, and things move inside them. That’s all that decides where you can walk. Tiles don’t block anything, and I removed the Blocking flag from them. Hits between things, like a spell into an enemy, are plain collision circles and boxes.

The reason is the same as last time. Spellweaver is played with right click to move, so that the other hand is free to combine elements, and that needs smooth paths.

What’s new is height. My first try had the player’s height come from the Z of the map’s layers, with stairs tiles to change it. I built that, played it, and it didn’t work the way I intended, so I dropped it and left height out until I could design it together with the navmesh.

Levels

A map now has levels: 0 is the ground, positive is above it, negative is below it. Height here is a 2D simplification and not real walls. A hero on a cliff can cast at an enemy below, and nothing stops the spell.

Drawing layers belong to a level, and their Z is just their order inside it. A map is drawn level by level from the lowest: the level’s layers, then everything standing on that level sorted by y, then the next level. A hero on level 0 walks under a bridge on level 1. A hero on level 1 is drawn over it, without any special cases.

Each level has its own walkable areas, and there’s one rule for moving between them:

• Where an area on one level shares an edge with an area on another, like stairs or a ramp, you can walk across and your level changes.
• Where they only overlap, like a bridge over a path, nothing connects them and you stay on your level.

Everything else follows from this rule. Stairs aren’t a tile type or a trigger any more. They’re just two areas that touch.

Clipper Comes Home

The areas have to be joined, and holes have to be cut out of them. In 2025 I wrote a triangle subtraction algorithm for this, then started rewriting Clipper2 for it, and then put that rewrite on hold saying that I may come back if needed. It was needed.

Clipper-2D went into the engine’s unity build as engine_clipper.h and engine_clipper.cpp, about 7,000 lines. A script did most of the port: names that clash with the engine’s are renamed, its copies of math helpers are dropped, and all memory comes from an arena. On the way I found that its f64 square root went through a float.

Then I turned on SIMD, which is one of the reasons the rewrite exists in the first place, and found out that it had never been on. Clipper’s switches tested macros that no compiler defines on x64, and they came after the headers that read them. They now follow __AVX__, __AVX2__ and the AVX-512 macros, and they sit at the top. cl builds for AVX2 now too, as clang-cl already did. Two aligned AVX stores into an unaligned stack buffer needed fixing, and the self-test passed.

Remember that self-test. It comes back later.

Drawing the Areas

The map editor gained a third tool beside Tiles and Entities. Clicks add points, and a click on the first point closes the area. Each area is walkable or a hole, and belongs to a level. Points can be dragged, Shift+click on an edge adds one, right click removes one. Other levels show as faint outlines, and undo covers all of it.

Two snapping rules make it pleasant. Every point lands on a grid of a tenth of a cell, and Ctrl puts it on the nearest cell edge. And a point near another area’s point joins it exactly, on any level, which is how two areas come to share an edge for stairs.

Areas are saved in the map file as plain lines:

nav walk 0 2.000 3.000 20.000 3.000 20.000 15.000 2.000 15.000
nav hole 0 8.000 6.000 12.000 6.000 12.000 9.000

The Bake

When assets are written, each map’s areas are baked into a mesh in the asset file. Per level:

1. Make all areas wind the same way. Clipper’s non-zero fill would otherwise cancel overlaps that wind in opposite directions.
2. Join the walkable areas and cut the holes with Clipper.
3. Round the points to a thousandth of a cell.
4. Split the result into convex polygons, with the same partitioning as before.
5. Link polygons over their shared edges.

Then come the links between levels, and they’re stricter: two edges are linked only if both are outer edges, they lie on one line, and the insides of the polygons are on opposite sides of it. An edge can touch only part of a longer one, so the link is the part they share. A bridge that merely overlaps a path gets no link.

Pathfinding is A* from link to link, then the funnel algorithm from the old code, with an extra path point added where a straight stretch changes level, so each point knows its level from there on. A game calls FindNavPath and doesn’t think about any of this.

The editor has a Test the bake button that bakes the areas as the asset writer would, draws the polygons and the links between levels, and lets me click a start and an end to see the path. My test arena, with water on level -1, ground on 0 and cliffs up to 3, comes out at 19 polygons and 40 links.

The Bugs It Found

The self-test I had for Clipper checked a union and a difference by counting points. I added a proper test for the whole bake, with stairs that aren’t symmetric, and that’s when things got interesting.

X and Y were swapped. This was in the function that converts a point:

Result.W = _mm_cvtpd_epi64(_mm_round_pd(_mm_set_pd(X, Y), ...));

_mm_set_pd takes the high lane first, so this puts Y where X should be. Every Clipper point came back with its coordinates swapped. It had been in the code since I wrote it, inside a SIMD path that never compiled, until I turned SIMD on three days earlier and made the bug live. The old self-test counted points, and a swapped point counts the same. That’s a good lesson about what a test actually checks.

Horizontal joins went the wrong way. Two rectangles sharing an edge unioned into a crossed ring, when one of the horizontal segments ran right to left. I only saw it as a “couldn’t be split” error at a point on my test map that didn’t exist anywhere in the map. Shared edges are exactly what this whole design depends on, and the self-tests cover them now.

Precision. Boolean operations rounded points to 1/128 of a cell, so a point at 31.7 came back as 31.703. They keep 1/16384 now, and the bake’s rounding gets the map’s own points back exactly.

Dangling list nodes. The polygon partitioning kept the first node of a list in a pointer across merges that could free it.

And two bugs that weren’t in the mesh at all. Saving a map with a negative level wrote level 4294967295, because FormatString read %d as unsigned, which had been wrong for negatives all along. Then a grid point of 16.8, which is 16.7999992 as a float, was saved as 16.799, because numbers were cut at their last digit instead of rounded, and it could lose another 0.001 at every save. A text file format really does put your number printing to the test.

Moving

A path is only half of it. Things also have to move a step at a time without ending up outside the mesh.

MoveOnNav takes a position, a level and a target, and walks that straight step through the convex polygons. Over a link, it continues in the next polygon, and the level becomes that polygon’s level. At a wall, what’s left of the step goes along the edge, so things slide along walls instead of stopping dead. A position stays a tiny distance inside the mesh, so that the next step starts on it. Only a link on the edge the step actually left by counts, so a link that touches the same corner doesn’t let you through.

For a click off the mesh, on a cliff face for example, ClosestNavPoint gives the nearest point on it.

The test arena plays on its mesh now. The hero walks around cliffs and up stairs, and creatures find their way around to reach it. Water tiles are still part of the mesh, because ice and stepping stones can make them walkable, and the game blocks them by itself.

What’s Next

Hearthmoor doesn’t have its navigation areas yet, so that’s waiting to be drawn. After that comes playing from the editor, and then I can finally get back to what all of this was for: making the game.

These meshes started with a post in May 2025, with a library and a triangle algorithm written along the way, and then they got put aside for a long time. Now they’re running in a game, drawn in my own editor and baked by my own Clipper.