AI PT 3: BOXHEAD'S Navigation SYSTEM.  I have been asked a lot of times how the navigation and object avoidance is achieved in Boxhead

Before reading this, it is really important to read the AI PT 2: THE MAP SYSTEM article below, as this is the basis for the navigation system.
Ok let's get started. The Navigation is fairly basic, but it is fast and can handle as many enemies as you want, basically each enemy (in this case a Zombie) will access a pre-defined navigation map, see fig 1.1

How do we do this? Well it is pretty simple, we flood-fill the map, if you are unfamiliar with this, then please read http://en.wikipedia.org/wiki/Flood_fill, this explains it really nicely. However, we want to make sure we fill the map one step at time from the Players position because we want the numbers to count away from the destination (the player), the Player is 0 and the cells away from the player are > 0.

Let's look at how we do this:

class NavCell extends Cell

Let's take the original Map cell class and extend it to make a new Class, NavCell. Now we have the NavCell we can create some properties that I think we will need to perform a flood fill. These properties will give us the result in Fig 1.1

{
    public var NavIndex:int;
    public var NavID:int;
    public var MapX:int;
    public var MapY:int;

    public function NavCell( ix:int, iy:int)
    {
        super();
        MapX = ix;
        MapY = iy;
    }
}

Now instead of creating new Cells we now create new NavCells for the map.

for ( var iy:int = 0; iy < MapHeight; iy++)
{
    MapCells[iy] = new Array();
    for ( var ix:int = 0; ix < MapWidth; ix++)
        MapCells[iy][ix] = new NavCell(ix,iy);
}

Now let's fill the Map from the Players position:

// Create a list of NavCells to work with to start the fill
var NavCells:Array = [MapCells[ int(player.y)][ int(player.x)]];

// Set The index to 0 - as 0 is the destination
for each ( var cell:NavCell in NavCells)
    cell.mCellIndex = 0;

// ??? Remember this, we will go over it later
var NavID:int    = Math.floor( Math.random()*1000000000);
while (NavCells.length) //More than one NavCell
    NavCells = FloodMap_Step( NavCells, NavTime);

You can see here that the Player's cell is added to the NavCells and the call to FloodMap_Step is only called then there is a cell in the NavCell. Let's write this function and mark the map.

function FloodMap_Step( cells:Array, id:int):Array
{
    var rCells:Array = new Array()
    for each ( var cell:NavCell in cells)
    {
        // Get all the cells surrounding cells
        // Make sure you handle any overlap i.e. 0-1 = -1
        var northCell:NavCell = MapCells[cell.MapY-1][cell.MapX];
        var southCell:NavCell = MapCells[cell.MapY+1][cell.MapX];
        var eastCell:NavCell = MapCells[cell.MapY][cell.MapX+1];
        var westCell:NavCell = MapCells[cell.MapY][cell.MapX-1];

  HINT: You could cache these different directions with in the class NavCell and create them when you create the map.

        // has the cell already been processed?
        if ( northCell.NavID != id)
        {
            northCell.NavIndex = cell.NavIndex+1;
            northCell.NavID = id;
            rCells.push( northCell);
        }

        // same for South/West/East
        ...           
    }

    // Return all the newly acquired cells
    return rCells;    
}

Now we said we would look at what the NavID is, well this ID allows us to check whether a cell has been processed or not, we don't want to check the same cell twice as the Flood fill will never end. Why not just clear the NavIndex? Well this makes it so you don't have to, you can just process the Navigation every time the player moves (or things change) and not have the overhead of the clear.

Now the Navigation becomes really simple for the Zombie, move to the next lowest cell surrounding the Cell it is on. When there is a ZERO in the adjacent cell then attack or do something...

Another Scenario:

Well this is a little more complex but the same thing applies except you add all the cells that the player's barricades are on.

// Add all the barricades to the NavCells
for each ( var b:Barricade in Barricades)
    NavCells.push( MapCells[ int(b.y)][ int(b.x)]];

Now continue with same as before and the NavMap will end up like FIG 2.1.

Hope this helps to progress your game. Any questions let me know on the email below,

Sean Cooper
develop@seantcooper.com