A picture of a crow

Frederick's Perch

The Traveling Minecraft Player Problem


You can scan a Minecraft world for diamonds and use GRASS’s v.net.salesman to plot an efficient route to get all of them.


In April I published my paper, Visualizing Player Engagement with Virtual Spaces using GIS in SIGBOVIK 2020 (it’s on page 273), where I analyzed Minecraft worlds in GIS software. In there, I mention possibly finding an efficient route to get to a bunch of command blocks (I called this the “Traveling Minecraft Player Problem”) with GRASS GIS’s v.net.salesman. At the time, I couldn’t figure out how to do it since it requires a network layer (normally a street map for real world purposes) and I didn’t have one. After months of not thinking about it, I was in the shower one day and realized all I need is a grid, since all of the blocks in a Minecraft world is nicely aligned to one.

Here, instead of plotting command blocks, I’m going to plot diamond ore. I go over how block plotting works in my paper, but basically I run ore_plot_qgis.py from the QGIS Python console and point to the .mca region file I want to look at. This puts a new layer into the QGIS project with locations of all the diamonds generated so far in the region.

Preparing for the Salesman

Changing the filename under “Region Information” in Dinnerbone’s Coordinate Tools to the region you’re analyzing will give you the extent of the grid you need to make with QGIS’s Vector creation > Create grid tool in the Processing Toolbox. The spacing, naturally, is 1 block (which gets represented as Degrees for me). Then you have to use Vector overlay > Split with lines with the grid as both the input and the split layer, which will cut up the grid into all its constituent line segments. This new split layer is the network you’ll use with v.net.salesman, and the point layer with the ores in it will be the centers point layer.


A pseudocolor map of the Minecraft region's heightmap, with a quickest route through all the diamonds plotted on top

v.net.salesman spits out the most efficient loop through all of the diamonds as it can find. Since the Traveling Minecraft Player Problem is NP-Hard and the algorithm is heuristic, the solution is not necessarily the most efficient route possible. It’s good enough though, especially for a Minecraft player who would otherwise be blindly searching for diamonds themselves. I’ve plotted the route for a test region and clustered contiguous veins of diamonds above, so veins with more diamonds have bigger numbers. Unfortunately since I can’t give v.net.salesman elevation data, it doesn’t take that into account. The attribute table for the ore plot generated by ore_plot_qgis.py does have elevation data, though.

Pairing with ComputerCraft

If you’re so inclined, you can use this data with ComputerCraft, which I love and have written about before. You can use Vector geometry > Extract vertices to extract vertices on the path and export it to GeoJSON. Then you can get elevation references for the diamonds by exporting the ore layer. Then you stick all the coordinates into a mining turtle and tell it to mine up the diamonds. This is left as an exercise for the reader, or if I end up doing it on my next ComputerCraft playthrough.