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

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

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.

Table of Contents

  1. Introduction
  2. Breadth-First search
  3. Accounting for cost
  4. Adding heuristic
  5. Conclusion

Breadth-First Search

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 {
      constructor(private readonly _graph: IGraph){}
    
      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 {
      // ... //
      // --- ADD --- //
      private GetCameFrom (start: IGraphNode, goal: IGraphNode): Record<string, IGraphNode | null> {
        const cameFrom: Record<string, IGraphNode | null> = {
          [start.Position.AsString()]: null
        }
    
        return cameFrom
      
      }
      // --- ADD --- //
    }

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
        }
        //  --- ADD --- //
        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
            }
          }
        }
        //  --- ADD --- //
        
        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[] = []
    
    	// --- ADD --- //
        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()
    
        // --- ADD --- //
        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', () => {
      // --- ADD --- //
      class GraphNode implements IGraphNode {
        public get Position(): Vector2D {
          return this._position
        }
    
        constructor(private readonly _position: Vector2D){}
      }
    
      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
        }
      }
      // --- ADD --- //
    
      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 {
        // ... //
      }
      // --- ADD --- //
      // 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))
      // --- ADD --- //
      
      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))
      
      // --- ADD --- //
      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],
      }
      // --- ADD --- //
    
      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', () => {  
        // --- ADD --- //
        expect(pathfinder.CalculatePath(node00, node22)).toStrictEqual([
    
        ])
        // --- ADD --- //
      })
    })

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
        ])
    	// --- ADD --- //
        expect(pathfinder.CalculatePath(node01, node12)).toStrictEqual([
          node11, node12
        ])
    
        expect(pathfinder.CalculatePath(node20, node02)).toStrictEqual([
          node10, node00, node01, node02
        ])
        // --- ADD --- //
      })
    })

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
        }
        // --- ADD --- //
        const costSoFar: Record<string, number> = {
          [start.Position.AsString()]: 0
        }
    	// --- ADD --- //
    	
        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 {
          // --- ADD --- //
          if(a.Position.x === 1 && a.Position.y === 0 && b.Position.x === 2 && a.Position.y === 0){
            return 2
          }
          // --- ADD --- //
          
          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:

Adding heuristics

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 _graph: IGraph,
        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()
    
    	  //  --- ADD --- //
    	  if(current === goal){
            break
          }
          //  --- ADD --- //
          // ... //
        }
      }
    }

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:

Like this piece? Share it!