PathFinding.js

A comprehensive path-finding library in javascript.

Introduction

The aim of this project is to provide a path-finding library that can be easily incorporated into web games. It may run on Node.js or the browser.

It comes along with an online demo to show how the algorithms execute. (The pathfinding speed is slowed down in the demo)

Note that this project only provides path-finding algorithms for 2D space. If you need to work in a 3D environment, then you may use @schteppe's fork.

There is new documentation being written for PathFinding.js. You can read it here. Note that this is in very early stages and far from complete so keep your eyes open for mistakes and don't hesitate to open a pull request in case you find one.

Server

If you want to use it in Node.js, you may install it via npm.

npm install pathfinding

Then, in your program:

var PF = require('pathfinding');

See the Basic Usage section below for usage details.

Browser

If you have bower installed then you can install it with the following command:

bower install pathfinding

By default bower will install pathfinding under the bower_components folder, so to include it in your page do something like:

<script type="text/javascript" src="path/to/bower_components/pathfinding/pathfinding-browser.min.js"></script>

You can also grab a release from the Releases Page if you don't use bower.

Basic Usage

To build a grid-map of width 5 and height 3:

var grid = new pfg.Grid(5, 3); 

By default, all the nodes in the grid will be able to be walked through. To set whether a node at a given coordinate is walkable or not, use the setWalkableAt method.

For example, to set the node at (0, 1) to be un-walkable, where 0 is the x coordinate (from left to right), and 1 is the y coordinate (from up to down):

grid.setWalkableAt(0, 1, false);

You may also pass in a matrix while instantiating the pfg.Grid class. It will initiate all the nodes in the grid with the same walkability indicated by the matrix. 0 for walkable while 1 for blocked.

