Overview

The FlatRedBall.AI.Pathfinding namespace provides implementation of pathfinding. Pathfinding is used in determining the best path from one location to another.

NodeNetwork Class

The NodeNetwork class provides the facility to group together PositionedNode items, and discover the best paths between them. Currently, only the A* pathfinding algorithm is implemented.

PositionedNode Class

PositionedNode represents a location within the NodeNetwork.

Link Class

PositionedNodes are linked to each other by Link objects. Link objects represent the cost from one PositionedNode to another.

Introduction

The VisibilityGrid can be used to quickly calculate line of sight between IViewers. The VisibilityGrid is a very efficient class when dealing with a small number of squares. For example, if each IViewer has a radius smaller than 10, visibility updates can be incredibly fast. The larger the radius (in tiles), the slower performance becomes. Visibility calculations require O(n^2) operations where N is the view radius in tiles, so be careful with larger view radii.

VisibilityGrid and IViewer

The VisibilityGrid can contain any number of IViewers. An IViewer is an object with a position and a view radius. The VisibilityGrid uses this information to calculate what is in view. Therefore, to use a VisibilityGrid, you must create a class that implements the IViewer interface.

Code Example

The following example shows how to create a simple Sprite IViewer, move it around a grid, and view the resulting visibility.

Create the IViewer class. Normally this would be an Entity, but we're going to just whip something together quickly for this example:

public class Viewer : IViewer
{
    public Sprite Sprite
    {
        get;
        set;
    }

    public float WorldViewRadius
    {
        get
        {
            return 5;
        }
        set
        {
            // do nothing, may want to allow a setter in real code.                
        }
    }

    public float X
    {
        get
        {
            return Sprite.X;
        }
        set
        {
            Sprite.X = value;
        }
    }

    public float Y
    {
        get
        {
            return Sprite.Y;
        }
        set
        {
            Sprite.Y = value;
        }
    }

    public float Z
    {
        get
        {
            return Sprite.Z;
        }
        set
        {
            Sprite.Z = value;
        }
    }
}

Add the following using statements in your Game1.cs file:

using FlatRedBall.AI.LineOfSight;
using FlatRedBall.Input;

Add the following at class scope:

VisibilityGrid visibilityGrid;
Viewer viewer;

Add the following to Initialize after initializing FlatRedBall:

float seedX = -15; // this is the left side
float seedY = -15; // this is the bottom
float spacing = 1; // the size of each grid space (this means 1X1)
int gridSizeX = 32; // the number of cells on the X axis
int gridSizeY = 32; // the number of cells on the Y axis
visibilityGrid = new VisibilityGrid(seedX, seedY, spacing, 
    gridSizeX, gridSizeY);

visibilityGrid.Visible = true; // for debugging, this makes the light-blue Sprite show up

viewer = new Viewer();
viewer.Sprite = SpriteManager.AddSprite("redball.bmp");
visibilityGrid.AddViewer(viewer);

Add the following to Update:

InputManager.Keyboard.ControlPositionedObject(viewer.Sprite);

if (visibilityGrid.Activity())
{
    visibilityGrid.UpdateDisplay();
}

Adding blockers

You can modify the code above as follows: Add the following after creating the VisibilityGrid:

visibilityGrid.BlockWorld(3, 3);
visibilityGrid.BlockWorld(4, 3);
visibilityGrid.BlockWorld(3, -2);
visibilityGrid.BlockWorld(5, 0);

// This will help us see the debug display better:
FlatRedBallServices.GraphicsOptions.TextureFilter = TextureFilter.Point;

Did this article leave any questions unanswered? Post any question in our forums for a rapid response.

Introduction

NodeNetworks are a collection of PositionedNodes which are linked to each other using Links. NodeNetworks are used for pathfinding.

Creating a NodeNetwork in Code

The following code creates a simple NodeNetwork and a Sprite. Pressing the 1, 2, 3, or 4 keys causes the Sprite to move toward a given node on the NodeNetwork.

using FlatRedBall.AI.Pathfinding;
using FlatRedBall.Input;

Add the following to your screen:

NodeNetwork nodeNetwork;
Sprite sprite;
List<PositionedNode> nodePath;

