Roguelike Tutorial 12
Roguelike in Go - Part 12 (Monster Pathfinding)
All code for this tutorial can be found here.
It’s all well and good that we have monsters shivering when a player is in their LOS. It’s better to have them chase the player. Let’s make it so the monsters will chase the player as long as the player is in its Field of View.
To do this, we will use A Star pathfinding. It’s not the be-all end-all of pathing algorithms, but for our purposes, it will serve quite well. If you want to truly understand it, I’d recommend Red Blob Games again, as it’s a really good resource on understanding the algorithm.
One important requirement of the A* algorithm is a distance calculation between nodes. Since our map is grid based, and I’m not personally in favor of diagonal movement, let’s just use the Manhattan Taxicab Distance calculation. Remembering that Manhattan is one big grid, the calculation is simply the distance of the X values added to the distance of the Y values. You can’t get much more simple than that, and it serves our purposes perfectly because that’s how our critters will move.
Open up components.go and add this to your imports:
"math"
We need this to get an Absolute Value for our formula. We could just use min/max for the same, but I’d rather use the proper library function for the purpose. Now we need to add a function to our Position type:
func (p *Position) GetManhattanDistance(other *Position) int {
xDist := math.Abs(float64(p.X - other.X))
yDist := math.Abs(float64(p.Y - other.Y))
return int(xDist) + int(yDist)
}
This can help us with combat ranges also, so it’s going to be a very useful function. Mr Toppam Hat would be proud.
Next, create a new file and call it astar.go. I’ll assume by this point that you know how to set the package to main, so I’ll just let that go with a mention. From now on, we will just assume that you do this on all files.
A* works on Nodes. Let’s create a type to represent one. Note that we have no need of this type outside of our A* code, so we can keep this lowercase to limit its scope to this file:
//Node represents a given point on a map
//g is the total distance of the node from the start
//h is the estimated distance of the node from the ending
//f is the total value of the node (g + h)
type node struct {
Parent *node
Position *Position
g int
h int
f int
}
As per usual, let’s make a function to construct a node:
func newNode(parent *node, position *Position) *node {
n := node{}
n.Parent = parent
n.Position = position
n.g = 0
n.h = 0
n.f = 0
return &n
}
Lastly, an equality function will come in handy. For our purposes, if the positions are the same, the nodes are the same:
func (n *node) isEqual(other *node) bool {
return (n.Position.X == other.Position.X && n.Position.Y == other.Position.Y)
}
Now just for namespacing, lets create an empty type to hold our Algorithm. This will let us implement others in the future and use an interface for simple replacement.
//AStar implements the AStar Algorithm.
type AStar struct{}
Now let’s spend a while on the Algorithm itself:
//GetPath takes a level, the starting position and an ending position (the goal) and returns
//a list of Positions which is the path between the points.
func (as AStar) GetPath(level Level, start *Position, end *Position) []Position {
We are taking a level (to determine if the tile represented by the node is passable), a starting position (our Monster’s location for instance) and an ending position (the player’s location). We return a collection of positions leading the shortest path from the monster to the player.
Next, let’s just do some setup in the function:
gd := NewGameData()
openList := make([]*node, 0)
closedList := make([]*node, 0)
//Create our starting point
startNode := newNode(nil, start)
startNode.g = 0
startNode.h = 0
startNode.f = 0
//Create this node just for ease of dropping into our isEqual function to see if we are at the end
//May be worth a refactor of changing the isEqual to test on Position.
endNodePlaceholder := newNode(nil, end)
openList = append(openList, startNode)
We grab GameData because we will need to know the boundaries of our map (don’t want to path outside the world). We initialize the open and close lists. Create our start node (from the start position) and create a node for our ending node (for distance determinations and to see if any given node is the end of our path). Lastly, we bootstrap the whole thing by adding the startnode to our open list.
Here is where the fun begins. We start by looping through the Open list. If at any point it’s empty, we break the loop, because we have nothing more to look for.
for {
if len(openList) == 0 {
break
}
Now set the first node as the current node and iterate through the list. We are looking for he one with the smallest f value (as it’s the most promising):
//Get the current node
currentNode := openList[0]
currentIndex := 0
//Get the node with the smallest f value
for index, item := range openList {
if item.f < currentNode.f {
currentNode = item
currentIndex = index
}
}
Once we have the most promising node, move from the open list to the closed list:
//Move from open to closed list
openList = append(openList[:currentIndex], openList[currentIndex+1:]...)
closedList = append(closedList, currentNode)
Now we check our finish condition. If our current node is the end, we have the full path. We iterate through all the nodes by chaining along the Parent node until the Parent is nil. Once it’s nil, we have the starting position. Unfortunately, that means our path is reversed, starting at the end and ending at the start. To fix that, simply reverse the slice. Now return the path. If we got here, we are done. Remember that this is in a loop, so we will be checking this every iteration.
//Check to see if we reached our end
//If so, we are done here
if currentNode.isEqual(endNodePlaceholder) {
path := make([]Position, 0)
current := currentNode
for {
if current == nil {
break
}
path = append(path, *current.Position)
current = current.Parent
}
//Reverse the Path and Return it
reverseSlice(path)
return path
}
Right now, your IDE is complaining that reverseSlice does not exist. Let’s add that function above where we declared the type AStar. Note that reversing a slice is kind of a pain in Go. This is a useful function to remember.
func reverseSlice(data interface{}) {
value := reflect.ValueOf(data)
if value.Kind() != reflect.Slice {
panic(errors.New("data must be a slice type"))
}
valueLen := value.Len()
for i := 0; i <= int((valueLen-1)/2); i++ {
reverseIndex := valueLen - 1 - i
tmp := value.Index(reverseIndex).Interface()
value.Index(reverseIndex).Set(value.Index(i))
value.Index(i).Set(reflect.ValueOf(tmp))
}
}
Well all that did was cause your IDE to complain about reflect missing. Add this to your imports:
import (
"errors"
"reflect"
)
Now things should be a bit calmed down again.
So, at this point, we have checked the current node and it’s not our end node. So, we get all the edges of this node for our next iteration. Since our map is grid based, the edges are all tiles in each direction. Since we are only working with 4 directional movement, it’s Up, Down, Left and Right (ignoring diagonals). If you wish to include diagonal movement, you would include all 8 directions (and change the distance calculation to a euclidian one). start by creating a slice to hold our edges
edges := make([]*node, 0)
Now let’s check the UP edge:
if currentNode.Position.Y > 0 {
tile := level.Tiles[level.GetIndexFromXY(currentNode.Position.X, currentNode.Position.Y-1)]
if tile.TileType != WALL {
//The location is in the map bounds and is walkable
upNodePosition := Position{
X: currentNode.Position.X,
Y: currentNode.Position.Y - 1,
}
newNode := newNode(currentNode, &upNodePosition)
edges = append(edges, newNode)
}
}
First we make sure we aren’t about to check a node that would be off the map. Then we verify that the given node is actually walkable. For now, it’s whether or not it’s a WALL. We can make this much more interesting later on. If it’s traversable, and it’s on the map, we add it to our edges slice.
Do this again for each of the other directions:
if currentNode.Position.Y < gd.ScreenHeight {
tile := level.Tiles[level.GetIndexFromXY(currentNode.Position.X, currentNode.Position.Y+1)]
if tile.TileType != WALL {
//The location is in the map bounds and is walkable
downNodePosition := Position{
X: currentNode.Position.X,
Y: currentNode.Position.Y + 1,
}
newNode := newNode(currentNode, &downNodePosition)
edges = append(edges, newNode)
}
}
if currentNode.Position.X > 0 {
tile := level.Tiles[level.GetIndexFromXY(currentNode.Position.X-1, currentNode.Position.Y)]
if tile.TileType != WALL {
//The location is in the map bounds and is walkable
leftNodePosition := Position{
X: currentNode.Position.X - 1,
Y: currentNode.Position.Y,
}
newNode := newNode(currentNode, &leftNodePosition)
edges = append(edges, newNode)
}
}
if currentNode.Position.X < gd.ScreenWidth {
tile := level.Tiles[level.GetIndexFromXY(currentNode.Position.X+1, currentNode.Position.Y)]
if tile.TileType != WALL {
//The location is in the map bounds and is walkable
rightNodePosition := Position{
X: currentNode.Position.X + 1,
Y: currentNode.Position.Y,
}
newNode := newNode(currentNode, &rightNodePosition)
edges = append(edges, newNode)
}
}
This code just screams for a refactor, given how much common code just got copied. We will need to do a refactor soon, but I wanted to leave this as it is for ease of understanding for now.
To continue, we will need to add another function up where we placed the reverseSlice function.
func isInSlice(s []*node, target *node) bool {
for _, n := range s {
if n.isEqual(target) {
return true
}
}
return false
}
This will simply let us know if something exists within a slice of nodes. We will need this to check the openList and closedList for elements.
So, next we iterate through the edges and determine if they are to be added to the open list for the next iteration of the algorithm’s main loop:
//Now we iterate through the edges and put them in the open list.
for _, edge := range edges {
if isInSlice(closedList, edge) {
continue
}
edge.g = currentNode.g + 1
edge.h = edge.Position.GetManhattanDistance(endNodePlaceholder.Position)
edge.f = edge.g + edge.h
if isInSlice(openList, edge) {
//Loop through and check g values
isFurther := false
for _, n := range openList {
if edge.g > n.g {
isFurther = true
break
}
}
if isFurther {
continue
}
}
openList = append(openList, edge)
}
}
return nil
}
First we check to see if the edge is already in the closed list. If so, we ignore it and move on. If not, we calculate the value of the edge and store the g, h and f values. Next, check to see if the edge is in the open list. If so, we want to know if the current values from it are greater than the ones currently in. If that value is greater, we don’t need to process it at all and continue. If the value is lower, there is likely a better path to follow and we will be processing this edge. If it’s not in the open list at all, it needs to be processed potentially. In order to process it, it’s simply added to our openList.
Now that we have processed through each edge, we close our loop. If we somehow end up with an empty openList and no path was found, we simply return nil.
Ok, now we have implemented A* pathing. Let’s apply it. Open up monster_systems.go and look at UpdateMonster. Look for this:
if monsterSees.IsVisible(playerPosition.X, playerPosition.Y) {
log.Printf("%s shivers to its bones.", mon.Name)
}
and replace it with this:
if monsterSees.IsVisible(playerPosition.X, playerPosition.Y) {
astar := AStar{}
path := astar.GetPath(l, pos, &playerPosition)
if len(path) > 1 {
nextTile := l.Tiles[l.GetIndexFromXY(path[1].X, path[1].Y)]
if !nextTile.Blocked {
l.Tiles[l.GetIndexFromXY(pos.X, pos.Y)].Blocked = false
pos.X = path[1].X
pos.Y = path[1].Y
nextTile.Blocked = true
}
}
}
So, if the monster sees the player, we get the shortest path the monster can take to catch the player. Note that we are now blocking tiles that monsters are standing on. Players and Monsters should not be able to occupy a tile that another player or monster is currently occupying. That’s a serious violation of personal space. If there IS a path, and it’s greater than 1 (meaning the player isn’t right beside the monster already), the monster will move toward the player.
We need to make a few changes to the player too so that the player also blocks movement (so the monster can’t violate the player’s personal space either). We are an equal opportunity dungeon.
So, open up player_move_system.go and look for TryMovePlayer. Change:
if tile.Blocked != true {
pos.X += x
pos.Y += y
level.PlayerVisible.Compute(level, pos.X, pos.Y, 8)
}
To this:
if tile.Blocked != true {
level.Tiles[level.GetIndexFromXY(pos.X, pos.Y)].Blocked = false
pos.X += x
pos.Y += y
level.Tiles[index].Blocked = true
level.PlayerVisible.Compute(level, pos.X, pos.Y, 8)
}
Now whichever tile the player is standing on it blocked.
Just because, let’s make a null action for the player (basically a skip turn). We will put it in TryMovePlayer. At the top of the function add this:
turnTaken := false
Where we check key presses, add this block:
if ebiten.IsKeyPressed(ebiten.KeyQ) {
turnTaken = true
}
Now, at the bottom of the function, find this line:
if x != 0 || y != 0 {
and replace it with this:
if x != 0 || y != 0 || turnTaken {
Now hitting Q will let the game turns advance without requiring the player to move. This is not the ideal place to do such things, but I wanted to add it here so you can see the monsters move without having to move the player.
Now when you run it, the monsters approach the player. However, nothing stops the monsters and players from walking on top of one another. The update to the Blocked property of the tile didn’t work. You can check that for yourself in your debugger.
This is because we have been passing Level.Tiles by value. Until now, it’s been the most performant way to utilize it. However, if we need to change it, unless we just want to change a copy, we need to pass it by reference. This will require four small changes in level.go
First, find the Level type and change:
Tiles []MapTile
to this:
Tiles []*MapTile
Now we are using a reference, which means any changes we make will persist between calls. The other changes are all in the createTiles function. Change the function signature:
func (level *Level) createTiles() []MapTile {
to this:
func (level *Level) createTiles() []*MapTile {
So now it will return the pointer to the MapTile instead of a Tile struct itself. Find the following line in the function:
tiles := make([]MapTile, gd.ScreenHeight*gd.ScreenWidth)
and change it to this:
tiles := make([]*MapTile, gd.ScreenHeight*gd.ScreenWidth)
At this point, it should be obvious why we did that. Lastly, when adding a tile to the tiles slice, change this:
tiles[index] = tile
to this:
tiles[index] = &tile
Now run the application and the monsters and the player respect each other’s space.
So…that was quite a lot.
As always, if you have any questions, feel free to ask me at fatoldyeti@gmail.com or @idiotcoder on the gophers slack. Also, feel free to join my discord and ask there. The link to join is the telephone button on the top right of the page.