# Building a Game With TypeScript. Pathfinding and Movement 4/7. Pathfinder

Chapter VI in the series of tutorials on how to build a game from scratch with TypeScript and native browser APIs Navigation vector created by pch.vector - www.freepik.com

Hey there and welcome back! The time has come for us to build our own Pathfinder. In the last post, we prepared utilities that will help us. Today we're jumping into the algorithms themselves.

Just a reminder, I am not going to spend time explaining details of neither Breadth-First search, not A*. The Internet is full of amazing content that goes into every single detail of these widely used techniques. I am going to focus on implementation only.

In Chapter VI “Pathfinding and Movement ”, we finally make our Ships alive! You can find other Chapters of this series here:

Feel free to switch to the `movement-pathfinding-3` branch of the repository. It contains the working result of the previous posts and is a great starting point for this one.

1. Introduction
3. Accounting for cost
5. Conclusion

We start by introducing The `pathfinder` class. It is constructed for a specific graph and has only one public method: `CalculatePath`:

``````// src/pathfinder/pathfinder.ts
import { IGraph, IGraphNode } from '@/utils'

export class Pathfinder {

public CalculatePath(from: IGraphNode, to: IGraphNode): IGraphNode[]{
const path: IGraphNode[] = []

return path
}
}
``````

Simple enough! We construct our Pathfinder with `IGraph` and then return (so far empty) an array of `IGraphNodes` from the public `CalculatePath` method.

Out first cut of the pathfinder will be a simple BFS. We'll drop it into a private method to keep our code slightly cleaner:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
// ... //
private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
const cameFrom: Record<string, IGraphNode | null> = {
[start.Position.AsString()]: null
}

return cameFrom

}
}
``````

This method returns a dictionary with keys of Node's position and values of either `IGraphNode` or `null`. Note, that I am making usage of the native TypeScript `Record` type which behaves as a dictionary in our case.

Let's start with a basic BFS implementation. I'll define "frontier", add `start` as a first item of it, and iterate over every neighbor until we reach the end:

``````// src/pathfinder/pathfinder.ts
import { IGraph, IGraphNode, PriorityQueue } from '@/utils' // <--- CHANGE
// ... //
export class Pathfinder {
// ... //
private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
const cameFrom: Record<string, IGraphNode | null> = {
[start.Position.AsString()]: null
}
const frontier = new PriorityQueue<IGraphNode>()

frontier.Enqueue(start, 0)

while (!frontier.IsEmpty) {
const current = frontier.Dequeue()

for (const next of this._graph.GetNeighborsOf(current)) {
const nextStr = next.Position.AsString()
if (typeof cameFrom[nextStr] === 'undefined') {
const priority = 0
frontier.Enqueue(next, priority)
cameFrom[nextStr] = current
}
}
}

return cameFrom
}
}
``````

If you need a refresher on what is going on here, please refer to this resource. Note that we have to explicitly compare `cameFrom[nextStr]`to `undefined` because it can be `null` and standard check `!cameFrom[nextStr]` would be insufficient.

Now, having a dictionary of `cameFrom` we can reconstruct the actual path:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
// ... //
public CalculatePath(from: IGraphNode, to: IGraphNode): IGraphNode[]{
const path: IGraphNode[] = []

let current: IGraphNode | null = to
const cameFrom = this.GetCameFrom(from, to)

while (current && current !== from){
path.push(current)
current = cameFrom[current.Position.AsString()]
}

path.reverse()

return path
}

}
``````

Let's also add a barrel file so we won't forget to do it:

``````// src/pathfinder/index.ts
export * from './pathfinder'
``````

And that is the very basic pathfinder! Before we start improving it, let's add some tests first

## Testing Pathfinder

The test we want to conduct sounds easy on the surface: we want to make sure `Pathfinder` can calculate a path from point A to point B:

