Using R and the A* Algorithm: Cruising Around Minecraft

March 18, 2019 by Michael Chow

(This article is the last in a series on using the A* algorithm in R. See the first and second posts for more.)

Last year at the NYC R conference, I had the chance to see David Smith demonstrate building and navigating a Minecraft maze, using the miner package. It was really cool! At the end of the talk, as we stepped out of the maze, my gaze turned to the lofty minecraft peaks in the distance.

I knew then that my heart belonged to finding the optimal path up one of those craggy slopes.

Navigating minecraft involves two pieces:

  1. Using the miner library to interact with minecraft
  2. Using the astar library to navigate a 3D space

In this article, I’ll quickly cover what went into the process.

Cruising Around Minecraft

Below is a video of A* trying to navigate to the peak of a mountain.

One potentially frustrating part in the video is that the algorithm searches so close to the goal, but then keeps on searching, rather than taking the few steps it would need to connect to the the endpoint. Why does it do this?

The reason is that it’s not just looking for a path to the goal, but the best path, so it spends a lot of rounds going back and looking to avoid the dip at the end.

If you’re interested, you can take a look at the code for the video above. In the following sections I’ll go over the basics of how it used the astar and miner packages, and how it was extended it to 3D.

Slinging Blocks in Minecraft with the miner Library

In order to make the 3D version easier to get into, I’ll go through the main functions needed to lay blocks in minecraft, using a 2D maze as an example.

Below, we define a simple maze (similar to the last post).

library(astar)

M <- matrix(ncol = 4, byrow = TRUE, c(
  0,0,1,0,
  0,0,1,0,
  1,0,1,0,
  0,0,0,0)
  )

# Get path from top left to top right
maze <- SearchMaze2D$new(M)
path <- maze$run(c(1,1), c(1,4))

Then, we draw it in Minecraft. The miner function used her are setBlock, and setBlocks, which let you put blocks of any material down. While the matrix above lets you get blocks indexing like M[row,col], setBlock (and Minecraft) is reversed…

setBlock(col, height, row, block_id)

library(miner)
mc_connect()

# Make a nice frame around maze in minecraft
setBlocks(0, 0, 0, nrow(M) + 1, 0, ncol(M) + 1, 2)
setBlocks(1, 0, 1, nrow(M), 0, ncol(M), 0)

# Lay out maze
for (ii in 1:nrow(M)) {
  for (jj in 1:ncol(M)) {
    # middle arg is height, last arg is block id
    # 0 is air, 1 is stone
    setBlock(jj, 0, ii, M[ii,jj])
  }
}

# Show path through maze
for (xy in path) {
  # set path to be a red wool block
  setBlock(xy[2], 0, xy[1], 35, 14)
}

And there you have it! For more on how to set up minecraft, and run miner, see the R programming with Minecraft book.

Taking it to 3D

In order to extend the approach to 3D, I needed to..

  • Require candidate blocks to have 2 blocks of air above them.
  • Account for navigating up or down.
  • Pull in existing terrain using miner::getBlocks.

Overall, one of the biggest challenges for me was the difference in how minecraft represents coordinates. I found myself spending a lot of time reorienting the player in game, and laying down things flipped around.

In the example script, I also put an example for building and navigating a custom maze.

Summary

In this post, I went over the basics of using A* to navigate in minecraft. If you’re interested in trying it for yourself, check out the following links.

In the off-chance that you develop any elaborate 3D mazes to navigate in minecraft, I would love to see, or am happy to run the algorithm through them! (let me know on the astar repo or on twitter @chowthedog).

© 2017 | Follow on Twitter | Hucore theme & Hugo