category

Building an OpenTTD AI (part 1) 2019-09-05 link

OpenTTD is a very interesting game which I've been spending too much time in lately. To free this time I've been trying to automate me playing it. Specifically I've been trying to make an AI. This post (and any that may follow) will explain my goals and how I've approached solving them.

Goals

For this AI I've picked a few things I want it to be able to do:

  • Play well with the Sailing Ships NewGRF and starting date in 1750.
  • Should be fast enough to use on a 4096x4096 map.
  • Make realistically looking networks.
  • Work well with cargodist enabled.
  • Be profitable.
  • Be fun to write.
  • Work on the temperate climate.

Consequences

I want to start in 1750, and the only two options of transport are either horse carriages or sailing ships. Horse carriages have a very low capacity, which results in a very small profit margin. Therefore my focus will be on making profit using boats.

I'll have to build this in Squirrel which is a slightly quirky language very similar to javascript and lua. It only allows computations using integers which makes certain things slightly harder.

Cargodist encourages building bigger networks. In my case I want to start with fully building out one network on the largest lake on the map.

Lake Detection

In order to find the biggest lake on the map I first have to figure out how many lakes there actually are. Because you can usually only execute 10.000 * 74 operations every game day and we could be dealing with a map of 4096 * 4096 = 16777216 tiles big, this has to be done in one pass.

The approach I'm using is based on Eller's Algorithm which is a very cool algorithm to generate mazes of arbitrary size in linear time one row at a time. Specifically, I'm using the trick to keep sets that indicate reachability of the line before the one we're processing:

  • Initialize an empty set of lakes on the previous row.
  • Initialize an empty set of found lakes.
  • For each row on the map:
    1. Initialize an empty set of lakes on the current row.
    2. Start iterating, once you find a water tile, keep iterating until you find land again.
    3. See if the strip of water we encountered lies adjacent to any of the strips we found in the previous row.
    4. If we found only one neighbor, add this strip to the lake we found on the previous strip.
    5. If we found multiple neighbors, merge them all into one new lake and remove the other ones.
    6. If we found no neighbors, create a new lake.
    7. Add the lake to the set of lakes on the current row.
    8. Go back to 1 until you're at the end of the row
    9. Replace the set of lakes on the previous row with the set of lakes on the current row.

The source code for this algorithm is available online.

Dock Placement

Once we have a list of lakes we pick the biggest one and make a list of all possible locations where we can place a dock. For these locations we can figure out what resources can be served from there.We don't want to have overlapping docks though and we want to pick the dock locations that give us the most possibilities. Unfortunately this is an NP-complete problem called Weighted Set Packing. There is however a greedy approach where you weight all docks on (number of cargo types served) / sqrt(number of other docks it blocks), and keep picking the highest one and discarding the ones it blocks.

Connecting the Network

Due to our decision to work well on cargodist we want the network to be fully connected. Ships in 1750 have the unfortunate property of being very unreliable. They require frequent service which means that the distance between endpoints should be relatively short. Because our interesting docks could be pretty distant from each other we have to place transshipment docks where cargo can be transferred to other ships.

We can do this using the same solution we used for placement as this is again a Set Packing problem:

  • Generate all places where we can place a dock and all places where we can make an island to place a dock
  • Remove all points that are within 2 * min_radius distance from a dock placed in the Dock Placement step.
  • Give all places a weight 1 / cost where existing shores are cheap and islands that have to be built are expensive.
  • Figure out what the optimal packing is with the greedy algorithm.

This results in a list of points that are used in the network. To actually generate a network we can use an algorithm to create a Relative Neighborhood Graph. This graph contains the minimal spanning tree which is useful because it shows that everything can be reached from any point. It is also relatively cheap to compute and looks pretty enough to use.

Now all that is needed is figuring out in which order we want to build out the network.