``````// src/pathfinder/pathfinder.spec.ts
describe('>>> Pathfinder', () => {
it('should calculate path from point A to point B', () => {  })
})
``````

To do that, our `Pathfinder` needs a Graph, which in turn relies on `IGraphNode`. Lets mock them:

``````// src/pathfinder/pathfinder.spec.ts
import { IGraph, Vector2D, IGraphNode } from '@/utils' // <--- ADD

describe('>>> Pathfinder', () => {
class GraphNode implements IGraphNode {
public get Position(): Vector2D {
return this._position
}

}

class Graph implements IGraph {
constructor(private readonly _edges: Record<string, GraphNode[] | null>) {}

public GetCost(a: IGraphNode, b: IGraphNode): number {
return 1
}

public GetNeighborsOf(node: GraphNode): GraphNode[] {
const neighbors = this._edges[node.Position.AsString()]
if (!neighbors) {
throw new Error('No neighbors')
}

return neighbors
}
}

it('should calculate path from point A to point B', () => {  })
})

``````

`GraphNode` implements `IGraphNode` and has to support `Position`. I will keep it simple and just supply position in the constructor.

Similarly, `Graph` implements `IGraph` and we will provide all "edges" in the constructor. I made `GetCost` return 1 for now and `GetNeighborsOf` simply attempts to find all neighbors of the provided node taking edges as a source of truth.

Now we are going to construct a 3x3 "grid" of nodes, similar to the one we have in the actual game. Each node is an instance of `GraphNode` and the grid itself will be represented by `Graph`.

First node will have the Position `(0, 0)`, second: `(1, 0)` and third `(2, 0)`. Together, they form the first "row" of our grid:

``````//  mantal map
(0, 0) | (1, 0) | (2, 0)

-----------------------

(0, 1) | (1, 1) | (2, 1)

-----------------------

(0, 2) | (1, 2) | (2, 2)

``````

Similarly, nodes with position `(0, 1)` , `(1, 1)` and `(2, 1)` form 2nd row, etc. I'll name variables to hint what their position is: `node01` has position `(0,1)`, `node22` has position `(2,2)` and so on

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
class Graph implements IGraph {
// ... //
}
// first row
const node00 = new GraphNode(new Vector2D(0, 0))
const node10 = new GraphNode(new Vector2D(1, 0))
const node20 = new GraphNode(new Vector2D(2, 0))

// second row
const node01 = new GraphNode(new Vector2D(0, 1))
const node11 = new GraphNode(new Vector2D(1, 1))
const node21 = new GraphNode(new Vector2D(2, 1))

// third row
const node02 = new GraphNode(new Vector2D(0, 2))
const node12 = new GraphNode(new Vector2D(1, 2))
const node22 = new GraphNode(new Vector2D(2, 2))

it('should calculate path from point A to point B', () => {  })
})
``````

And now we can define "edges". These are simply dictionaries with the key being a string representation of the position of each node and the value being an array of all neighbors of that node :

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
const node22 = new GraphNode(new Vector2D(2, 2))

const edges = {
[node00.Position.AsString()]: [node10, node01],
[node10.Position.AsString()]: [node00, node20, node11],
[node20.Position.AsString()]: [node10, node21],

[node01.Position.AsString()]: [node00, node11, node02],
[node11.Position.AsString()]: [node10, node01, node21, node12],
[node21.Position.AsString()]: [node20, node11, node22],

[node02.Position.AsString()]: [node01, node12],
[node12.Position.AsString()]: [node02, node11, node22],
[node22.Position.AsString()]: [node21, node12],
}

it('should calculate path from point A to point B', () => {  })
})
``````

This gives us the opportunity to define a `Graph` and feed it to `Pathfinder`:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
import { Pathfinder } from './pathfinder' // <--- ADD

describe('>>> Pathfinder', () => {
// ... //
const graph = new Graph(edges) // <--- ADD
const pathfinder = new Pathfinder(graph) // <--- ADD

it('should calculate path from point A to point B', () => {  })
})
``````

