Right Foot, Left Foot (III)

Continuing with my work on navigation meshes, the latest changes made during the past few days bring a lot of new and exiting improvements:

Visualizing the navigation mesh

Having a good look at how the nav mesh is defined is very important in order to understand where its problems are.

Screen Shot 2017-09-17 at 6.59.59 PM.png

As the image above shows, each cell will display its center and normal vectors now (and correctly ordered)

Vertex order

The first change in the list was to enforce the order of the vertices for each cell to make it clockwise. This is a must in when identifying which points are inside or outside of a given cell. Otherwise, normal vectors won’t be pointing in the right direction and results will end up all mixed up.

I also modified the OBJ loader also transform vertices accordingly.

Edge Sliding

Probably the most noticeable change of all, the new implementation is able to handle collisions with walls and borders in a more friendlier fashion than before. Instead of just stopping movement once a character has reach an unshared edge (a wall, for example), the nav mesh will now compute a sliding vector in order to make the movement more fluid.

Screen Shot 2017-09-17 at 6.59.59 PM copy

In the picture above, the player attempts to walk forward (red arrow). Since there’s no valid cell in that direction, the nav mesh will slide the movement slightly to the up and to the right.

Enhanced navigation controller

All the above changes lead to an enhanced NavigationController component. Now, it will keep track of the current cell (so we don’t have to compute that every iteration) and provide new methods for movement, teleport and snap (soon). And it will update the current node’s position automatically, too.

One big commit

All of these changes, plus a couple more, have been pushed to the devel branch in Github. Feel free to take a look here

Bonus track: Math fixes

I took some time to revise and improve some of the math tools related with nav meshes, like planes, distance and intersection methods. It’s funny how there’s still a lot of room for improvement in code that I’ve been using for the past 10 years or more…


Right Foot, Left Foot (II)

I’ve been improving the navigation controller to support holes and bridges in the level geometry. Check this out:

This slideshow requires JavaScript.

The underlying navmesh for the above scene is like this:

Screen Shot 2017-07-19 at 11.33.08 AM


Once again, the navmesh borders take into consideration the width of the character model so it doesn’t stand in the air.

I’ll be upgrading the navigation controller soon with pathfinding and other improvements. See you next time!



Right foot, left foot (I)

It’s been a while since I’ve introduced a NEW feature in Crimild. I mean, this is not a refactor or an improvement over something already there, but a completely new thing. Exciting, right?

So, without further ado…


Navigation meshes are the other big feature to be included in Crimild’s next release (soon). Simply put, a NavMesh is a data structure used for navigation (duh) and pathfinding on complex spaces. It defines a set of polygons (i.e. triangles), describing areas that are traversable by agents in a simulation, simplifying things like collision detection with walls and other static objets. Basically, it defines what “the floor” means for our game.

The current implementation is pretty basic, but I implemented a tool for loading nav meshes from geometry described in OBJ files. That way, you can create a whole level and its nav mesh in a 3D editor like Blender (and I don’t have to write a level editor at this stage). Once loaded, triangles are linked together automatically based on edge sharing. It’s simple, but it’s more than enough for my secret project ;).

There’s a demo already available in the examples projects with a simple scene and a walking character. Check it out:

This slideshow requires JavaScript.

The next step is to add support for “bridges” in the geometry (as in characters walking below other parts of the level) and pathfinding tools (like A* or other techniques).

See you next time!