Minecraft Piton Bolt Network Routing Problem (work in progress)
Different algorithms for connecting stations in a piston bolt network
With all the new development in piston bolt tech old servers might consider rebuilding their piston bolt network in the nether.
When you already know where the stations will be it is an interesting combinatorial optimization problem of how to connect all stations with piston bolts in a way that your system is both easy to build (has smallest total piston bolt length) and fast (has smallest average piston bolt travel time between any set of two stations). I was always sleeping at graph theory lectures, so I'm not saying that this is good stuff I coded in here.
Problem Domain
Generalizing and looking outside the Minecraft this problem comes down to finding an optimal interconnect for a given set of points (stations) on a Euclidean 2 dimentional plane. Minecraft restriction adds to this problem the fact that plane is actually a rectilinear lattice graph. So classical euclidean geometry is getting replaced. Graph itself will be weighted and undirected, since ether people always build bolts both ways, or maybe you managed to get falling end portal, thus allowing you to teleport back to spawn instantly. Weight of a vertex will be calculated using Chebyshev distance since it takes same amount of time to go 1 block ether diagonally or straight.
For all the calculations I will use coordinates of stations at Dugged SMP, but same can be applied to any.
1. Merging at coordinates.
First solution doesn’t go far from the existing system. All stations are connected to a single internal node (portal to main storage system in our case), in graph theory this is also called a star network. But it is optimized from what we currently have by going as much as possible diagonally before going straight. That way we shorten travel time (since diagonally we travel sqrt((20^2)+(20^2)) = 28.28 m/s instead of 20 m/s).
| Bolt count | 29 |
| Total bolt distance | 19.2 km |
| Total travel time | 16 min |
| Average travel time | 66.1 sec |
2. Merging at average coordinates.
Something that sounds like a good idea but is not.
| Bolt count | 29 |
| Total bolt distance | 19.6 km |
| Total travel time | 16.4 min |
| Average travel time | 67.7 sec |
3. All to All
Of course I had to try this, theoretically shortest amount of travel time - 16 sec less than previous results.
| Bolt count | 435 |
| Total bolt distance | 432 km |
| Total travel time | 360 min |
| Average travel time | 50 sec |
4. Nearest Neighbour (NN) algorithm
Heuristic solution to travelling salesman problem. This should find the shortest rout possible without additional stations (terminals) by going to each station only once. I tried starting from different stations and seems like our downaccel gold farm gives the shortest total bolt distance - 2 times less than what we currenly have. Sadly average travel time got 3 times more than what we currently have.
| Bolt count | 29 |
| Total bolt distance | 11.7 km |
| Total travel time | 9.8 min |
| Average travel time | 293 sec |
5. Loop
Small improvement to average travel time for NN algorithm we can do is to close the loop, this decreases travel time by 50%.
| Bolt count | 30 |
| Total bolt distance | 14.6 km |
| Total travel time | 12.2 min |
| Average travel time | 182.7 sec |
6. Rectilinear Steiner tree
Work in progress on a heuristic algorithm for constracting Stainer minimal tree
Getting started
Eh, it is not really user friendly, find Bolt_List.json and enter your stations by hand.
License
This program is licensed under the GNU General Public License v3.0. Please read the License file to know about the usage terms and conditions.