Pathfinding Visualizer

NO ACCOUNT — Thu, 06 Aug 2020 19:56:23 +0000

Intro

I'd like to re-create and show how to build one of my favorite projects. Were going to create a basic Pathfinding Visualizer. At the end of this series (two parts), we will create a grid of nodes, with random walls, that can visualize Djistra's Pathfinding Algorithm.

This post assumes you have a basic dev environment setup as well as basic knowledge of HTML and Typescript.

Lets get started!

Setup

Start by creating a new project and then creating an index.html file. Within the body creating a <canvas> element. Give the canvas element an id of "canvas" and a width and height of 800px.

<body>
  <canvas id="canvas" width="800px" height="800px"></canvas>
</body>

After that create an main.ts file and in your terminal run tsc --watch main.ts.

Creating and Drawing Our Grid

In your main.ts file we need to initiate some global variables.

const numRows: number = 20;
const cellSize: number = 800 / numRows;
const canvas = <HTMLCanvasElement>document.getElementById('canvas');
const ctx = <CanvasRenderingContext2D>canvas.getContext('2d');

numRows is the number of rows/columns our grid will have. cellSize is the width/height of our canvas divided by the number of rows and columns. After that we get a reference to our canvas and the 2d context of our canvas.

After that we need to define our Cell interface, that we will populate our grid with.

interface Cell {
  row: number;
  col: number;
  distance: number;
  isVisited: boolean;
  isWall: boolean;
  previousNode: Cell | any;
}

Each cell has row and column which represents its place on the grid. A distance value which will represent the distance from one node to the next, a isVisisted value that our algorithm with use to determine if a cell as been visited before. isWall is how we determine if the cell is a wall or not (which our algorithm will use later on to find a path, and the preivousNode, which how we build our path from start to end.

Now that we have our cell lets create a grid full of them. We are going to accomplish this by creating a 2d array. Our next step is to create a function that will generate a 2d array and populate it full of Cells for us.

function createRandomGrid() {
  const grid: Array<Array<Cell>> = new Array(numRows);

  for (let i = 0; i < numRows; i += 1) {
    grid[i] = new Array(numRows);

    for (let j = 0; j < numRows; j += 1) {
      grid[i][j] = {
        row: i,
        col: j,
        distance: Infinity,
        isVisited: false,
        isWall: Math.random() < 0.2 ? true : false,
        previousNode: null,
      };
    }
  }

  return grid;
}

Our function createRandomGrid() generates and returns a 2d array of cells. Now that we can generate a grid, we have to display that data onto the webpage. To do that we are going to create a new function called drawGrid().

function drawGrid(context: CanvasRenderingContext2D, grid: Array<Array<Cell>>) {
  context.strokeStyle = 'black';
  context.fillStyle = 'brown';

  for (let i = 0; i < grid.length; i += 1) {
    for (let j = 0; j < grid.length; j += 1) {
      const value: boolean = grid[i][j].isWall;

      switch (value) {
        case true:
          context.fillRect(i * cellSize, j * cellSize, cellSize, cellSize);
          break;
        default:
          context.clearRect(i * cellSize, j * cellSize, cellSize, cellSize);
          break;
      }
      context.strokeRect(i * cellSize, j * cellSize, cellSize, cellSize);
    }
  }
}

In order to draw the grid we make use of a few functions from the Canvas2D Context. The fillRect, clearRect and strokeRect all take in four paramaters.

ctx.fillRect(x, y, width, height);

The draw the grid nicely, we use the i and j variables that are availible within the nested for loops, then multiply them by the cellSize to create an even grid.

Now lets break down the rest of the function. We pass in our canvas' context and a grid to draw. The first thing we do is define the styles for our cells. With fillStyle being the color of the walls. Next we will use a nested for loop to iterate over our grid, and if the isWall boolean is true, then we will fill in the cell on our grid, if not we will leave it empty.

Now lets create the masterGrid and render the grid on the webpage.

let masterGrid: Array<Array<Cell>> = createRandomGrid();
drawGrid(ctx, masterGrid);

If you open your index.html you will see a grid, with randomly placed walls. If you refresh your page, you can see the walls randomly shift positons.

In Part 2 (coming soon) we will explore how to implement and animate a pathfinding algorithm.

DEV Community: NO ACCOUNT

Pathfinding Visualizer

Intro

Setup

Creating and Drawing Our Grid