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.