Path finding is the process of plotting the shortest route between two points by a computer application. So, how can we use it in our development process? The answer to this question lays in this article, so please read carefully.

Installation

For our needs we will use a JavaScript library called PathFinding.js. You can install it using npm or just download the package from https://github.com/qiao/PathFinding.js. Then in your application simply use require('pathfinding') for Node.js or <script src="./pathfinding-browser.min.js"></script> using browser side version. Decide yourself which one fits your needs. In our project we will use the standard script tag for local copy of the library.

Why?

For what reason we might want to use this library? The answer is simple. It has many built in, path finding algorithms. There are also available heuristics, just by switching some configuration options. The available search algorithms are listed below. And since you are a developer, you have surely heard something about them in the past.

• AStar
• BreadthFirst
• BestFirst
• Dijkstra
• JumpPoint
• Trace

A great online demo can be found at http://qiao.github.io/PathFinding.js/visual. There is a possibility to choose between algorithms, select the start and end points and add some walls to the board. Simply click Start Search to plot the shortest path between the points.

Lets examine an example situation where we could use our library. First we will use the A* algorithm, which is actually a variant of the Dijkstra's algorithm.

1 A* with Manhattan heuristic

length: 40
time: ~7 s
operations: 1108

2 Best-First-Search with Euclidean heuristic

length: 80
time: ~2.5 s
operations: 465

Pathfinding.js is a great library for both basic and advanced usage. There are many useful algorithms we can use in many situations. We haven't done a full presentation of the library, but our use case showed you how simple it is to find the shortest path between two points. Pathfinding.js can be used to build Tizen applications, games etc. The ideas of usage are only limited to the imagination of your mind. 

By studying these two images we are able to say which algorithm fits more our needs. In the first case we are using the A* algorithm (with the Manhattan heuristic), which behaves extremely slow in our example, but at the end, it finds a two times shorter way to home. In the second case we have used the Best-First-Search algorithm (with the Euclidean heuristic). That one found the “shortest” path very quickly, but as you can see it isn't optimal. It also made much less operations to complete it. Summing up the example, you can see how important is the decision about choosing the most suitable algorithm for our projects' needs before starting programming with pathfinding.js.

Usage

You should start by defining a virtual grid of points in a 2-dimensional space. Below you can find the description, how it should be made.

var sampleGrid = new PF.Grid(5, 8);

We just defined the matrix and now we are able to set the points which cannot be reached. It is important to set the disabled points. As by default all coordinates are allowed.

SampleGrid.setWalkableAt(2, 3, false); 

It is also possible to define a whole matrix and walkable coordinates in one step, by using the array notation.

var sampleMatrix = [
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];
var sampleGrid = new PF.Grid(5, 5, sampleMatrix);

The next step is to choose a search algorithm, we will call the findPath method and pass in our newly created sampleGrid as one of the parameters. The example of implementation is presented below. We've chosen the A* algorithm, because the results of our test found it the most suitable for our needs.

var sampleFinder = new PF.AstarFinder();
var samplePath = sampleFinder.findPath(0, 0, 2, 3, sampleGrid);

As a result we've got the array of coordinates with all the points needed to be visited during the virtual walk, including both the start and the end point.

Our sample project

We will try to visualise the effect of finding a path between points from the sample data. To do it, we will use an html table reflecting our sample grid, where the td tag represents one point. Every point is represented by a table cell, which can be found by specyfing the x and y coordinates. Please examine the source code to be sure you understand this cocncept.

This is how our board looks like. The white fields are walkable areas and the grey ones are disabled for pathfinding. The red square in the middle of the field is the start point, the other red square is the end point, while the green ones are showing the computed path.

This is a graphical representation of the previously presented sampleMatrix where we have marked the disabled fields by 1 and walkable areas by 0.

As in the previous chapter we plot the shortest path using just few lines of code. Simply define a matrix, create the grid and call the findPath method. Then use the drawPath function, which is responsible for plotting the path on the screen. The implementation of the function can be found below.

function drawPath(path) {
  setTimeout(function loop() {
    var current = path.shift();

    var point = document.querySelector('.c' + current[0] + current[1])
    point.classList.add('path')

    if (path.length)
      setTimeout(loop, 500);
  }, 500);
}

To make it more understandable we are using the setTimeout method for printing one coordinate of the path every 0.5 seconds. Our function takes the points from the beginning of the passed array, then finds a particular cell of the table using the built in querySelector method. The found cell is marked by adding a css class.

Summary

Pathfinding.js is a great library, both for basic and advanced usage. It provides many useful algorithms we can use in different situations. We haven't done an exhaustive presentation of the library but our use case showed you how simple it can be to find a path, in particular the shortest one. Pathfinding.js as a library can be used to build Tizen applications, games etc. The ideas are only limited by your mind.