Now the test itself. Assuming we're looking to find a path between (0, 0) and (2, 2), what can it be?

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
it('should calculate path from point A to point B', () => {
expect(pathfinder.CalculatePath(node00, node22)).toStrictEqual([

])
})
})
``````

Let's take a look at our little grid again:

``````//  mantal map

(0, 0) | (1, 0) | (2, 0)

-----------------------

(0, 1) | (1, 1) | (2, 1)

-----------------------

(0, 2) | (1, 2) | (2, 2)

``````

There are few ways we can get from (0, 0) to (2, 2). For example, it can be the path: (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2,2)

It can also be: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)

And quite a few other options are also possible. To figure out which one our `Pathfinder` will choose we have to take a look at how we set up our neighbors. We added them starting with the most "left" one and then moving clockwise: Left -> Top -> Right -> Bottom. This means `Pathfinder` will prioritize neighbors in that order.

Hence, its safe to assume it will suggest the path (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2,2).

Since starting position should not be included, the expectation is to have the path:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
it('should calculate path from point A to point B', () => {
expect(pathfinder.CalculatePath(node00, node22)).toStrictEqual([
node10, node20, node21, node22 // <--- ADD
])
})
})
``````

`` And it works! If you run `npm t` you should see your test pass. Let's add a few more cases to be safe:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
it('should calculate path from point A to point B', () => {
expect(pathfinder.CalculatePath(node00, node22)).toStrictEqual([
node10, node20, node21, node22 // <--- ADD
])
expect(pathfinder.CalculatePath(node01, node12)).toStrictEqual([
node11, node12
])

expect(pathfinder.CalculatePath(node20, node02)).toStrictEqual([
node10, node00, node01, node02
])
})
})
``````

At this point, our code should successfully compile with `npm start` and all test should pass with `npm t`: ## Accounting for cost

Now with basic implementation in place, we can improve our algorithm. First, let's add a movement cost:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
// ... //
private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
const cameFrom: Record<string, IGraphNode | null> = {
[start.Position.AsString()]: null
}
const costSoFar: Record<string, number> = {
[start.Position.AsString()]: 0
}

const frontier = new PriorityQueue<IGraphNode>()

frontier.Enqueue(start, 0)

while (!frontier.IsEmpty) {
const current = frontier.Dequeue()

for (const next of this._graph.GetNeighborsOf(current)) {
const newCost = costSoFar[current.Position.AsString()] + this._graph.GetCost(current, next) // <--- ADD
const nextStr = next.Position.AsString()
if (typeof costSoFar[nextStr] === 'undefined' || newCost < costSoFar[nextStr]){ // <--- CHANGE
const priority = newCost // <--- CHANGE
costSoFar[nextStr] = newCost // <--- ADD
frontier.Enqueue(next, priority)
cameFrom[nextStr] = current
}
}
}

return cameFrom
}
}

``````

Having cost will make our pathfinder slightly smarter and allow it to prioritize the least expensive paths.

No surprise our test still passes: `GetCost` of fake `Graph` always returns the same value which means all paths are equal. Let's make it a bit more interesting.

Remember our first test? The one that verifies that Pathfinder would choose (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2,2) to get from (0, 0) to (2,2)?

``````//  mantal map

(0, 0) | (1, 0) | (2, 0)

-----------------------

(0, 1) | (1, 1) | (2, 1)

-----------------------

(0, 2) | (1, 2) | (2, 2)

``````

Imagine now, that passing from (1,0) to (2,0) is more expensive than 1. That way, pathfinder has to consider another option, probably this one: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2,2)

To test that we first need to adjust `GetCost`:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
class Graph implements IGraph {
// ... //
public GetCost(a: IGraphNode, b: IGraphNode): number {
if(a.Position.x === 1 && a.Position.y === 0 && b.Position.x === 2 && a.Position.y === 0){
return 2
}

return 1
}
}
// ... //
})
``````

