Using Dijkstra's Algorithm for Battlesnake

Intro

By the end of this tutorial you will have a simple Battlesnake who will use Dijkstra's Algorithm to find the shortest path to food. This tutorial is intended to be a second-step for a dev beginning to create their snake, after they have followed Battlesnake's initial tutorials.

Setup

I used the TypeScript Starter Project to make my snake.

git clone git@github.com:BattlesnakeOfficial/starter-snake-typescript.git battlesnake
cd battlesnake

I used dijkstrajs npm package package to do the pathfinding.

npm install dijkstrajs

And for typescript to allow this we add a file:

echo "declare module 'dijkstrajs';" >> src/dijkstra.d.ts

Grid.js

Create a class to hold our grid data. The constructor will take the game data provided by the Battlesnake server and use it to set up the nodes and edges of the grid.

In summary, every node will have an edge to each of the four adjacent tiles. Then, we'll change the weight of hazard tiles. Lastly, we'll crank up the weight of edges that have a snake in them.

Then we create a findPath function to

/// <reference path='./dijkstra.d.ts' />
import { InfoResponse, GameState, Game, Board, Battlesnake, MoveResponse, Coord, Graph, Edges } from "./types"
import * as dijkstra from 'dijkstrajs'

export default class Grid {
    game: Game
    graph: Graph
    board: Board
    you: Battlesnake

    constructor(gameState: GameState) {
        this.game = gameState.game
        this.graph = {}
        this.board = gameState.board
        this.you = gameState.you
        this.buildGrid()
    }

    buildGrid(): void {
        // Initial variables
        this.graph = {}
        const graph = this.graph
        const boardWidth = this.board.width
        const boardHeight = this.board.height

        // For every tile in the board, set the default weight of every edge
        for (let y = 0; y < boardHeight; y++) {
            for (let x = 0; x < boardWidth; x++) {
                const key = this.keyName({x, y})
                const edges: Edges = {}
                if (x > 0) edges[`${x-1},${y}`] = boardWidth - x + 10 // to the left
                if (x < boardWidth - 1) edges[`${x+1},${y}`] = x + 10 // to the right
                if (y > 0) edges[`${x},${y-1}`] = boardHeight - y + 10
                if (y < boardHeight - 1) edges[`${x},${y+1}`] = y + 10
                graph[key] = edges
            }
        }

        // Increase the weight of edges to Hazard tiles
       const hazardDamagePerTurn = this.game.ruleset.settings.hazardDamagePerTurn
        this.board.hazards.forEach((hazard) => {
            this.setAllEdges(hazard, hazardDamagePerTurn * 10)
        })

        // Increase the weight of edges to other snake bodies
        this.board.snakes.forEach((snake) => {
            // If the snake's gonna die this turn, ignore it
            if (
                snake.id !== this.you.id
                && snake.health === 1
                && !this.board.food.some((food) => this.findDistance(snake.head, food) === 1)
            ) {
                return
            }
            snake.body.forEach((coord, i) => {
                const distance = this.findDistance(snake.head, coord)
                if (distance >= (snake.length - i)) return // It's gonna be gone then
                // There's a miniscule chance that the snake might run out of health or
                // Move out of bounds and be removed before our move resolves
                // So it's better to move into another snake than into a wall.
                const weight = (snake.id === this.you.id) ? -1 : 1000000 + snake.health
                this.setAllEdges(coord, weight)
            })
        })
        this.graph = graph
    }

    /*
        Uniformly name the key based on its coordinate
    */
    keyName(coord: Coord): string {
        return `${coord.x},${coord.y}`
    }

    /*
        Get all the adjacent keys of a coordinate
    */
    adjKeys(coord: Coord): Coord[] {
        const boardWidth = this.board.width
        const boardHeight = this.board.height
        return [
            { x: coord.x, y: coord.y + 1 },
            { x: coord.x, y: coord.y - 1 },
            { x: coord.x + 1, y: coord.y },
            { x: coord.x - 1, y: coord.y }
        ]
    }

    /*
        Set all the edges going to a key
    */
    setAllEdges(coord: Coord, value: number) {
        const graph = this.graph
        const adjCoords = this.adjKeys(coord)
        const coordKey = this.keyName(coord)
        adjCoords.forEach((adjCoord) => {
            const adjKey = this.keyName(adjCoord)
            if (graph[adjKey] && graph[adjKey][coordKey]) {
                const edges = graph[adjKey]
                if (!edges[coordKey]) return
                if (value === -1) delete edges[coordKey]
                else edges[coordKey] = value
            }
        })
    }

    findPath(start: Coord, coord: Coord) {
        return dijkstra.find_path(this.graph, this.keyName(this.start), this.keyName(coord))
    }

    findDistance(start: Coord, coord: Coord) {
        return dijkstra.find_path(this.graph, this.keyName(start), this.keyName(coord)).length - 1
    }
}

Using the Grid class

import Grid from './grid'

/* ... */

// The function that handles the POST /move route
function move(gameState: GameState): MoveResponse {
    const myHead = gameState.you.head
    const response: MoveResponse = {
        move: 'up' // We'll change this by the end
    }
    const grid = new Grid(gameState, myHead)
    let chosenPath: string[] = []
    // Find the closest food
    gameState.board.food.forEach((food) => {
        try {
            const path = grid.findPath(myHead, food)
            if (!chosenPath.length || path.length < chosenPath.length) {
                chosenPath = path
            }
        } catch (error) {
            // console.log(`${gameState.game.id} ${gameState.you.id} no path to food`)
        }
    })
    // Move to my own tail otherwise
    if (!chosenPath.length) {
        try {
            const path = grid.findPath(myHead, gameState.you.body[gameState.you.length-1])
            if (path.length > 1) { // Gotta have space
                // TODO: Make sure we don't hit our tail right after eating
                chosenPath = path
            }
        } catch (error) {
            // console.log(`${gameState.game.id} ${gameState.you.id} no path to my tail`)
        }
    }
    if (chosenPath.length > 1) {
        const direction = getDirection(myHead, chosenPath[1], gameState)
        response.move = direction
    }
    return response
}

/*
    Gets a direction string from the coordinate we receive from dijkstra's function
*/
function getDirection(start: Coord, key: string): string | undefined {
    const [keyX, keyY] = key.split(',')
    const end: Coord = {x: parseInt(keyX), y: parseInt(keyY)}
    if (start.x === end.x) {
        // same row
        if (start.y + 1 === end.y) return 'up'
        if (start.y - 1 === end.y) return 'down'
    }
    if (start.y === end.y) {
        // same column
        if (start.x + 1 === end.x) return 'right'
        if (start.x - 1 === end.x) return 'left'
    }
}

Wrapped Mode

For the 2022 season Battlesnake introduced Wrapped mode. It wouldn't take too much work to get this grid to have wrapped edges, you would just need to detect when you were at a border node and create an edge pointing to the other side.

Final Thoughts

This is set up to tell us the path that is the lowest health cost to get to food, which might not necessarily be the shortest path. If you wanted your snake to make decisions based on the fewest number of turns, you could set up a second graph where every edge has a cost of 1.