Add the following in CustomInitialize:

 // Instantiate the NodeNetwork.
 nodeNetwork = new NodeNetwork();

 // Create the 4 nodes.
 PositionedNode node = nodeNetwork.AddNode();
 node.Position = new Vector3(-150, 150, 0); // top left

 node = nodeNetwork.AddNode();
 node.Position = new Vector3(150, 150, 0); // top right

 node = nodeNetwork.AddNode();
 node.Position = new Vector3(150, -150, 0); // bottom right

 node = nodeNetwork.AddNode();
 node.Position = new Vector3(-150, -150, 0); // bottom left

 // Link the nodes together.
 // LinkTo creates two links - one to and one from.
 float linkCost = 1;
 nodeNetwork.Nodes[0].LinkTo(nodeNetwork.Nodes[1], linkCost);
 nodeNetwork.Nodes[1].LinkTo(nodeNetwork.Nodes[2], linkCost);
 nodeNetwork.Nodes[2].LinkTo(nodeNetwork.Nodes[3], linkCost);
 nodeNetwork.Nodes[3].LinkTo(nodeNetwork.Nodes[0], linkCost);

 // Make the NodeNetwork visible.  Usually only used for debugging
 // and development.
 nodeNetwork.Visible = true;

 // Create the Sprite used to move around the NodeNetwork
 sprite = SpriteManager.AddSprite(RedBallTexture);
 sprite.TextureScale = 1;

Add the following in CustomActivity:

 FlatRedBall.Input.Keyboard keyboard = InputManager.Keyboard;

 // Press 1, 2, 3, or 4 to set the Sprite's path for the target node.
 if (keyboard.KeyPushed(Keys.D1))
 {
     nodePath = nodeNetwork.GetPath(
         ref sprite.Position, ref nodeNetwork.Nodes[0].Position);
 }
 if (keyboard.KeyPushed(Keys.D2))
 {
     nodePath = nodeNetwork.GetPath(
         ref sprite.Position, ref nodeNetwork.Nodes[1].Position);
 }
 if (keyboard.KeyPushed(Keys.D3))
 {
     nodePath = nodeNetwork.GetPath(
         ref sprite.Position, ref nodeNetwork.Nodes[2].Position);
 }
 if (keyboard.KeyPushed(Keys.D4))
 {
     nodePath = nodeNetwork.GetPath(
         ref sprite.Position, ref nodeNetwork.Nodes[3].Position);
 }

 // Progress towards the goal.
 if (nodePath != null && nodePath.Count != 0)
 {
     PositionedNode node = nodePath[0];

     if ((sprite.Position - node.Position).Length() < .1f)
     {
         nodePath.RemoveAt(0);
         sprite.Velocity = new Vector3();
     }
     else
     {
         float magnitude = 50;
         var directionToMove = (node.Position - sprite.Position).AtLength(50);
         sprite.Velocity = directionToMove;
     }
 }

Loading a NodeNetwork From .nntx

The .nntx file format is a standard way to define node networks; however, there is currently no built-in .nntx creating tool supported. Therefore, apps which are interested in working with nntx will need to create their own .nntx files by using the NodeNetworkSave class.

If you have an existing .nntx you can load it from-file by adding it to the FlatRedBall Editor or to Visual Studio. If you add it directly to Visual Studio, you must manually load the file:

1. Add the file to your project in Visual Studio

2. Select the .nntx file once it's in the Solution Explorer.

3. Press F4 or right click and select Properties

4. Select "None" for the Build Action.

5. Select "Copy if newer" for the "Copy to Output Directory".

Add the following using statement:

using FlatRedBall.AI.Pathfinding;
using FlatRedBall.Content.AI.Pathfinding;

Add the following code to Initialize after initializing FlatRedBall:

NodeNetworkSave save = NodeNetworkSave.FromFile("sample.nntx");
NodeNetwork nodeNetwork = save.ToNodeNetwork();
nodeNetwork.Visible = true;

Introduction

The Visible property controls whether the NodeNetwork has a visible representation. The visible representation for NodeNetworks can be useful in tools and during the development of a game.

Code Example

The following code shows how to make a NodeNetwork visible in code, and how to properly clean up the NodeNetwork when the containing Screen is destroyed.

private void CustomInitialize()
{
  // assuming the NodeNetwork is defined in Glue.
  // If not, you can create it in code too
  NodeNetworkInstance.Visible = true;
}

private void CustomDestroy()
{
  // Setting it to invisible automatically removes all shapes
  // from the ShapeManager.
  NodeNetworkInstance.Visible = false;
}

Keep in mind that you do not need to set the Visible to false if you are setting a NodeNetwork's visiblity to true in the FlatRedBall Editor - generated code handls that automatically.

Introduction

OccupyTileWorld marks the tile at the given location (in world coordinates) as occupied. Occupied tiles can have an occupier which can be checked with the GetOccupier function. Note that occupied tiles will still be considered in pathfinding.

Code Example

The following code shows how to check if a tile is occupied, and if so, to move a character to the given tile. To keep the code shorter, it only considers moving in one direction.

Introduction

The GetPath method returns a List of PositionedNodes which can be used to get from one point to another. The GetPath method first PositionedNode will be the closest node to the startPosition argument and the last PositionedNode will be the closest node to the endPosition.

Example

For an example on how to use GetPath, see the main NodeNetwork page.

