This post is the second part of a series on using the A* algorithm in R.
- manually define a maze and plot it with ggplot
- use an example class from the astar library to navigate it
- add a bonus picture of a gnome to the maze
- use a single line of gganimate to animate the A* search
Drawing the maze
First, we’ll load in the necessary libraries, and create a simple maze to navigate.
# Create maze # remotes::install_github("machow/astar-r") library(astar) library(gganimate) library(dplyr) M <- matrix(ncol = 8, byrow = TRUE, c( 0,0,0,0,0,0,1,0, 0,0,1,1,0,1,1,0, 1,0,0,0,0,0,1,0, 0,0,1,1,1,1,1,0, 1,0,1,0,0,0,0,0, 0,0,0,0,1,1,0,0 ))
Note that this task is pretty straightforward.
The one important piece that makes it easy to read is setting
byrow = TRUE.
Otherwise, it will appear rotated 90 degrees.
Below, I make a quick plot of the maze, by creating a data.frame where each row is the coordinate of a piece of wall.
walls <- which(M == 1, arr.ind = TRUE) %>% as.data.frame() %>% transmute(y = row, x = col) walls %>% ggplot(aes(x,y)) + geom_tile(width = 1, height = 1, fill = "#623B17") + scale_y_reverse() + scale_x_continuous(breaks = seq(0, 8, 1), limits = c(0, 8.5), minor_breaks = NULL)
Note that the plot uses
scale_y_reverse, to take care of the fact that a matrix uses a y index that counts down (e.g. walls[1,] is the top row), but
ggplot’s y index counts up.
Navigating through and saving our path
Once the maze is defined, we can use the MazeGazer R6 class to run through it. This class keeps a history of all the spots that the A* algorithm searched from, so we can visualize them later.
# Run maze mg <- MazeGazer$new(M) goal_path <- mg$run(c(1,1), c(1,8)) history <- mg$history %>% bind_rows() head(history)
## round y x ## 1 1 1 1 ## 2 2 1 1 ## 3 2 1 2 ## 4 3 1 1 ## 5 3 1 2 ## 6 3 1 3
Note that the astar library has a base class called AStar, that you can use as a template (or subclass) when writing your own tools.
Loading up the infer gnome
Probably the most critical step of the process is loading in the infer gnome hex sticker. Without this sticker, there would be no incentive to get to the end of the maze.
library(png) library(grid) # download to computer gnome <- "https://github.com/tidymodels/infer/raw/master/figs/infer_gnome.png" download.file(gnome, "./gnome.png") # load that gnome up! img <- readPNG("./gnome.png") g <- rasterGrob(img, interpolate=TRUE)
With gnome in hand, we’re ready to chart our course through the maze.
Making the run!
Below is the code to animate the trip through the maze. Notice that it only needs a single line of gganimate!
ggplot(history, aes(x, y)) + # ggplot maze part geom_tile(width = 1, height = 1, fill = "#623B17", data = walls) + geom_point(aes(group = round)) + scale_y_reverse(breaks = seq(6, 0, -1), limits = c(6, 0), minor_breaks = NULL) + scale_x_continuous(breaks = seq(0, 100, 1), limits = c(0, 9.5), minor_breaks = NULL) + coord_fixed() + # ggplot gnome part annotation_custom(g, xmin = 7.30, xmax = 8.70, ymin = -.3, ymax = -1.70) + # gganimate transition_time(round)
Overall, I was amazed that gganimate is so easy to get into, and did its job in a single line of code! To be sure, it took more lines of code to load the gnome hex sticker than to use gganimate. I’d be curious to know how large the maze (and the history log) can get before making the plot takes too long. I’m also curious if there’s a way with gganimate to only specify the dots we want to add or take away after each round, rather than logging the full path.
If you use the astar package solve any interesting problems, or encounter any bugs, let me know on github! If you have strong opinions on gnomes feel free to share them with me on twitter (\@chowthedog).