- Openttd cargodist code#
- Openttd cargodist free#
It is also relatively cheap to compute and looks pretty enough to use. This graph contains the minimal spanning tree which is useful because it shows that everything can be reached from any point. To actually generate a network we can use an algorithm to create a Relative Neighborhood Graph. This results in a list of points that are used in the network. Figure out what the optimal packing is with the greedy algorithm.Give all places a weight 1 / cost where existing shores are cheap and islands that have to be built are expensive.Remove all points that are within 2 * min_radius distance from a dock placed in the Dock Placement step.Generate all places where we can place a dock and all places where we can make an island to place a dock.We can do this using the same solution we used for placement as this is again a Set Packing problem: 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. They require frequent service which means that the distance between endpoints should be relatively short. Ships in 1750 have the unfortunate property of being very unreliable. Connecting the Networkĭue to our decision to work well on cargodist we want the network to be fully connected. 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. Unfortunately this is an NP-complete problem called Weighted Set Packing. 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. 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.
Openttd cargodist code#
The source code for this algorithm is available online.
Replace the set of lakes on the previous row with the set of lakes on the current row. Go back to 1 until you're at the end of the row. Add the lake to the set of lakes on the current row. If we found no neighbors, create a new lake. If we found multiple neighbors, merge them all into one new lake and remove the other ones. If we found only one neighbor, add this strip to the lake we found on the previous strip. See if the strip of water we encountered lies adjacent to any of the strips we found in the previous row. Start iterating, once you find a water tile, keep iterating until you find land again. Initialize an empty set of lakes on the current row. Initialize an empty set of found lakes. Initialize an empty set of lakes on the previous row. Specifically, I'm using the trick to keep sets that indicate reachability of the line before the one we're processing: 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. 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. In order to find the biggest lake on the map I first have to figure out how many lakes there actually are. In my case I want to start with fully building out one network on the largest lake on the map. It only allows computations using integers which makes certain things slightly harder.Ĭargodist encourages building bigger networks. I'll have to build this in Squirrel which is a slightly quirky language very similar to javascript and lua. Therefore my focus will be on making profit using boats. Horse carriages have a very low capacity, which results in a very small profit margin. I want to start in 1750, and the only two options of transport are either horse carriages or sailing ships. Should be fast enough to use on a 4096x4096 map. Play well with the Sailing Ships NewGRF and starting date in 1750. Goalsįor this AI I've picked a few things I want it to be able to do: This post (and any that may follow) will explain my goals and how I've approached solving them. Specifically I've been trying to make an AI. Openttd cargodist free#
To free this time I've been trying to automate me playing it. OpenTTD is a very interesting game which I've been spending too much time in lately.
0 kommentar(er)
