qiao / pathfinding.js Goto Github PK

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.

I'm finishing up a trace pathfind algorithm in javascript ...
Is there any chance it can be included in qiao?
Any recomendations?

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

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) 了

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

http://imgur.com/JjL0mRh

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.

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?

These docs look great!
http://pathfindingjs.readthedocs.org/en/latest/user-guide/introduction/
You should add the link to the readme under "Introduction"

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...

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.

The minified version at /lib/pathfinding-browser.min.js appears to be rebuilt incorrectly.

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.

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?

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.

states and button labels/actions

before searching; no colored squares - state B

• Start Search - to N
• Pause Search - button disabled (grayed out)

starting a new search - state N

This state clears any existing search progress and then immediately goes to state S.

during searching - state S

• Restart Search - to N
• Pause Search - to P

when search has finished - to F

search is paused - state P

• Resume Search - to S
• Cancel Search - to B

search has finished - state F

• Restart Search - to N
• Clear Path - to B

selecting a different algorithm or adding or deleting walls - to M

after search has finished and user has changed settings - state M

• Start Search - to N
• Clear Path - to B

additional features needed to implement this suggestion

• pausing the search (don't discard search progress when stopping)
• resuming the search
• clearing the path (the blue and green colored squares) but not the walls
• a system for changing button labels and function based on current state
• entering my state data above in the form of code

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);

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'.

Hi qiao,

You're building very cool and useful tools. Any chance of adapting PathFinding to work in non-euclidean space?

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.

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?

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?

Hello, can i set what cells are diagonable? Is that possible with PathFinding? Or just is true or false for everything?

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.

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:

• the search stops and you draw a wall
• the search stops, you draw a wall, and when you let go of the mouse, the search restarts
• you are unable to draw any walls until the search finishes or you stop it

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.

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.

Possibilities for where the number could be displayed

• Next to the option (e.g. A* Manhattan) that generated that path. This would make it easy to compare the paths generated by different options. However, it is unclear in this case where to put the number if you are comparing bidirectional vs no bidirectional. You could still put it next to the algorithm name, but then you couldn't see both numbers at once. But that still might be good enough.
• In the bottom-left corner, next to the ms and ops of the search.
• In a new panel, the "Transcript" panel, which would record the statistics of the most recent searches at its top, and scroll that history down as new searches are made. Like a chat transcript, or the "Paper Tape" feature of a calculator.
• In an overlaid bubble somewhere on top of the yellow line.
  • on or next to the start position
  • on or next to the end position
  • exactly halfway through the path

Steps to reproduce

• Use any A* heuristic
• Check Allow Diagonal and Bi-directional
• Do not paint any walls
• Click start

Expected Result

• Optimal path should be a straight line

Actual Result

• Optimal path has a diagonal in the center

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

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.

seems like IDA algoritm freeze, just add a block in the way.

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 ?

Windows doesn't have make preinstalled so it shouldn't be a required dependency

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.

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);
},

steps to reproduce

Drag the mouse very quickly across the grid, in any shape.

expected

I get a continuous line of walls where I dragged my mouse.

actual

I get walls only in some of those places. Though I dragged the shape of one continuous wall, the wall has big holes.

how to implement

• When drawing walls, while the mouse is down, ...
• instead of just drawing a wall under the current cursor position, ...
• always remember the last cursor position, and use a line-drawing algorithm to draw a continuous line from the previous position to the current position.

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!

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

Sometimes "Restart Search" leaves garbage. See attached image:

The blue node on the left, and the green one on the right are garbage. After pressing "Cancel Search" I get this:

It seems to leave at most one garbage node at a time, but these can be accumulated.

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]]

This task should:

1. Change and commit the version in package.json
2. Push to npm registery
3. Checkout the bower git repo
4. Update version in bower.json
5. Update the pathfinding-browser.js and pathfinding-browser.min.js files
6. Push to the bower git repo
7. Create a tag in bower git repo with the new version.

Steps

1. Start a search.
2. Wait for it to finish.
3. Draw a wall over any of the squares colored by the search.
4. Draw over the wall again to remove it.

Expected

The uncovered square is colored as it used to be.

Actual

The uncovered square is white.

Why

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.

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.

@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?

Hi @qiao as per the instructions given on the below link could you please configure the repo to trigger doc building on readthedocs:

https://docs.readthedocs.org/en/latest/webhooks.html

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:

Cutting corners:

Avoiding corner cutting:

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.

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 -

• It will prevent beginners from changing the wrong files. E.g. see #32.
• Because the minified file is a single line it is prone to merge conflicts. It will prevent those.

@qiao What do you say?

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

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/

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.

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.

I have a closed room with an only diagonal exit, none of the algorithms is able to find a solution.