First, I decided to add static objects in the form of walls to the castle. These are not tiles, so my pathfinding code does not handle them at all. Let’s call it a stress test.

Don’t mind the jankiness of the walls.

I added statics to collision avoidance with special handling.

All right, some things worked well, others not so much.

• Queuing is a nice emergent behavior from steering, that worked fantastic.
• Walls are a major problem.
• Clumping is a major problem.
• Mages often get caught dodging back and forth near the door, and in some cases, refuse to walk through it.

Let’s say we’re trying to reach the red dot.

The raycast detects a potential collision with the static walls and creates a force pushing the mage upward, to the left.

The avoidance code is not aware there will also be a wall in that direction until the mage turns, and then with a powerful force, tells the mage to go back down.

And then they begin a cycle of back-and-forth, never going through the door.

Okay, steering for collision avoidance probably isn’t the right solution for larger static objects like walls.

Back to Pathfinding

What if I just updated my node-based graph to omit overlap with walls, so they’d never recommend walking through a static object?

Unfortunately, tiles are much larger than these wall chunks. It makes a mess.

While the answer might seem like I should just use tiles for walls, but this’ll show back up with objects like trees, buildings, and so-on.

I thought to myself, you know what would solve this…

You should really stop using this quirky home-grown graph and build a navmesh.

Let’s build a navmesh

I should’ve done this a year ago.

it took a few hours to integrate a GDX navmesh library with my tile system and static objects, but it was surprisingly straightforward (thanks to libraries, of course).

I modified the PathFindSystem’s core algorithm to find a path of portals. I ripped out the node-graph system, the pathskipping algorithm, and replaced it with the string pull algorithm for the navmesh.

However, because navmeshes path along edges, there was some work for adding a body radius padding near corners so that static avoidance wouldn’t have to handle that on its own.

It took less time than writing the original node-based approach.

The most difficult part came from a hidden tolerance setting on the clipper. It saw 25 units as the minimum for passable, but in my game, that is 25 meters. That’s roughly the size of the entire castle interior.

Of course, I didn’t see that setting until I spent an hour debugging why the navmesh was a completely empty unwalkable polygon.

Navmesh pathfinding

Since my PathFindSystem stores a set of coordinates in a NavAgent component, the MovementSystem didn’t have to be updated at all to work with the new system.

And it worked so much better.

But can it beat the hallway gauntlet?

Let’s find out.

Not bad. What about if two mages are heading down the hallway in opposite directions?

Will unit avoidance work well enough, will they be trapped by a missing tile?

Huh, it worked!

A surprise, to be sure, but a welcome one.

Edge Cases

I didn’t add support stitching two navmeshes from different areas together yet for when the castle portcullis and drawbridge drop, but it shouldn’t be difficult to add as a future improvement.

The navmesh solves a substantial amount of issues, but what should be done when a user tells the unit to move off of a navmesh?

Most older games have the unit just stand still confused. Modern MOBAs seem to have the unit walk to the boundary of the navmesh and halt.

I think that’s the better UX, so I decided to add support for it.

When a user sends a MoveCommand, I find the nearest navmesh and the nearest edge. Since the edge of a navmesh would actually get a mage stuck, I find the path to the closest point towards the navmesh triangle’s centroid beside the edge.

I decided to keep the final destination for now until I add support for stitching together navmeshes so that units can still move between them. After I add that support, I’ll remove it, and units will halt.

So I’ve handled that… edge case. 🥁