The Cost member represents the difficulty in traveling the node. Cost can be based on distance, but can also be adjusted to represent terrain difficulty or other concepts related to making decisions about which path to take. Examples include:

• Difficulty in crossing due to terrain

• Difficulty in crossing due to risk (enemies, thieves)

• Resources required to perform a particular action (if node networks are used abstractly)

The cost property is used by the NodeNetwork to find the most efficient path from one node to the next.

The NodeLinkingTo property gets or sets the PositionedNode that the Link connects to. Notice that a link only has one NodeLinkingTo. This means that links are "one way". Therefore, if two PositionedNodes need to link to each other, then each will need a Link to the other.

The UpdateShapes method refreshes the visible layout of the NodeNetwork. This method is internally called when a NodeNetwork is first made visible. If you are making any changes to a NodeNetwork, such as by changing existing nodes or adding new ones, you need to call UpdateShapes if you would like those changes to be reflected in the visible node network.

Introduction

Links represent a one-way path to a PositionedNode. PositionedNodes store a list of links to other PositionedNodes internally. These are used by NodeNetworks to find the shortest path between two nodes.

One-Way Links

Links are one-way to support wider functionality with pathfinding. In other words, if Node A and B link to each other, then A stores a link to B and B stores a link to A. The reason this is important is because the cost to travel from A to B may not necessarily be the same as the cost to travel from B to A. If A is on higher ground, then traveling to B may be considered easier because the trip is downhill.

Introduction

PositionedNodes represent locations within a NodeNetwork which can be travelled to. PositionedNodes have a position and multiple links to other nodes.

Pathfinding

Links can be created between any two PositionedNode objects, and can be one-way or two-way. A link has an associated value, which represents the cost of traveling across that link. Once a set of PositionedNode objects have been created, linked, and then added to a NodeNetwork object, the shortest path from one node to another can be discovered.

Creating a Link

To create a link from one node to another, call the LinkTo method. This automatically creates a two-way link between the nodes. The LinkToOneWay method creates a one-way link from the node this method is called on, to the node that is passed on the method.

Introduction

AddAndLinkTiledNode adds a new PositionedNode at the argument X, Y index at the argument DirectionType, or using the default DirectionType specified in the constructor if one isn't specified. This method uses indexes, where 0,0 is the bottom left of the TileNodeNetwork. Each index represents one tile, so if your TileNodeNetwork has a tile size of 16, then an X value of 1 would translate to 16 pixels further to the right than an X index of 0.

Code Example - Adding nodes manually

The following code adds a few nodes to a TileNodeNetwork using X,Y indexes.

void CustomInitialize()
{
    var left = -150;
    var bottom = -150;
    var gridSize = 32;
    var numberOfTilesWide = 30;
    var numberOfTilesTall = 30;

    var tileNodeNetwork = new TileNodeNetwork(left, bottom,
        gridSize, numberOfTilesWide, numberOfTilesTall, DirectionalType.Four);

    // add nodes at some positions at index X, Y
    // Note this is index and not world positions, 
    // so 0,0 will always be the bottom-left location
    // of the node network regardless of its actual world
    // position
    tileNodeNetwork.AddAndLinkTiledNode(0, 0);
    tileNodeNetwork.AddAndLinkTiledNode(1, 0);
    tileNodeNetwork.AddAndLinkTiledNode(2, 0);
    tileNodeNetwork.AddAndLinkTiledNode(3, 0);


    tileNodeNetwork.AddAndLinkTiledNode(2, 1);
    tileNodeNetwork.AddAndLinkTiledNode(3, 1);
    tileNodeNetwork.AddAndLinkTiledNode(4, 1);
    tileNodeNetwork.AddAndLinkTiledNode(5, 1);


    tileNodeNetwork.AddAndLinkTiledNode(2, 2);
    tileNodeNetwork.AddAndLinkTiledNode(2, 3);
    tileNodeNetwork.AddAndLinkTiledNode(2, 4);
    tileNodeNetwork.AddAndLinkTiledNode(2, 5);

    // So we can see the node network changes
    tileNodeNetwork.Visible = true;
}

Code Example - Adding Nodes with the Cursor

The following code can be used to add nodes with the cursor when the PrimaryDown value is true (left mouse button). The following code could be added to CustomActivity of a Screen which has access to a TileNodeNetwork.

var cursor = GuiManager.Cursor;

if(cursor.PrimaryDown)
{
    TileNodeNetwork.WorldToIndex(cursor.WorldX, cursor.WorldY, out int xIndex, out int yIndex);

    var nodeAtPoint = TileNodeNetwork.TiledNodeAt(xIndex, yIndex);
    if(nodeAtPoint == null)
    {
        TileNodeNetwork.AddAndLinkTiledNode(xIndex, yIndex);
        TileNodeNetwork.UpdateShapes();
    }
}