Making a Custom Navigation Mesh for AI

Hi Xander here…

This week I decided to totally redo the way I have been handling character movement.

I used to have a free ranging character controller that basically moved in the direction your joystick wanted. I never really had that as my vision for this game as I wanted a more 2.5D feel to the game and a limited number of places you could move to. I got to this point because I was working on the enemy AI scripts using a custom mesh to navigate around.

The game level (or rather endless pattern of a level) is 16 Units wide and two deep.  In this case a Unit is a building component like a piece of floor or doorway or elevator shaft etc.  All these components are 8 x 8 blocks in Unity scaling. This is an example of an elevator shaft:

When you build them all together it looks something like this (that’s a very basic mock up below):

So you got a forward position where you can go up the stairs on the right and a middle position where you can go up the stairs on the left (see they are set back a bit) and a very back position which is through a doorway. So basically there are three parallel positions along the X axis.

What I wanted to do was to create a “patrol point” on every floor space within that grid of a floorplan and also create a patrol point if there is a door that is open.

On the floor positioned at the top or bottom of a stair you do not have a patrol point so there is never anyone at the top or bottom of a stair to block you going up or to knock you back down.

This all gets created at instantiate time and every level is random so I cannot use any of the mesh or nav components that Unity provides.

So all my patrol points get made into lists when the floor is instantiated and added to an array of levels.

When an enemy AI agent starts off they read in all the available patrol point nodes on the floor and work out the available nodes around it to move to.

So the agent knows about the nodes around it in a four square plus it’s own central location. 

As the game mostly scrolls along the left – right axis during game play the nodes are weighted so that travel along the X axis is more likely than the Z. 

At the end of the frame after moving (in late update) the nodes list is refreshed if a new node has been reached.

How does an agent find all the nodes around it?  Using a Raycast is too expensive.  So on each move the agent parses the list of nodes and works out the closest in each direction.

Basically for each node in the list get the x and z and subtract it from your own then put that value in a temporary location – every node gets tested the same way and if the return value is less than the temporary value then you got your closest node in that direction. You would need to do this four times (left, right, forward and back) and handle the null values when there is no space to move next to you. 

At an agent update interval when a new node is reached we first check all the nodes in the list and make a new list of nodes on the floor and our closest points. This gets added to the basic agent control behaviour of “looking around” where the AI stays in one spot and looks left and right in a rotation.  In all cases if they are looking left and the character is right then they cannot pursue him.  If he fires then they will turn.  All of these behaviours are then blended by weight.

I’m not sure if I will continue with this method for the character controller but it’s pretty good for the enemy AI scripts.

Getting a Foot in the Door of Game Design

First of all – sorry about the misleading title – this post is about getting the doors working in the Endless Elevator game that we are currently developing. I thought it was a good pun and that as this post is all about our development process that it wasn’t too bad. The only career advice I got is just to start making games…any games.

You’d think making a door that opens and closes would be a pretty simple thing to do but surprisingly it wasn’t.

I designed and built some 3D models of building components in MagicaVoxel and exported them as .obj files. I use MagicaVoxel because it’s free and really quick and simple to use. When I model components I can be sure that they are all exactly the same scale and that all the different bits (no matter when I made them) are going to fit together without any hassle. But the models are not optimised for game engines as they have a reasonably high poly count due to the modelling process within the program. Most of the models come out with heaps of unnecessary triangles that need to be managed first. In most cases I will import the object into Blender and use the “decimate” modifier on the planes (with an angle of about 20 if you are interested). In the case of the door object it was pretty simple, it is just a door after all, and I didn’t need to optimise it.

Here is what the door looks like in MagicaVoxel:

Notice that the door object is sitting just forward of the enclosing frame and that when exporting the object the center is at the middle bottom plane of that frame. The door is off center because it’s modelled to fit exactly in a doorway that sits exactly in that position within the frame. This saves me a huge amount of time lining everything up when it gets to Unity as the position of the door (or any other object for that matter) is already in the right spot. The problem is that the point of origin for the door is in the wrong spot. It exports a few units behind the door and on the floor! This becomes important when you try and rotate that object (like you would when opening and closing a door) and the pivot point is not where the hinges should be.

To fix this I had to import the .obj file into Blender and reposition the point of origin for the model.

This is what it looks like in Blender when I did this:

To do it I selected the edge that I wanted the door to pivot on when opened.

Then in Edit Mode:
Mesh -> Snap -> Curser to Selected

In Object Mode:
Object -> Transform -> Origin to 3D Curser

So that puts the curser onto the correct position in the middle of that edge where the hinges would be and resets the point of origin (which is where it will pivot when rotated in Unity) to the right spot.

Once we were all imported into Unity and looking good I set up a prefab for the “Doorway” object with the door as a child object. The doorway object has a bunch of colliders to stop the player walking through the walls and a big sphere collider where the door would be to trigger the open / close function when the player walks into it.

This is what the doorway looks like in Unity:

Next I scripted up a few options for opening the door. I’ll post the script at the end of this article but basically there were three options of opening the door that I wanted to test. (Actually I tried it about six ways but whittled it down to the most simple methods – and just as an aside there is an actual “hinge” object type in Unity if you ever need it).

This is how the script looks in the editor:

Notice the slider at the bottom to control how far I want the door to open. It’s really handy to have this when playing in the editor and getting your settings right. If you want to know more about using it see this post

The three tick boxes are for testing the three different ways of opening the door.

Snappy was a quick simple transform of the position from open to closed with no “in betweening”. It looks a bit unnatural as the door magically goes from closed to open but it’s not too bad and most people are pretty used to similar behaviour in video games.

