NavMesh

Island Invasion Tech I – Dynamic NavMesh

One of the most challenging aspects of Island Invasion’s development was implementing the ability for the player to “control the enemy path”. In this post, I’m going to go over the solution to that problem, the alternatives, and lessons learnt.

Unity’s NavMesh System

Out of the box, Unity provides you with a well-developed navigation system, which I’ll refer to as the NavMesh system for simplicity. The idea behind a NavMesh is that  the world area can be broken down into polygons, representing walkable areas. Agents (entities traversing the mesh) can navigate the world by walking these polygons. Calculations happen behind the scenes to determine the quickest route to take between the polygons, resulting in a path of vectors the agent should follow from start to finish.

Unity NavMesh example

Unity’s NavMesh visualised (from Unity’s tutorials)

Unity makes it really simple to create a NavMesh – simply create or import a model, mark the NavMesh static flag as true, open the Navigation window (under Windows -> UI), and then “Bake”. The NavMesh is now ready to use! Add a NavMeshAgent to a non-static GameObject and you’re pretty much there.

This works really well for a game where the levels are designed by hand, for example in a first-person shooter. But for a game with procedurally generated levels, it’s more of a challenge.

Fortunately, Unity provides a package to allow you to bake a NavMesh in realtime. It’s available on their GitHub here.

Realtime Navigation Baking

When a map is generated in Island Invasion , a few things happen. Firstly, a noise function is used and smoothed to create the mesh. This is what you see on screen (I’ll cover the level generation in more detail in a future post). The sea is spawned in next; the enemies will navigate this area. A simple collider is added to the sea, which allows a NavMesh to be generated. This is done really simply, by adding a NavMeshSurface component to the sea, setting its mask to “Water” and “Ground”, then calling the “BuildNavMesh” method on the component instance. This creates a NavMesh on the water, carved out by the landmasses.

At the start of the game, the EnemyPathManager does two things. Firstly, it figures out where enemies can enter and exit the map. It generates a bunch of vectors where the sea is wide enough at the edge of the map. Then, it works out the longest path available from these vectors by calculating paths between each of them. It then selects the longest path as the path you see at the start of the game.

Path start

These paths are calculated as the longest at the start of the game

Enemy Navigation

All enemies have a NavMeshAgent component attached. Lazily, I decided to just remove this on airborne enemies, as they follow a straight path near enough. The NavMeshAgent is data driven by an attached Enemy component, which, amongst other things, defines how fast the enemy should move.

Enemies take the path generated by the EnemyPathManager, and set their NavMeshAgent’s path to that. The NavMesh is then responsible for movement along the path – very little else needs to be done in terms of sea enemy movement.

Path blockers, which I’ll cover in the next section, can break up the path, changing where it goes. The EnemyPathManager recalculates the path regularly, and lets all enemies know when it has changed using my custom EventSystem (another blog!). If the path is not suitable for the enemy, it will recalculate a path itself. Sometimes, the path is still invalid, in which case the enemy is teleported to the nearest path “corner”. The enemy can then continue on its merry way!

NavMesh

The NavMesh visualised

Path Blockers

Path blockers allow the player to redirect and slow down enemies. They are a neat little mechanic that allows more for strategic tower placement

Path blockers have a NavMeshObstacle component attached to them. This allows them to “carve” the NavMesh, creating holes. This updates the NavMesh, meaning the path can change. As stated in the previous section, the EnemyPathManager is constantly checking for these changes, and lets enemies know so they can plan a new route.

There is a chance that by placing a path blocker, the route becomes incomplete from start to finish. In this instance, the last path blocker placed is removed, completing the path once more.

Tweaking this mechanic to work as expected was very difficult, but the results are very satisfying!

The Alternatives

I considered (and trialled) a few alternatives to this method, which I’ll list below:

  • Span blockers – one idea was to have an entire span of water blocked, rather than individual “bollards”. I scrapped this as it didn’t feel as satisfying the place them down. Visually it looked pretty sweet, as it used Star Wars-esque laser fences!
  • Gates – another ideas was to have some pre-placed “gates” across spans, that the player could activate or de-activate. This method was scrapped due to time, as it required messing with the already complex world generation. In another life (or a sequel perhaps!) this saw the light of day and was very satisfying to use.
  • A* grid – A* is popular in many games, and isn’t actually that complicated to implement. It would likely have been more robust too. One of the big problems with the NavMesh is that you don’t really know what Unity is doing behind the scenes, when working out paths and such. Enemies in beta got stuck in coves, going nowhere. An A* grid would have allowed me to control how paths are worked out, and how enemies dealt with bad situations. Once again though, this was a victim of having a lack of time.
  • Nothing – given the problems with the dynamic pathing in the end, I came close to scrapping it altogether! A game with randomly generated levels was possibly enough of a USP on its own. But playtesters enjoyed it, so I kept it, and it does add depth to the game.
Lessons Learnt
  • Know the alternatives – if the list above is anything to go by, know that you can switch out your mechanic if need be.
  • Playtest – the playtesters found a number of issues that I wouldn’t have. They don’t play the same way as you do, so watch and learn!
  • Persevere – the mechanic might not feel right now, but tweak and iterate. Dynamic pathing was still being tinkered with on the week of release. Play with it until it feels right.
  • Make sure you can actually do it – while Unity is a fantastic engine, there are some things it just won’t do. If Unity hadn’t provided their GitHub repo, dynamic pathing probably wouldn’t have seen the light of day, given my timescale.
Island Invasion sounds like an amazing game, where can I play it?

I’m glad you asked.

Check out Island Invasion’s page on this website, or if you’re super-keen, there’s a link to Steam below.