# Using Dijkstra's Algorithm for Battlesnake

February 05, 2022  ## 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

grid.ts
``````/// <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) => {
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
*/
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 coordKey = this.keyName(coord)
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

logic.ts
``````import Grid from './grid'

/* ... */

// The function that handles the POST /move route
function move(gameState: GameState): MoveResponse {
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 {
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 {
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, 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.