Building a Game With TypeScript. Pathfinding and Movement 3/7. Graph and Priority Queue

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 3/7. Graph and Priority Queue

Node vector created by WangXiNa - www.freepik.com

Hey folks! In the last article, we spent our time highlighting Nodes in configurable range. Our next step is calculating the path Ship can take from its current position to the one chosen by the Player.

I am going to skip the theory behind pathfinding algorithms and techniques. There are an enormous amount of books, papers, and videos out there, describing every single detail of these algorithms and patterns. For example, consider Amit Patel's blog, one of the best interactive explanations of many game-dev-related topics I’ve ever seen. I personally have learned a ton from his work and cannot recommend it highly enough.

Moving forward I will assume that you have an understanding of what a graph and a queue are, and how Breadth-First Search and A* algorithms work. We will apply this knowledge to build a pathfinding system in our TypeScript game.

Throughout the series, we follow the "incremental approach" mantra: start simple and bring on complexity when necessary. In the spirit of that, we will start our pathfinding journey with, perhaps, the easiest algorithm for the job: Breadth-First Search. Then, we extend it to become smarter, eventually ending up with an A*.

To implement these algorithms we need some data structures that do not exist out-of-the-box in JavaScript/Typescript: Graph and Priority Queue. In this installment, we will focus on preparing these structures.

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-2 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. Graph and Graph Node
  3. Interface and tests for Priority Queue
  4. Implementing Priority Queue
  5. Conclusion

Graph and Graph Node

Graph, by the end of the day, is a set of locations and connections between these locations. Or, using another terminology, Nodes and Edges. Nodes can be presented in many ways but we will simply consider them coordinates presented by Vector2D.

We could run away with a simple object of type Vector2D but having a dedicated interface will slightly ease our efforts when we will apply Graph on our Grid:

// src/utils/graph/node.h.ts
    import { Vector2D } from '@/utils'
    
    export interface IGraphNode {
      Position: Vector2D
    }

In our, rather naive first implementation of Graph, we can agree that Graph is something that can return all nodes that are connected to a provided one. In other words, returns all its neighbors:

// src/utils/graph/graph.h.ts
    import { IGraphNode } from './node.h'
    
    export interface IGraph {
      GetNeighborsOf(node: IGraphNode): IGraphNode[]
    }

Also, it should be able to calculate the cost of moving from one node to another. This can become in handy if we want to introduce different types of nodes on our grid: some of them can be easily "passable" like plains and roads, some harder ("rivers", "forests") some impassable at all ("mountains", "swamps", etc):

// src/utils/graph/graph.h.ts
    // ... //
    export interface IGraph {
      GetCost(a: IGraphNode, b: IGraphNode): number // <--- ADD
      GetNeighborsOf(node: IGraphNode): IGraphNode[]
    }

And traditionally let's add barrel file:

// src/utils/graph/index.ts
    export * from './graph.h'
    export * from './node.h'

And don't forget to re-export our new module:

// src/utils/index.ts
    // ... //
    export * from './ecs'
    export * from './graph' // <--- ADD
    export * from './lifecycle'
    // ... //

Interface and tests for Priority Queue

Priority Queue’s API is also straightforward. It should support adding and removing elements from the queue (Enqueue and Dequeue respectively) as well as the IsEmpty property:

// src/utils/priority-queue/priority-queue.h.ts
    export interface IPriorityQueue<T> {
      IsEmpty: boolean
    
      Enqueue(item: T, priority: number): void
      Dequeue(): T
    }

Note, that IPriorityQueue is a generic type: it depends on some unknown type T. This is the type of element we put in the queue. It does not have to have any knowledge about what type is that, or what it does. All it cares about is that Enqueue can add only the same type of items into this instance of the queue. So, if we create a queue of strings, for example, the compiler won’t allow us to add numbers to it. Neat!

The only difference between Priority and regular Queues is the ability to prioritize items in the queue. This way, it's not just first-in-first-out, but rather "first-in-first-in-priority-out".

It will make our life slightly easier to also have a dedicated type for a pair "priority-value":

// src/utils/priority-queue/priority-queue.h.ts
    // ... //
    // --- ADD --- //
    export interface IPriorityQueueItem<T> {
      priority: number
      value: T
    }
    // --- ADD --- //

Following the TDD approach, let's add tests first:

// src/utils/priority-queue/priority-queue.spec.ts
    import { IPriorityQueue } from './priority-queue.h'
    
    describe('>>> Priority Queue', () => {
      let q: IPriorityQueue<string>
      
      it('should return IsEmpty true if queue is empty and false otherwise', () => { })
      it('should Enqueue and Dequeue items in the queue according to priority', () => { })
    })

It could be a queue of any type so we'll make do with string as one of the simplest types in JS.

Testing IsEmpty is quite simple. We validate it is true by default when q has no elements. Then we add something and check that IsEmpty is no longer true. Finally, we'll dequeue element and expect IsEmpty to be truthful again:

