[TOOL] Automatic Waypoint Generation - a Unity to Unreal journey


I want to use waypoints not to navigate Agents but as a way to decide why to go to location x not z. They are used to store spatial information to support a good decision process.

What are the waypoints as a data structure?

Basically it is a graph of connected nodes as dense as you wish. You can search the graph like any other graph structure. You can also use it to flood it with information like in a heat map where you store information like “how dangerous is this area” to further enhance your decision process.

It could look like this:

So how to start and what i did until now?
I did this before for Unity and one time with the Recastnavigation SDL example. So i have something as a base.
The data in need is from the NavMesh - intermediate data produced during its creation to be precise.
In Unreal i have to change the engine source since i need information recast navigation produces while building the NavMesh.

Since i have no experience with UE4 i decided to start simple and rough.

  1. I added a AActor subclass to the source which can process a recast rcCompactHeightfield - which is the information i am interested in. My ARecastProcessor.
  2. I changed the NavMesh sources that they - if exists - hand over this data to my ARecastProcessor so that it can do something with it.
    Rest happens in the project not in the engine.

In the engine i then subclassed ARecastProcessor and added it to the stage and connected it to the NavMesh. It will be called if the NavMesh is rebuilt.

What data is this?
The data are the Voxels recast navigation uses to build the NavMesh. A Voxel-Representation of the walkable areas and the border of it. You can also examine this data to automatically find areas which can be used as cover or such.

Ok we have access to the data what now?
I now kind of flood/splash the Voxel-Walkable-Areas with a restricted range. The algorithm produces a kind of Voronoi-Partitioning. You can see it below in the screenshots. The center of the painted regions will later be the locations of the waypoints.

Next steps

  1. Calculate the waypoints and their connections
  2. A additional skeleton-graph representing the structure of a environment
  3. When this works with one tile, make it work with multiple NavMesh-Tiles (will be the worst part)

How did it feel compared to Unity?
Well in Unity i had no access to the source so i also had to use a 3rd-Party NavMesh solution. This is easier in UE4. Also i like that i can work directly in XCode.
I am no experienced C++ Coder but this actually was not the problem until now. I expected more problems. Debug-Drawing was worse in Unity since the performance was bad if i used standard Debug-Drawing. I had to build real meshes during this process. In Unreal i can simply draw Points without bothering about Performance. The rest is mostly algorithms so the work is comparable there.

Now how does this look

Simple test-scene:

How the processor is connected to the NavMesh:


How the partitioning looks like:

I could not have done this
Without the great work and kind help of Mikko Mononen the creator of recastnavigation which actually drives most NavMesh-Implementations i know of.

If you are interested in the process. Any advices on how to organize and do things better is very welcome,

Looks good. reminds me of the old Life of crime game with Cypresshill. That game had the best navmesh out and still ranks top 5 of AI nav. Is this out yet? Been lookin for somethin like this. Good job