a simple server-side path finding module for NodeJS
CoffeeScript JavaScript Shell
Switch branches/tags
Nothing to show
Latest commit 90be728 Oct 1, 2013 @yi fix typo
Permalink
Failed to load latest commit information.
bin setup project Jan 1, 2013
lib add sample in readme Oct 1, 2013
src fixed condition Jun 12, 2013
.gitignore setup project Jan 1, 2013
README.md fix typo Oct 1, 2013
index.js add index.js, and update version to 0.2.1 May 10, 2013
package.json fix typo Oct 1, 2013
tests working on grid Jan 1, 2013

README.md

Node Path Finding

This is a Node.JS implementation for AStar path finding algorithm. This implementation uses primitive data types (Number and Byte/Buffer) to present location and block data that significantly improve the speed and have a good control on memory consumption

Installation

npm install node-pathfinding

Advantages

  • This module uses much less runtime memory then other node path finding module I can find on the net
  • The path finding implementation uses primative JavaScript Number type, so much safe to memory leak
  • Simple code, easy to change and extend

Limitations

  • The max size of map is limited to 65535 x 65535
  • Does not support negtive location

How To Use

var array2d, buf, grid, height, path, pathfinding, width;

pathfinding = require("node-pathfinding");

array2d = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0]];

width = 4;

height = 5;

// generate grid from 2D array
buf = pathfinding.bytesFrom2DArray(width, height, array2d);
grid = pathfinding.buildGrid(width, height, buf);

path = pathfinding.findPath(1, 0, 1, 4, grid);

console.log("path:" + path);

// print the path
console.log("path on grid :" + (grid.toString(1 << 16 | 0, 1 << 16 | 4, path)));

// output:
// path:65536,131072,131073,196609,196610,196611,196612,131076,65540
// path on grid :[Grid(width=4, height=5)]
// Dump: ░=walkable, ▓=blocked
// ▓S1░
// ░▓23
// ░░▓4
// ▓▓░5
// ▓E76

Glossary

  • BrickLoc: To reduce memory usage and use less Object instances, each dot(node, point) in the given map is represented by an 32bit uint, which is composed by x << 16 | y
  • Map Buffer: The map is presented by a Buffer, column by row. Each dot(node, point) is a bit in the Buffer. 0 means walkable, 1 means blocked.

Performance and Memory Consumption

Try node tests/sync_astar_continue_test.js it does a continuous test of pathfinding on some map fixtures, and the vm memory recycled correctly.