var matrix = [
    [0, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
];
var grid = new pfg.Grid(matrix);

Currently there are 10 path-finders bundled in this library, namely:

• AStarFinder *
• BestFirstFinder
• BreadthFirstFinder *
• DijkstraFinder *
• IDAStarFinder.js *
• JumpPointFinder *
• OrthogonalJumpPointFinder *
• BiAStarFinder
• BiBestFirstFinder
• BiBreadthFirstFinder *
• BiDijkstraFinder *

The prefix Bi for the last four finders in the above list stands for the bi-directional searching strategy.

Also, Note that only the finders with trailing asterisks are guaranteed to find the shortest path.

To build a path-finder, say, the AStarFinder:

var finder = new pfg.AStarFinder();

To find a path from (1, 2) to (4, 2), (Note: both the start point and end point should be walkable):

var path = finder.findPath(1, 2, 4, 2, grid);

path will be an array of coordinates including both the start and end positions.

For the matrix defined previously, the path will be:

[ [ 1, 2 ], [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 3, 2 ], [ 4, 2 ] ]

Be aware that grid will be modified in each path-finding, and will not be usable afterwards. If you want to use a single grid multiple times, create a clone for it before calling findPath.

var gridBackup = grid.clone();

Advanced Usage

When instantiating path-finders, you may pass in additional parameters to indicate which specific strategies to use.

For all path-finders, you may indicate whether diagonal movement is allowed. The default value is false, which means that the path can only go orthogonally.

In order to enable diagonal movement:

var finder = new pfg.AStarFinder({
    allowDiagonal: true
});

When diagonal movement is enabled, you might want to prevent the path from touching the corners of the occupied grid blocks. This is usually desirable if the objects using the path have physical width and can also move between the grid cells.

To enable the corner crossing prevention:

var finder = new pfg.AStarFinder({
    allowDiagonal: true,
    dontCrossCorners: true
});

Note that dontCrossCorners only makes sense when allowDiagonal is also used. Currently all algorithms except JumpPointFinder support this feature.

For AStarFinder, BestFirstFinder and all their Bi relatives, you may indicate which heuristic function to use.

The predefined heuristics are pfg.Heuristic.manhattan(default), pfg.Heuristic.chebyshev, pfg.Heuristic.euclidean and pfg.Heuristic.octile.

To use the chebyshev heuristic:

var finder = new pfg.AStarFinder({
    heuristic: pfg.Heuristic.chebyshev
});

To build a BestFirstFinder with diagonal movement allowed and a custom heuristic function:

var finder = new pfg.BestFirstFinder({
    allowDiagonal: true,
    heuristic: function(dx, dy) {
        return Math.min(dx, dy);
    }
});

To smoothen the path, you may use pfg.Util.smoothenPath. This routine will return a new path with the original one unmodified.

var newPath = pfg.Util.smoothenPath(grid, path);

Note that the new path will be compressed as well, i.e. if the original path is [[0, 1], [0, 2], [0, 3], [0, 4]], then the new path will be [[0, 1], [0, 4]].

To just compress a path without smoothing it, you may use pfg.Util.compressPath.

var newPath = pfg.Util.compressPath(path);

To expand the compressed path like [[0, 1], [0, 4]] back to [[0, 1], [0, 2], [0, 3], [0, 4]], you may use pfg.Util.expandPath.

var newPath = pfg.Util.expandPath(path);

Development

Layout:

.
|-- lib          # browser distribution
|-- src          # source code (algorithms only)
|-- test         # test scripts
|-- utils        # build scripts
|-- benchmark    # benchmarks
`-- visual       # visualization

Make sure you have node.js installed, then use npm to install the dependencies:

npm install -d 

The build system uses gulp, so make sure you have it installed:

npm install -d -g gulp

To build the browser distribution:

gulp compile

To run the tests (algorithms only, not including the visualization) with mocha and should.js First install mocha:

npm install -d -g mocha

Then run the tests:

gulp test

To run the benchmarks:

gulp bench

Or if you are feeling lazy, the default gulp task does everything(except running the benchmarks):

gulp

License

MIT License

© 2011-2012 Xueqiao Xu <xueqiaoxu@gmail.com>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

SQLite format 3

@ 
.(k
�� ����;last_compatible_version16version41
#mmap_status-1 ����;
last_compatible_version
version# mmap_status
��J
e) file:///D:/Project/lib/pfg/visual/index.htmlPathFinding.js.�}�f2&
��
 urls
��
  .�}�f2&0
B


��

��

�� .�}�f2&      
��0
e file:///D:/Project/lib/pfg/visual/index.html
��/e file:///D:/Project/lib/pfg/visual/index.html
��

��
  .�s�
�� .�s�
��

��/e file:///D:/Project/lib/pfg/visual/index.html   ��g�e�v%�q ��}BQ<��;��z
�
�

y��
�tabledownloadsdownloadsCREATE TABLE downloads (id INTEGER PRIMARY KEY,guid VARCHAR NOT NULL,current_path LONGVARCHAR NOT NULL,target_path LONGVARCHAR NOT NULL,start_time INTEGER NOT NULL,received_bytes INTEGER NOT NULL,total_bytes INTEGER NOT NULL,state INTEGER NOT NULL,danger_type INTEGER NOT NULL,interrupt_reason INTEGER NOT NULL,hash BLOB NOT NULL,end_time INTEGER NOT NULL,opened INTEGER NOT NULL,last_access_time INTEGER NOT NULL,transient INTEGER NOT NULL,referrer VARCHAR NOT NULL,site_url VARCHAR NOT NULL,tab_url VARCHAR NOT NULL,tab_referrer_url VARCHAR NOT NULL,http_method VARCHAR NOT NULL,by_ext_id VARCHAR NOT NULL,by_ext_name VARCHAR NOT NULL,etag VARCHAR NOT NULL,last_modified VARCHAR NOT NULL,mime_type VARCHAR(255) NOT NULL,original_mime_type VARCHAR(255) NOT NULL)�F 55
�/tablekeyword_search_termskeyword_search_termsCREATE TABLE keyword_search_terms (keyword_id INTEGER NOT NULL,url_id INTEGER NOT NULL,lower_term LONGVARCHAR NOT NULL,term LONGVARCHAR NOT NULL)X /
windexvisits_time_indexvisits CREATE INDEX visits_time_index ON visits (visit_time)X/
windexvisits_from_indexvisits CREATE INDEX visits_from_index ON visits (from_visit)O-
gindexvisits_url_indexvisitsCREATE INDEX visits_url_index ON visits (url)n%%
�tablevisit_sourcevisit_sourceCREATE TABLE visit_source(id INTEGER PRIMARY KEY,source INTEGER NOT NULL)�*
�/tablevisitsvisitsCREATE TABLE visits(id INTEGER PRIMARY KEY,url INTEGER NOT NULL,visit_time INTEGER NOT NULL,from_visit INTEGER,transition INTEGER DEFAULT 0 NOT NULL,segment_id INTEGER,visit_duration INTEGER DEFAULT 0 NOT NULL,incremented_omnibox_typed_score BOOLEAN DEFAULT FALSE NOT NULL)P++
Ytablesqlite_sequencesqlite_sequenceCREATE TABLE sqlite_sequence(name,seq)�
�atableurlsurlsCREATE TABLE urls(id INTEGER PRIMARY KEY AUTOINCREMENT,url LONGVARCHAR,title LONGVARCHAR,visit_count INTEGER DEFAULT 0 NOT NULL,typed_count INTEGER DEFAULT 0 NOT NULL,last_visit_time INTEGER NOT NULL,hidden INTEGER DEFAULT 0 NOT NULL)f

�/tablemetametaCREATE TABLE meta(key LONGVARCHAR NOT NULL UNIQUE PRIMARY KEY, value LONGVARCHAR)';
indexsqlite_autoindex_meta_1meta  h;� � T ��_ � W  v�h�C5
�indexkeyword_search_terms_index3keyword_search_termsCREATE INDEX keyword_search_terms_index3 ON keyword_search_terms (term)�C5
�indexkeyword_search_terms_index2keyword_search_termsCREATE INDEX keyword_search_terms_index2 ON keyword_search_terms (url_id)�C5
�?indexkeyword_search_terms_index1keyword_search_termsCREATE INDEX keyword_search_terms_index1 ON keyword_search_terms (keyword_id, lower_term)G)
indexurlsurl_indexurlsCREATE INDEX urls_url_index ON urls (url)�;;
�Atabletyped_url_sync_metadatatyped_url_sync_metadataCREATE TABLE typed_url_sync_metadata (storage_key INTEGER PRIMARY KEY NOT NULL,value BLOB)n7'
�indexsegments_usage_seg_idsegment_usageCREATE INDEX segments_usage_seg_id ON segment_usage(segment_id)�Q'
�;indexsegment_usage_time_slot_segment_idsegment_usageCREATE INDEX segment_usage_time_slot_segment_id ON segment_usage(time_slot, segment_id)�8''
�/tablesegment_usagesegment_usageCREATE TABLE segment_usage (id INTEGER PRIMARY KEY,segment_id INTEGER NOT NULL,time_slot INTEGER NOT NULL,visit_count INTEGER DEFAULT 0 NOT NULL)S+
mindexsegments_url_idsegmentsCREATE INDEX segments_url_id ON segments(url_id)M'
eindexsegments_namesegmentsCREATE INDEX segments_name ON segments(name)p
�3tablesegmentssegmentsCREATE TABLE segments (id INTEGER PRIMARY KEY,name VARCHAR,url_id INTEGER NON NULL)?S-
indexsqlite_autoindex_downloads_slices_1downloads_slices�h--
�tabledownloads_slicesdownloads_slicesCREATE TABLE downloads_slices (download_id INTEGER NOT NULL,offset INTEGER NOT NULL,received_bytes INTEGER NOT NULL,finished INTEGER NOT NULL DEFAULT 0,PRIMARY KEY (download_id, offset) )G [5
indexsqlite_autoindex_downloads_url_chains_1downloads_url_chains�B55
�'tabledownloads_url_chainsdownloads_url_chains CREATE TABLE downloads_url_chains (id INTEGER NOT NULL,chain_index INTEGER NOT NULL,url LONGVARCHAR NOT NULL, PRIMARY KEY (id, chain_index) )