qiao / pathfinding.js Goto Github PK
View Code? Open in Web Editor NEWA comprehensive path-finding library for grid based games
Home Page: http://qiao.github.io/PathFinding.js/visual/
A comprehensive path-finding library for grid based games
Home Page: http://qiao.github.io/PathFinding.js/visual/
These docs look great!
http://pathfindingjs.readthedocs.org/en/latest/user-guide/introduction/
You should add the link to the readme under "Introduction"
I tried to allow diagonal but it does not find a solution when "dontcrosscorners" is set to false. is any one else facing the same issue and can anyone help me with a solution ?
var matrix = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
];
var grid = new PF.Grid(7, 5, matrix);
var finder = new PF.AStarFinder({
allowDiagonal: true,
dontCrossCorners: false
});
var path = finder.findPath(2, 2, 4, 2, grid);
After a search is complete and the yellow path line is drawn, show somewhere the length of the yellow line (the length of the path; the cost of the path). This will more easily allow the user to compare which algorithm does the best on a particular problem, in cases where there are two long possible paths that are almost but not quite the same length. Currently, the user has to manually count the number of steps in the path to compare algorithms.
I followed the 'Basic Usage' and 'Advanced Usage' instructions, and the code as follow (Env: Mac OSX 10.8.3, node 0.8.22 / 0.10.13, pathfinding 0.4.3):
var PF = require('pathfinding');
var matrix = [
[0, 0, 0, 1, 0],
[1, 0, 0, 0, 1],
[0, 0, 1, 0, 0]
];
var grid = new PF.Grid(5, 3, matrix);
var finder = new PF.AStarFinder({
allowDiagonal: true,
dontCrossCorners: true
});
var path = finder.findPath(1, 2, 4, 2, grid);
console.log('path = %j', path); // path = [[1,2],[1,1],[2,1],[3,1],[3,2],[4,2]]
// But, the expected result is: path = [[1,2],[1,3],[2,3],[3,3],[4,2]]
// I think the point is param 'dontCrossCorners'.
I am using this in a game, and I have more than one wall. The Tiles are makred by IDs (0-500) and the way I create the blocked tiles ("walls") is by putting them into an array as such:
var blocked_tiles = new Array();
blocked_tiles.push(1);
blocked_tiles.push(190);
As you can see, your script only marks the ID 1 as a wall when in my game there is more than one wall with the ID of 1. How do I add more types of walls?
The uncovered square is colored as it used to be.
The uncovered square is white.
It looks weird to have a white line running through the colors, or a white hole in the middle of the colored area. And if someone is drawing walls in a way related to the colors, it might erase something they were interested in. Maybe it was a mistake that they drew the wall there in the first place, and they are removing the wall so they can draw it elsewhere. Then that person would prefer to see the colors, so they can keep drawing the wall in relation to all the colored squares.
An alternate solution is to clear all colored squares as soon as you start changing the wall layout. I'm not sure about that solution because some people might want to draw a wall in a way related to the colored squares, e.g. tracing the outline.
After experimenting with the site one would be interested in algorithm details (especially after Jump Point Search :) So it'd be nice to have descriptions a click away from the page. Wikipedia will do fine. Both algoritms and heuristics need links.
Hi,
Thanks for the great library.
A small problem: when using JumpPointFinder with no parameters specified, it can happen that the "smoothened" path is incorrect. In the diagram below the original path is in blue, whereas the smoothened path is in red. Needless to say, one cannot recover the original path by applying expandPath to the smoothened path.
For this particular grid, the problem vanishes when one uses e.g. AStarFinder or OrthogonalJumpPointFinder. I also include the respective 64*64 adjacency matrix.
The start point is (12,4) and the end point is (56,60).
Cheers,
Rob
[[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
seems like IDA algoritm freeze, just add a block in the way.
I'm finishing up a trace pathfind algorithm in javascript ...
Is there any chance it can be included in qiao?
Any recomendations?
Hi there, not sure if this is the right place to ask questions, but I'll try anyway.
I'm in the process of a massive update to my game, and I'm using Pathfinding.js for it. I have used it successfully in plotting the movement between two positions for units in a previous version, however, I would like to be able to use it for something else - the compilation of movement options for units.
Basically, the use case would be like this - I have a matrix and a position for a unit inside of that matrix, let's say it's 6,7
(so row 6, column 7). Now, I want to be able to pass some method this position, and an integer value, and what I get back is a list of all the possible coordinate options for that unit to move to. The final result would look something like this
Is it possible to do this with Pathfinding.js? If not I will write my own method but I thought if the lib can handle it then I shouldn't reinvent the wheel.
line 162 -- 166
jx = this._jump(x + dx, y, x, y);
jy = this._jump(x, y + dy, x, y);
if (jx || jy) {
return [x, y];
}
改为
jx = this._jump(x + dx, y, x, y);
if (jx || ( jy = this._jump(x, y + dy, x, y) ) ) {
return [x, y];
}
也许会有点性能的提升吧.
当jx存在时, 就不需要再执行 jy = this._jump(x, y + dy, x, y) 了
Hello, can i set what cells are diagonable? Is that possible with PathFinding? Or just is true or false for everything?
Here are suggestions for enhancing the buttons in the lower-right panel for controlling the search. The buttons would change their label and function depending on the state of the search. Next to each button I have written the state it would go to when clicked. I don't list the right-most button, Clear Walls, because it would always do the same thing - clear the walls and go to state B.
This state clears any existing search progress and then immediately goes to state S.
when search has finished - to F
selecting a different algorithm or adding or deleting walls - to M
Hi qiao,
You're building very cool and useful tools. Any chance of adapting PathFinding to work in non-euclidean space?
Drag the mouse very quickly across the grid, in any shape.
I get a continuous line of walls where I dragged my mouse.
I get walls only in some of those places. Though I dragged the shape of one continuous wall, the wall has big holes.
When ever i want to fix the values of the row and column then it behave like crap.Start and end blocks are not able to be moved and some blocks cant be blocked this happens for all the blocks below 360th column.
Things i have altered
in view.js
nodeSize: 10, // width and height of a single node, in pixel
init: function(opts) {
this.numCols = 32;
this.numRows = 48;
this.paper = Raphael('draw_area');
this.$stats = $('#stats');
},
in controller.js
setDefaultStartEndPos: function() {
var width, height,
marginRight, availWidth,
centerX, centerY,
endX, endY,
nodeSize = View.nodeSize;
width = 320;
height = 800;
marginRight = $('#algorithm_panel').width();
// availWidth = width - marginRight;
centerX = Math.ceil(width / 2 / nodeSize);
centerY = Math.floor(height / 2 / nodeSize);
this.setStartPos(centerX - 5, centerY);
console.log(centerX+"/"+centerY);
this.setEndPos(centerX + 5, centerY);
},
Hi @qiao as per the instructions given on the below link could you please configure the repo to trigger doc building on readthedocs:
When a node has been settled by both the forward and backward search, the search can be terminated, as the shortest path has been found. This does not mean, however, that this node must lie on the shortest path.
Take this example in a graph: http://www.cosketch.com/SavedImages/phS9Zraa.png
Forward search starts at s, inserts v into queue with weight 6 and t with weight 10. Backward search starts at t, inserts v into queue with weight 6 and s with weight 10. Forward search removes v from queue, finds t with weight 12, does not add to queue, settles v. Backward search removes v from queue, finds s with weight 12, does not add to queue, settles v. The search is aborted here, yet v is not on the shortest path.
Screenshot to illustrate the problem: http://i.imgur.com/N9FaLY6.png
The shortest path is obviously incorrectly drawn.
You did not include coffee-script in the npm dependencies so as a node.js module there will be a error "Error: Cannot find module 'coffee-script'.
Easy to fix via "npm install coffee-script" in the pathfinder module dir, but should be fixed in package.json I think.
Files lib/pathfinding-browser.js and lib/pathfinding-browser.min.js should be removed. These are release artefacts which should be produced only when making a release. For people to have ready access to these files they should be uploaded on the repo's release page.
Benefits of doing this are -
@qiao What do you say?
Try this:
Place walls around the goal expect one diagonal block and start a search (e.g. JPS). It won't find a solution, but there is one.
I think it has something to do with your getneighbours method which is far to complicated.
You try to avoid things like issue #17 but in fact you should let your user decide if you want this edge cutting or not.
Also you should clean up your GetNeighbours method which you can easily implement with two for-loops. Give it a try.
Hello,
I have a world which is based on a grid, but the characters roam freely in it. As such, I'd like to allow diagonal movement for the path finding, but not when it would cut over a corner. Below are pictures illustrating this:
My use case: a robot which is not infinitely thin cannot cut corners:
Of course this should be optional. I think it could be added to the Grid
fairly easily. Depending on how the pathfinding algorithms are implemented, perhaps in isWalkableAt
or getNeightbours
.
Here's a reference implementation of it for a different AStar pathfinder:
link.
Would it be possible to add a non binary cost (e.g. 0.5) to matrices, so cells can be counted as walkable but costing more, to allow taking terrain speed into account for example.
This afternoon I created an IDA* implementation, mostly following [1, 2]. At Gerjo@5f6b16f you can find the initial implementation. I've published a demo at http://gerjo.github.io/PathFinding.js/visual/ Recursion takes a fair amount of steps, so the visualisation can be disabled through a checkbox.
I noticed that the performance is terrible; add a few obstacles and you'll hit the javascript stack-recursion-limit. I'm at a loss here whether this is an implementation error on my side, or simply the nature of IDA*. Any thoughts or suggestions?
[1] http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html
[2] ftp://ftp.cs.utexas.edu/.snapshot/hourly.1/pub/AI-Lab/tech-reports/UT-AI-TR-87-46.pdf
The minified version at /lib/pathfinding-browser.min.js appears to be rebuilt incorrectly.
I'm not sure if I'm doing something wrong, I added the library via browser as mentioned in the docs. When I include pathfinding-browser.js
all my app crashes, not sure why. If I include the minified version then the app works again but PF
is nowhere to be found. Do I need to include any other dependency?
Hi @qiao
Could you please add me as a collaborator for pathfinding on npm. See https://www.npmjs.org/doc/cli/npm-owner.html for details on how to do it.
imor
In the file Grid.js in the function _buildNodes, I saw a local variable row, but it's unused. Sorry for my very-very bad English!
@rafaelcastrocouto Do you know if Trace is guaranteed to find the shortest path?
In the above image a path bypassing the upper obstacle would be shorter but Trace goes by near the bottom obstacle. Is this a bug or it's alright?
Tried with and without diagonal option defined and same result. When I run the pathfinder method it works twice returning expected results in an array. When I run it for a third time, it returns an empty object. Strange. http://jsfiddle.net/ccarterc1984/5ABHL/
This task should:
While a search is running, you can draw walls. You can even draw them in the path of the colored squares. But the search ignores the newly-drawn walls and just runs right through them. If you rerun the search after it finishes, though, your newly-drawn wall is now there.
Trying to draw a wall during a search should make one of these things happen:
Another idea is for the search to dynamically take this new wall into account, and work around the new wall while still remembering what it already searched, but I would guess that none of your current algorithms are made to deal with that situation. If they are, though, that would be really cool to see.
Great plugin!
I'm having a really unusual problem. Sometime, at random, I will get the following error from line 851 of pathfinding-browser.js:
Uncaught TypeError: Cannot read property '0' of undefined
It obviously has to do with smoothing. But when I deactivate smoothing I still get a random error in another line related to the path[0][0] not being set. It really is bizarre. There's nothing unusual as to how I am creating the path. Example of my parameters when the error happens:
var path = finder.findPath(113, 135, 140, 165, grid);
The grid, which is 800 x 300, is being re-created just before the path is created. I'm looping through a bunch of objects and setting nodes unwalkable just after creating the grid. I'm literally scrapping the old grid and creating a new one just before I create the path each time (not using the clone method).
The error is also happening at line 507:
Grid.prototype.setWalkableAt = function(x, y, walkable) {
this.nodes[y][x].walkable = walkable;
};
Any idea why path[0][0] is somehow becoming undefined?
Windows doesn't have make preinstalled so it shouldn't be a required dependency
Not really sure if this is an issue ...
All path-finders return every grid step in the path, except the JumpPointFinder that ignores all clear paths in between. Is this expected, like some intrinsic finder behavior, or the gaps should be returned in the array?
Just to make myself clear: http://codepen.io/rafaelcastrocouto/pen/cveyC
uncomment the 3rd line of javascript to understand.
When I run make I'm presented with an error (see below). I've run it through Google at no avail.
Steps I've taken so far:
install npm v1.3.1 and nodejs v0.10.12, and through npm I installed uglify-js and browserify.
The error
kubanskaya:PathFinding.js gerjo$ make
/Users/gerjo/PathFinding.js/utils/build.js:12
var browserified = browserify.bundle(__dirname + '/../src/PathFinding.js');
^
TypeError: Object function (opts) {
if (opts === undefined) opts = {};
if (typeof opts === 'string') opts = { entries: [ opts ] };
if (Array.isArray(opts)) opts = { entries: opts };
var b = new Browserify(opts);
[].concat(opts.entries).filter(Boolean).forEach(b.add.bind(b));
return b;
} has no method 'bundle'
at build (/Users/gerjo/PathFinding.js/utils/build.js:12:33)
at Object. (/Users/gerjo/PathFinding.js/utils/build.js:19:1)
at Module._compile (module.js:456:26)
at Object.Module._extensions..js (module.js:474:10)
at Module.load (module.js:356:32)
at Function.Module._load (module.js:312:12)
at Function.Module.runMain (module.js:497:10)
at startup (node.js:119:16)
at node.js:901:3
make: *** [lib/pathfinding-browser.js] Error 8
BestFirstFinder calculates f as follows -
f = g + (h * 1000000)
As the weight of the heuristic function h is huge, the heuristic function dictates which nodes should be expanded first hence the greedy behaviour.
TraceFinder calculates f as follows -
f = (g * aNumberSmallerThanOne) + h
This again means that the effect of h is more pronounced than that of g.
This is also evident from test runs on actual maps where the order of node expansion is identical between the two algos. Try it yourself @ http://qiao.github.io/PathFinding.js/visual/
Ping @qiao @rafaelcastrocouto
I'm not sure if this is because the implementation makes this difficult, or if you just forgot, but Jump Point search will always run with diagonals allowed. It also doesn't have a bi-directional option. If possible, it would be nice to see these added. I might be able to touch up a bit on my JS and write it in for you...
Currently, if you surround the start position with walls so it can't get to the end position, green fills up its area with colored squares, and then nothing happens. It would be nice to have some indicator that the search has given up. (And if currently, the code actually keeps looking for a solution that doesn't exist infinitely, then the first step is to make it actually give up when it can't do anything else.)
Maybe all of the blue-colored squares could turn light red. Or just the ones on the boundary.
Make a way to save the layout of walls, start position, end position, selected algorithm, and algorithm settings in the URL. If someone visits that URL, the pathfinder is preconfigured with those settings, ready for the user to click Start Search. That way, people can share links to configurations with interesting behavior. For instance, they can show someone situations where a certain algorithm finds a suboptimal path.
To get the link, the user might click a button or link somewhere on the page that would display and select the URL for the current layout, so the user can just hit Command/Ctrl-C to copy it. Or possibly, the current URL could continuously get updated with whatever the user is setting, but I think it would be bad for the user to see the URL to the page turn ugly and long as he changes things.
Sometimes, the shortest path is not enough. It requires a shortest path with less turns. It is quite normal in the robot and maze problem. For example, the graph below is the shortest path found by A* algorithm with Manhattan distance.
If we consider turning is an issue here, the actual shortest path is that go down then turn left and go to the goal directly. This path is the same weight with the shortest path found above but with less turns.
PathFinding.js is a great searching library but I notice that PathFinding.js does not provide this feature directly. Is there anyway to add the feature in and is there any plan to support this feature by default?
Any clues on how you could get this to work in a 3d environment, such as voxeljs?
initially thought it could work if I simply scored each possible voxel around the pathfinder, but not sure how I'd feed that into this if there are overlapping paths.
I use PathFinding.js within a simulation with a population and try to optimize it a bit. There is kind of a counter and sometimes a queue of clients build up, which is expected, because one is handled at time. However, everyone in the queue searches the whole board for a route through the only door which is blocked by another client and consumes a lot of cpu cycles. How can I limit search depth to let's say a distance of 10?
In the same example I want to make the door only work in one way, let's say North to South, so that the clients do not try to reach the counter that way. That way I could implement exit doors and entrances of a building.
I do not expect a ready to go solution, but a an educated guess where to start would be really helpful.
A*
heuristicAllow Diagonal
and Bi-directional
start
I've made my own benchmarks and it appears that the algorithm is fast but clone method is really slow
Would it be possible to search for a path without cloning the grid ?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.