This is an updated web version of an old project of mine. With all the new development in piston bolt tech old servers might consider rebuilding their piston bolt network in the nether. Thus, a good question arise, what is the right way to do it?
When you already know where the stations will be, it comes down to multi-objective optimization problem of how to connect all stations with piston bolts in a way that will minimize both total piston bolt length and the average piston bolt travel time between any set of two stations. This means that the solution lies somewhere on the Pareto frontier.
Piston bolt network of Dugged
Problem domain
Star graph
Complete graph
Minimum spanning tree (MST)
Steiner tree
Distance matrix heatmap
Pareto front
How to use
Generalizing and looking outside the Minecraft, this problem comes down to finding an optimal interconnect for a given set of vertices (stations) on a 2 dimensional Chebyshev metric space. The solution to the problem is a weighted directed/undirected graph. Weight will be Chebyshev distance between vertices (stations) and directionality would come down to the fact that the graph has loops or not. For example, [Hamiltonian path] can be directed, since in theory a player can get to any station from any station just by traveling in one direction.
Star graph is a type of tree graph with one internal node and k leaves. You can place the internal node at any arbitrary location, however median or average coordinates of all stations work the best.
Complete graph is an undirected graph in which every pair of distinct vertices is connected by a unique edge. This gives theoretically shortest amount of average travel time.
MST is a subset of the edges of a connected, weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
NN is a quick approximation to finding out true MST. The graph this algorithm produces is directed and weighted. Worth mentioning that in the given set of points there are intersections between edges. My implementation is missing one optimization, when detecting line intersections -> switch end points of intersecting lines to get a new, smaller graph.
Hamiltonian path is a loop graph that visits each vertex exactly once.
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.
Kruskal's algorithm finds MST of an undirected edge-weighted graph.
Steiner tree problem consists of finding the minimum tree that includes specific points and, if necessary, uses a number of auxiliary points to minimize the tree length (unlike MST). This problem is NP-hard, however heuristic solution exists.
To calculate average travel time in a given network I use Floyd-Warshall algorithm that generates this matrix of shortest path between any set of points.
To choose a network that best suits your needs, there is a page with scatter plot and Pareto front.
This section is work in progress.
Example network JSON:
{
"stations": [
{
"name": "Station A",
"description": "This is station A",
"colour": "#f2a788",
"x": 0,
"z": 0
},
{
"name": "Station B",
"description": "This is station B",
"colour": "#f2a788",
"x": 10,
"z": 30
}
],
"bolts": [
{
"directed": false,
"station_a": {
"name": "Station A",
"x": 0,
"z": 0
},
"turn": {
"x": 10,
"z": 10
},
"station_b": {
"name": "Station B",
"x": 10,
"z": 30
},
"length": 30,
"colour": "#8f7f10"
}
]
}This program is licensed under the MIT License. Please read the License file to know about the usage terms and conditions.