QRD.js (Quickroad.js)

Build Status: [master]

Purpose

• Allows you to define Points and Relations between points and put them in the matrix
• Allows you to find the shortest path between points

Todos

• Automate workflow with grunt/gulp
• Make sure relation.cost returns a float number
• Add code documentation wherever applicable
• Do not modify original point objects while using path finder. Use value objects
• Prepare functional tests so that even if unit tests work, the results of program running return values that are expected
• Use browserify to provide browser-friendly version of the library

  browserify lib/qrd.js --standalone QRD > qrd.js

Installation

HTML:

  <script src="qrd.js"></script>

NodeJS (install package):

  npm install qrd

NodeJS (include in your code):

  var QRD = require('qrd');

Usage

Setup

1. First, set up points

  var points = [
    new QRD.Point(0,0),
    new QRD.Point(2,2),
    new QRD.Point(3,1),
    new QRD.Point(5,-1),
    new QRD.Point(1,-1),
    new QRD.Point(4,-3)
  ];

2. Second, set up relations between points

  var relations = [
    new QRD.Relation(points[0], points[1]),
    new QRD.Relation(points[0], points[2]),
    new QRD.Relation(points[2], points[3]),
    new QRD.Relation(points[2], points[4]),
    new QRD.Relation(points[3], points[5]),
    new QRD.Relation(points[4], points[5])
  ];

3. Third, create an empty matrix

  var matrix = new QRD.Matrix();

4. Fourth, load points onto the matrix

  matrix.addPoints(points);

5. Fifth, load relations onto the matrix

  matrix.addRelations(relations);

Now, the matrix contains both points and relations. You can imagine this as dots on a matrix connected with straight lines (source -> target)

You could simply avoid using addPoints and addRelations methods by providing points and relations in Matrix constructor directly:

  var matrix = new QRD.Matrix({ points: points, relations: relations });

Perform calculations

1. Create an instance of PathFinder

  var pathFinder = new QRD.PathFinder(matrix);

2. Find the shortest path

You can reference points array directly

  pathFinder.findShortestPath(pathFinder.points[0], pathFinder.points[4]);
  // => [ point, point, point ]

Or you can use shortcut method if you know exact element indexes

  pathFinder.findShortestPath(0, 4);
  // => [ point, point, point ]

For simplicity purposes you can use 'first' and 'last' words to reference first and last point from the array

  pathFinder.findShortestPath('first', 'last');
  // => [ point, point, point ]

You're done! You've received the collection of points that form the shortest path between start and end points

Final form

  var points = [
    new QRD.Point(0,0),
    new QRD.Point(2,2),
    new QRD.Point(3,1),
    new QRD.Point(5,-1),
    new QRD.Point(1,-1),
    new QRD.Point(4,-3)
  ];

  var relations = [
    new QRD.Relation(points[0], points[1]),
    new QRD.Relation(points[0], points[2]),
    new QRD.Relation(points[2], points[3]),
    new QRD.Relation(points[2], points[4]),
    new QRD.Relation(points[3], points[5]),
    new QRD.Relation(points[4], points[5])
  ];

  var matrix = new QRD.Matrix({ points: points, relations: relations });

  new QRD.PathFinder(matrix).findShortestPath('first', 'last');
  // => [ point, point, ..., point ]

Where and how can you use the library?

• You can easily use this library to calculate the closest element to focus when navigating your website with keyboard/arrows (point <-- relation.cost --> point)
• You can easily calculate the shortest route to take (e.g. on a map)
• You can also extend the library to support elements in 3D space if needed

Test Suite

• In order to run the tests suite, simply type mocha in your console
• mocha.js must be globally installed

Contributing

Feel free to contribute or contact me at contact@maciejsmolinski.com with any questions