Using R and the A* Algorithm: Cruising Around Minecraft

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.

• miner package
  • R programming with minecraft manual
• machow/astar-r
  • minecraft example directory

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).