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.

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

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.

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.

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

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.

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

NodeNetworks are a collection of which are linked to each other using . 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.

Add the following to your screen:

Add the following in CustomInitialize:

Add the following in CustomActivity:

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:

Add the following code to Initialize after initializing FlatRedBall:

Introduction

The VisibilityGrid can be used to quickly calculate line of sight between . 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:

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

Add the following at class scope:

Add the following to Initialize after initializing FlatRedBall:

Add the following to Update:

Adding blockers

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

Introduction

The GetPath method returns a List of 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 .

Introduction

The TileNodeNetwork object is a type of which is designed specifically for tile-based games. Since the TileNodeNetwork object inherits from , all available methods in are available in TileNodeNetwork. Therefore, you should check out the for additional information and features on the TileNodeNetwork object. Normally a TileNodeNetwork is used when creating a game which uses tile maps.

For information on creating a TileNodeNetwork in the FlatRedBall Editor (this isthe most common approach), see the FlatRedBall Editor page.

Benefits of the TileNodeNetwork

The TileNodeNetwork offers the following benefits:

• Simple addition of tiles on a grid-based system using four or eight-way movement.

• Quick index based ( O(1) ) tile finding

• Concept of tile occupation to prevent multiple characters moving on the same tile.

Example - Creating a TileNodeNetwork In Code

The following code creates a TileNodeNetwork that is 10X10 with has a seed (bottom left tile) at 0,0. Add the following using statement:

Add the following to Initialize after initializing FlatRedBall:

Example - Creating a TileNodeNetwork from a TileMap in Code

The following code can be used to create a TileNodeNetwork using a loaded TMX file:

Note that the example above uses a name (PathTile) for simplicity, but you can also use properties. You simply have to convert the properties to a list of names:

Introduction

Many games which have tile maps which also require pathfinding often include different terrain types. For example, a map may include regular terrain, water, and mountains. Terrain is important because certain units may be able to travel over certain terrain faster than other terrain. The SetCosts method allows for specifying the cost of travelling over certain terrain types quickly without modifying the cost of travelling across each Link in the NodeNetwork manually.

How it works

The SetCosts method requires the following steps:

1. The costs of each terrain type must be defined. These are defined in a float array

2. Each point on the tile which is not of the default type must have its terrain type set through the PositionedNode's PropertyField variable.

3. The TileNodeNetwork's SetCost method must be called with the float array containing the cost of each terrain as the argument.

Code Example

The following pieces of code show how a TileNodeNetwork can be set up for different terrain types. First the terrain types must be defined. Since they will be reused in multiple places we'll use an enum:

   public enum TileType
   {
       Mud,
       Water,
       Lava,
       Spikes,
       Quicksand
   }

The following code assumes that tileNodeNetworkInstance is a valid TileNodeNetwork instance which has already hadd its nodes added:

 // let's make a wall of lava
 for (int i = 3; i < 8; i++)
 {
     float xCoord = i;
     float yCoord = 3;
     PositionedNode node = tileNodeNetwork.GetClosestNodeTo(xCoord, yCoord);
     // The PropertyField is a bitfield so we need to
     // shift over the number 1 by the tile type.
     // Because of this we're limited to values between 0 and 31 (inclusive)
     node.PropertyField = (1 << (int)(TileType.Lava));
 }
 // Now let's set the costs of different terrain:
 float[] costs = new float[32];
 costs[(int)TileType.Lava] = 100;
 costs[(int)TileType.Mud] = 3;
 costs[(int)TileType.Quicksand] = 6;
 costs[(int)TileType.Spikes] = 50;
 costs[(int)TileType.Water] = 1.5f;
 tileNodeNetwork.SetCosts(costs);

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.

// Assumes Player is a valid entity
if(InputManager.Keyboard.KeyDown(Keys.Right))
{
    var isTileOccupied = tileNodeNetwork.IsTileOccupiedWorld(
        Player.X + 16, // assumes tiles are 16 pixels
        Player.Y);

    if(!isTileOccupied)
    {
        // un-occupy the current tile:
        tileNodeNetwork.Unoccupy(this);

        tileNodeNetwork.OccupyTileWorld(
            Player.X + 16, 
            Player.Y,
            Player);

        // Move the player to the tile, either by setting the position
        // directly, or by setting velocity or doing some other form of 
        // interpolation.
    }
}

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();
    }
}

Introduction

AddAndLinkTiledNodeWorld adds a new node at the given position, and links it to any adjacent nodes following the DirectionalType specified in the argument call, or using the default DirectionalType specified in the TileNodeNetwork's constructor.

Code Example: Adding Nodes by Clicking

The following code can be added to a screen to allow the user to click the mouse and add new nodes. Newly-created nodes will be connected to adjacent nodes using the DirectionType specified in the constructor (four-way).

// Define the TileNodeNetwork at class scope
// so we can access it in both CustomInitialize
// and CustomActivity
TileNodeNetwork tileNodeNetwork;

void CustomInitialize()
{
    var left = -200;
    var bottom = -200;
    var gridSize = 32;
    var numberOfTilesWide = 40;
    var numberOfTilesTall = 40;

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

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

    // So we can see the cursor
    FlatRedBallServices.Game.IsMouseVisible = true;
}

void CustomActivity(bool firstTimeCalled)
{
    var cursor = FlatRedBall.Gui.GuiManager.Cursor;

    if(cursor.PrimaryClick)
    {
        var worldX = cursor.WorldXAt(0);
        var worldY = cursor.WorldYAt(0);

        // See if there is an existing node there:
        var existingNode = tileNodeNetwork.TiledNodeAtWorld(worldX, worldY);

        if(existingNode == null)
        {
            tileNodeNetwork.AddAndLinkTiledNodeWorld(worldX, worldY);

            // So we can see the newly-added shapes
            tileNodeNetwork.UpdateShapes();
        }
    }
}