I simply compare the position of the first and second nodes and make sure if these nodes are (1, 0) and (2,0) respectively, the cost of crossing between them would be 2 instead of 1.

Also, we need to update our expectations. Now `Pathfinder` would prefer to avoid crossing form (1, 0) to (2,0) so it will choose (1, 0) -> (1, 1) instead:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
it('should calculate path from point A to point B', () => {
expect(pathfinder.CalculatePath(node00, node22)).toStrictEqual([
node10, node11, node21, node22 // <--- CHANGE
])

// ... //
})
})
``````

Woohoo! Tests are passing and now we are sure to cost is being accounted for by `Pathfinder`.

At this point, our code should successfully compile with `npm start` and all test should pass with `npm t`: By the end of the day, heuristics is just a function that nudges our pathfinding algorithm to be more efficient. Pretty much, it should help it understand where the "goal" may be relative to any other node.

For example, for our fake grid, the heuristic can be defined as a distance between two nodes:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
const heuristic = (a: IGraphNode, b: IGraphNode): number => Math.abs(a.Position.x - b.Position.x) + Math.abs(a.Position.y - b.Position.y) // <--- ADD
const graph = new Graph(edges)
const pathfinder = new Pathfinder(graph)
// ... //
})
``````

Since `heuristic` depends on how the graph is set up, I'll make it read-only property as well:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
constructor(
private readonly _heuristic: (a: IGraphNode, b: IGraphNode) => number // <--- ADD
){}
``````

And now we can add it to the tests:

``````// src/pathfinder/pathfinder.spec.ts
// ... //
describe('>>> Pathfinder', () => {
// ... //
const heuristic = (a: IGraphNode, b: IGraphNode): number => Math.abs(a.Position.x - b.Position.x) + Math.abs(a.Position.y - b.Position.y)
const graph = new Graph(edges)
const pathfinder = new Pathfinder(graph, heuristic) // <--- CHANGE
// ... //
})
``````

And all we have to do is use it in our priority calculations:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
// ... //
private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
// ... //
while (!frontier.IsEmpty) {
const current = frontier.Dequeue()

for (const next of this._graph.GetNeighborsOf(current)) {
const newCost = costSoFar[current.Position.AsString()] + this._graph.GetCost(current, next)
const nextStr = next.Position.AsString()
if (typeof costSoFar[nextStr]  === 'undefined' || newCost < costSoFar[nextStr]){
const priority = newCost + this._heuristic(goal, next) // <--- CHANGE
costSoFar[nextStr] = newCost
frontier.Enqueue(next, priority)
cameFrom[nextStr] = current
}
}
}
}
}
``````

And also, we can add "early exit": when we know we have reached the destination, there is no need for us to keep iterating:

``````// src/pathfinder/pathfinder.ts
// ... //
export class Pathfinder {
// ... //
private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
// ... //
while (!frontier.IsEmpty) {
const current = frontier.Dequeue()

if(current === goal){
break
}
// ... //
}
}
}

``````

And that's it! We have built ourselves A* pathfinder! At this point, our code should successfully compile with `npm start` and all test should pass with `npm t`: You can find the complete source code of this post in the `movement-pathfinding-4` branch of the repository.

## Conclusion

Awesome job! It was not an easy installment but you did it! You prepared your very-own implementation of Pathfinder. We will continue on this in the next article: we are going to apply this algorithm to our `Grid`. We also are going to add one more debug tool to illustrate the path and make sure it works correctly. Cannot wait to see you then!

I would love to hear your thoughts! If you have any comments, suggestions, questions, or any other feedback, don’t hesitate to send me a message on Twitter or email! If you enjoy this series, please share it with others. It really helps me keep working on it. Thank you for reading, and I’ll see you next time!

This is Chapter N in the series of tutorials "Building a game with TypeScript". Other Chapters are available here: