Benefits

If you've tried to build a road pathfinder yourself, you may have noticed it's hard to get it correctly. Mainly corners on foundations are a problem. Using the pathfinder from the library will solve that for you, so you don't have to do the hard work yourself.

Initialization

As with any library, before you can use it, you need to import it. You can do this by placing the following line at the top of your code.

import("pathfinder.road", "RoadPathFinder", 3);

This imports the road pathfinder version 3 and names it RoadPathFinder. You can now instance it like any other class:

local pathfinder = RoadPathFinder();

Now set what kind of road type you want to find a path for:

AIRoad.SetCurrentRoadType(AIRoad.ROADTYPE_ROAD);

Before you start finding a route, you may want to set some parameters first. The available parameters are:

To set a parameter, you just use:

pathfinder.cost.tile = 100;

Planning a route

SO, now we know how to create an instance of the pathfinder and to set the cost functions, it's time to put that knowledge to some use. Let's plan our first road. First we need one (or more) source tile(s) and one (or more) goal tile(s). For now let's assume we already have those, as it's outside the scope of this page to explain how to get those. So say for example we want to build a road between tile_a and tile_b. First we call InitializePath on our pathfinder object:

pathfinder.InitializePath([tile_a], [tile_b]);

The pathfinder expects an array of source tiles and an array of goal tiles, since we only have one source and one goal tile, we'll just create two arrays with one element each. Now the pathfinder is ready to find a path.

local path = false;
while (path == false) {
  path = pathfinder.FindPath(100);
  AIController.Sleep(1);
}

The parameter FindPath accepts is the number of iterations it should do before returning. 100 is just fine. Don't make that value too big, as you'll notice slowdowns in OpenTTD. The AIController.Sleep(1); line is really needed. FindPath returns false if it isn't finished with pathfinding. When it's done, it returns either the path it found or null to indicate no route exists.

Building the planned route

Suppose the pathfinder returned a path, how do start building it? For a start, it's nice to know that FindPath returns an instance of the AyStar.Path class. To view the documentation, open bin/ai/library/graph/aystar/main.nut. Basically, it has three functions: GetParent(), GetCost() and GetTile(). GetCost() isn't useful for now, so we'll just use GetParent() and GetTile(). To build the route found by the pathfinder, we call path.GetParent() until it returns null. As the pathfinder can also return bridges / tunnels, we need to check the distance between the current node and the previous node. If that distance is more than 1, we should build a bridge / tunnel.

while (path != null) {
  local par = path.GetParent();
  if (par != null) {
    local last_node = path.GetTile();
    if (AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) == 1 ) {
      if (!AIRoad.BuildRoad(path.GetTile(), par.GetTile())) {
        /* An error occurred while building a piece of road. TODO: handle it. 
         * Note that this could mean the road was already built. */
      }
    } else {
      /* Build a bridge or tunnel. */
      if (!AIBridge.IsBridgeTile(path.GetTile()) && !AITunnel.IsTunnelTile(path.GetTile())) {
        /* If it was a road tile, demolish it first. Do this to work around expended roadbits. */
        if (AIRoad.IsRoadTile(path.GetTile())) AITile.DemolishTile(path.GetTile());
        if (AITunnel.GetOtherTunnelEnd(path.GetTile()) == par.GetTile()) {
          if (!AITunnel.BuildTunnel(AIVehicle.VT_ROAD, path.GetTile())) {
            /* An error occured while building a tunnel. TODO: handle it. */
          }
        } else {
          local bridge_list = AIBridgeList_Length(AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) + 1);
          bridge_list.Valuate(AIBridge.GetMaxSpeed);
          bridge_list.Sort(AIList.SORT_BY_VALUE, false);
          if (!AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridge_list.Begin(), path.GetTile(), par.GetTile())) {
            /* An error occured while building a bridge. TODO: handle it. */
          }
        }
      }
    }
  }
  path = par;
}

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

Note: do not use parent as variable name for GetParent, it's a keyword, giving peculiar results.

A sample AI

import("pathfinder.road", "RoadPathFinder", 3);

class SampleAI extends AIController {
}

function SampleAI::Start()
{
  /* Get a list of all towns on the map. */
  local townlist = AITownList();

  /* Sort the list by population, highest population first. */
  townlist.Valuate(AITown.GetPopulation);
  townlist.Sort(AIAbstractList.SORT_BY_VALUE, false);

  /* Pick the two towns with the highest population. */
  local townid_a = townlist.Begin();
  local townid_b = townlist.Next();

  /* Print the names of the towns we'll try to connect. */
  AILog.Info("Going to connect " + AITown.GetName(townid_a) + " to " + AITown.GetName(townid_b));

  /* Tell OpenTTD we want to build normal road (no tram tracks). */
  AIRoad.SetCurrentRoadType(AIRoad.ROADTYPE_ROAD);

  /* Create an instance of the pathfinder. */
  local pathfinder = RoadPathFinder();

  /* Set the cost for making a turn extreme high. */
  pathfinder.cost.turn = 5000;

  /* Give the source and goal tiles to the pathfinder. */
  pathfinder.InitializePath([AITown.GetLocation(townid_a)], [AITown.GetLocation(townid_b)]);

  /* Try to find a path. */
  local path = false;
  while (path == false) {
    path = pathfinder.FindPath(100);
    this.Sleep(1);
  }

  if (path == null) {
    /* No path was found. */
    AILog.Error("pathfinder.FindPath return null");
  }

  /* If a path was found, build a road over it. */
  while (path != null) {
    local par = path.GetParent();
    if (par != null) {
      local last_node = path.GetTile();
      if (AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) == 1 ) {
        if (!AIRoad.BuildRoad(path.GetTile(), par.GetTile())) {
          /* An error occured while building a piece of road. TODO: handle it. 
           * Note that is can also be the case that the road was already build. */
        }
      } else {
        /* Build a bridge or tunnel. */
        if (!AIBridge.IsBridgeTile(path.GetTile()) && !AITunnel.IsTunnelTile(path.GetTile())) {
          /* If it was a road tile, demolish it first. Do this to work around expended roadbits. */
          if (AIRoad.IsRoadTile(path.GetTile())) AITile.DemolishTile(path.GetTile());
          if (AITunnel.GetOtherTunnelEnd(path.GetTile()) == par.GetTile()) {
            if (!AITunnel.BuildTunnel(AIVehicle.VT_ROAD, path.GetTile())) {
              /* An error occured while building a tunnel. TODO: handle it. */
            }
          } else {
            local bridge_list = AIBridgeList_Length(AIMap.DistanceManhattan(path.GetTile(), par.GetTile()) + 1);
            bridge_list.Valuate(AIBridge.GetMaxSpeed);
            bridge_list.Sort(AIAbstractList.SORT_BY_VALUE, false);
            if (!AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridge_list.Begin(), path.GetTile(), par.GetTile())) {
              /* An error occured while building a bridge. TODO: handle it. */
            }
          }
        }
      }
    }
    path = par;
  }
  AILog.Info("Done");
}

Create an info.nut for this AI and give it a try. Play a bit with various cost, for example setting pathfinder.cost.no_existing_road = pathfinder.cost.max_cost. now the pathfinder will only find routes over already existing road. Not very useful if you want to build a new connection, but it can be nice if you want to check if a previously build connection is still OK.