The active line in the code is:
the_door.transform.Rotate(-Vector3.up * 90 * Time.deltaTime);

The next method works more like a door should. In that it swings open and closed the whole way in a steady fashion. But the big problem with this method was that it was OK when the character was going into the doorway and with the swing of the door but when it was time to come back out of the doorway the door was in the way. There was not enough room to trigger the door opening from the other side without being hit by the door as it opened. Plus if the player enters the collider from the wrong trajectory the character gets pushed through a wall by the swinging door which is sub-optimal. I called this method InTheWay!

The active line here is:
the_door.transform.rotation = Quaternion.Euler(targetPositionOpen);

In an effort to combat this I chose to do a hybrid method that opened the door to a point that wouldn’t hit the player and then do the magic transform to get all the way open. I call this one aBitBoth. It looks a little weird too. Like there is an angry fairy pulling the door closed with a snap after the character enters.

Here are all three to compare.


In The Way

A Bit of Both

I’m not too sure which one I’m going to use at this stage as the Snappy method works best for now but I like the In The Way method better. I looks more normal and I like that you have to wait just a few milliseconds for the door to swing (adds tension when you are in a hurry to escape a bullet in the back). I could do something like halt the player movement from the rear of the door when it triggers to open from the closed side or maybe play around with the radius of the sphere. Neither solutions seem like great ideas to me right now but something like that will need to be done if I’m going to use that method. Maybe I could just have the door swing both ways and open to the outside when he is behind it but that’s probably a bit weird for a hotel door.

Here is that script that I was testing with:

Oversharing About Overriding

The idea of a class and how objects, scripts or behaviours are implemented in Unity is pretty straightforward. Each object or type is a class and each script is a sub class of the MonoBehaviour class. So we are using classes all the time. Even if a script isn’t a behaviour, like a controller script or similar, the common pattern in a Unity project is to make an empty object and attach the script to it.

Classes are useful for separating code that is re-usable or for segregating data structures. Good Class usage is supposed to make your code easier to read if you have a sensible naming convention and self explanatory methods. I don’t know if it really does help personally I find it hard to keep flipping between scripts and classes in different locations when writing and debugging. Sometimes I find it easier to have all behaviours in one big class and split up code into functions where possible.

I’ve published two games and written many more but I have never used a class that wasn’t derived from standard MonoBehavoir. But lately I’ve changed things up a bit. I started working with the concept of Overriding. I’m not sure if it’s any easier or better at this stage but I’ll describe the general concept and you can try it for yourself (of course you’ve probably been doing this for years!).

But first let’s go back to Classes.


A useful metaphor for a class that’s been used many times is the Vehicle. The basic behaviour for a vehicle is that it moves. Be it a bike, a car, a motorcycle, a truck, or a tank they can all be categorised as a type of “Vehicle”. Our basic variables for all Vehicles could be maxSpeed, acceleration, and direction. Our base class could also have a function called Move().

If we want to make a new Vehicle we can go:
Vehicle someVehicle = new Vehicle(); // and it get’s all those parameters (maxSpeed, acceleration, direction) and can access the Move() function.

If we want to make a constructor to handle those default parameters on instantiation we can do something like this:

Using the constructor I can make a new sportsCar instance of a Vehicle object and initialize the base values immediately:
Vehicle sportsCar = new Vehicle(210, 21, Vector2.right, “MazdaRX7”);

Then if I upgrade my RX7 with a new fuel injector I can access those values like this:
sportsCar.MaxSpeed = 240;

And of course I can drive it round now too:

Now I can keep going building automobiles with different variables that represent their base characteristics – fill a whole garage if I want.
But what if I made an asumption about my Vehicle() class that they all had wheels and I wanted to add a plane?
I could write the plane a new class to handle flying or I could keep the sanctity of the Vehicle concept intact and just override the Move() function to include a bit of up and down action.


What we can do is override the Move() function in the Vehicle class with an Airplane Move() function.
What we are doing here is also called up Upcasting. We are effectively overriding a Parent method in a Child Class.
The Vehicle class and the new Airplane class form part of an Inheritance Hierarchy.

Vehicle -> Airplane (Parent -> Child)

This is how to do it.
To make a Parent method able to be overridden use the ‘virtual’ keyword on it’s method and the ‘override’ keyword in the child method.

The parent Vehicle class has:
public virtual void Move()
// The direction variable is a Vector2 as it moves around on a flat surface using wheels

The child Airplane class has:
public override void Move()
// The direction variable is a Vector3 which adds the up and down movement using wings

For example the Airplane Class

You can also add the Parent method into the new Class by using the base keyword but unfortunately this is where my example above falls down. You would never need to keep the 2D movement and add the 3D movement on a vehicle. Unless maybe you were giving the RX7 a jetpack and wings – it could be that kind of game.

If you have to do this the syntax is to declare the function in the new Child class using “base” to indicate that the parent(base) method is being used:

I’ve put links at the bottom of the post for more info here if you want it.

But why use a custom class and the override feature? One good reason is when you don’t need the stuff that you inherit from MonoBehaviour.
You could define your own class when you don’t need functions like Update(), Awake() and similar things like FixedUpdate(), OnCollision(), or UI behaviours.

You could define classes when they are not game objects like in-game information, a score multiplier, number of bullets left, etc. or you could use them when you have a common data structure that is shared by several objects like in our Vehicle example but you certainly don’t have to. One of my favourite things about old programming and scripting philosophy is the concept ‘that there is more than one way of doing it’. You don’t have to write perfect code that follows a pattern or schema. It just has to work (mostly) and be understandable (at least to you) next time you have to look at it.