// src/utils/priority-queue/priority-queue.spec.ts
    // ... //
    describe('>>> Priority Queue', () => {
      // ... //
      
      it('should return IsEmpty true if queue is empty and false otherwise', () => { 
        // --- ADD --- //
        expect(q.IsEmpty).toBeTruthy()
    
        q.Enqueue('one', 1)
        expect(q.IsEmpty).toBeFalsy()
    
        q.Dequeue()
        expect(q.IsEmpty).toBeTruthy()
        // --- ADD --- //
      })
      // ... //
    })

Testing Enqueue and Dequeue is also straightforward. We need to verify that after adding items with a specific priority they are dequeued in proper order. The lower provided priority is, the upper item should be in the q:

// src/utils/queue/queue.spec.ts
    // ... //
    describe('>>> Queue', () => {
      // ... //
      it('should Enqueue and Dequeue items in the queue according to priority', () => {
        // --- ADD --- //
        q.Enqueue('two', 1)
        q.Enqueue('one', 0)
        q.Enqueue('three', 2)
    
        expect(q.Dequeue()).toEqual<string>('one')
        expect(q.Dequeue()).toEqual<string>('two')
        expect(q.Dequeue()).toEqual<string>('three')
        // --- ADD --- //
      })
      // ... //
    })

We add three items to an empty queue and then dequeue them one by one. Note, that even tho we added "two" first and "one" second, we expect the latter to be on the top of the queue anyway because its priority is 0.

Awesome! No surprise that our tests still fail: we are yet to add the implementation!

Implementing Priority Queue

There are a few ways to implement Priority Queue with TypeScript. I'll go with perhaps the easiest one: I'll use a native JS array and I am going to sort it during the insertion. We can always revisit and add other implementations in the future if we hit any issues:

// src/utils/priority-queue/priority-queue.ts
    import { IPriorityQueue } from './priority-queue.h'
    
    export class PriorityQueue<T> implements IPriorityQueue<T> {
      public IsEmpty: boolean
      public Enqueue(value: T, priority: number): void {
        throw new Error('Method not implemented.')
      }
      public Dequeue(): T {
        throw new Error('Method not implemented.')
      }
    }

Number one thing we need is a storage of items:

// src/utils/priority-queue/priority-queue.ts
    import { IPriorityQueue, IPriorityQueueItem } from './priority-queue.h' // <--- CHANGE
    
    export class PriorityQueue<T> implements IPriorityQueue<T> {
      private _items: IPriorityQueueItem<T>[] = [] // <--- ADD
      // ... //
    }

IsEmpty can do its job by comparing items length:

// src/utils/priority-queue/priority-queue.ts
    export class PriorityQueue<T> implements IPriorityQueue<T> {
      // ... //
    	
      // --- CHANGE --- //
      public get IsEmpty(): boolean {
        return this._items.length === 0
      }
      // --- CHANGE --- //
    
      // ... //
    }

To implement Dequeue we can turn to the native methods but also we have to check that item is in the queue in the first place

// src/utils/priority-queue/priority-queue.ts
    export class PriorityQueue<T> implements IPriorityQueue<T> {
      // ... //
      public Dequeue(): T {
        // --- CHANGE --- //
        const item = this._items.shift()
        if (typeof item === 'undefined') {
          throw new Error('Attempt to dequeue from an empty queue')
        }
    
        return item.value
        // --- CHANGE --- //
      }
    }

And finally, Enqueue is all about adding an item to the array and then sorting it based on priority:

// src/utils/priority-queue/priority-queue.ts
    export class PriorityQueue<T> implements IPriorityQueue<T> {
      public Enqueue(value: T, priority: number): void {
        // --- CHANGE --- //
        this._items.push({
          value,
          priority
        })
    
        this._items = this._items.sort((a, b) => a.priority - b.priority)
        // --- CHANGE --- //
      }
    }

And to make sure it works, let's instantiate and test it:

// src/utils/priority-queue/priority-queue.spec.ts
    // ... //
    import { PriorityQueue } from './priority-queue' // <--- ADD
    
    describe('>>> Priority Queue', () => {
      let q: IPriorityQueue<string>
      // --- ADD --- //
      beforeEach(() => {
        q = new PriorityQueue<string>() 
      })
      // --- ADD --- //
      // ... //
    })

Finally, we should update barrel files accordingly:

// src/utils/priority-queue/index.ts
    export * from './priority-queue'
    export * from './priority-queue.h'

And the one in utils folder:

// src/utils/index.ts
    // ... //
    export * from './onclick'
    export * from './priority-queue' // <--- ADD
    export * from './vector2D'

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-3 branch of the repository.

Conclusion

Awesome job! We have prepared the utilities we'll need to implement our Pathfinder. The next installment will be all about it. 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 VI in the series of tutorials "Building a game with TypeScript". Other Chapters are available here:

Like this piece? Share it!