prettymuchbryce / easystarjs Goto Github PK

Let's explore the possibility of converting the code base to Standard JS, along with adding a .editorconfig file.

We should provide a typescript definition file for the folks who prefer to use TypeScript.

In my game, I have two types of obstacles. Walls and Units/soldiers. Units can be diagonally crossed, but walls can't. So I have to implement my own checkAdjacentNode or isTileWalkable to allow these two types of elements.

Any ideas of how to do that with the current API?

Hi, when walking on 0
[1, 0]
[0, 0]
there should be an option to allow or prevent the diagonal when next to one obstacle.

Also
[1, 0]
[0, 1]
to allow or prevent when walking between diagonally between two obstacles

How would you go about implementing a directional condition on some tiles?

Take for example a ledge a character can jump of from, but cannot climb onto.

Here is an example from vim-adventures. You can move from left to right onto the ledge, but not from right to left.

Would you be willing to accept a PR for this?

For example, if my player clicks on a rock, I want him to path to next to the rock.

Similarly for my ranged enemies (who can fire lets say 4 tiles distance), I want them to path to 4 squares away.

I coded a similar thing for a C# A* algorithm and I think it was possible purely through an early abort if the path reached the distance required, no pathfinding changes needed.

I'm looking for a way to make transitional or "bridge" tiles, that could connect two other tile types.

I.e.
Imagine that 0 is terrain, 1 is stairs and 2 is a wall.

let grid = [
  0, 0, 0, 0, 0, 0,
  0, 2, 2, 0, 2, 0,
  0, 2, 0, 0, 2, 0,
  0, 2, 0, 1, 2, 0,
  0, 2, 2, 2, 2, 0,
  0, 0, 0, 0, 0, 0
]

All tiles (0, 1, 2) should be acceptable, but in order to get from 0 to 2 or vice versa, 1 must be crossed.

I can't find a built-in feature to support this and the directional conditions are not exactly what I'm looking for.

Any suggestions?

#16 strikes back!

For example:

Another:

Coordinates for reproduce:
Start point (4,4)
End point (2, 2)

I would like to set allowed directions for each tile, to force desired path and not the shortest path.

We should explore the feasibility of taking advantage of the Web Workers API to calculate paths. This would come in the form of an optional API method to enable this feature, similar to enableSync().

It's probably a little far out, but it would also be interesting to see if we can take advantage of Web Assembly in some way to improve performance.

Why not have a bower package?

Need to figure out why

I have an iso "engine" in pixi that I am using easystarjs to do the walking and auto roaming. It is working great except for when I try x: 4, y: 7 to dx: 43, dy: 39. That is a long path, but x: 4, y: 7 to dx: 40, dy: 39 works. I did notice that the character walks slightly to the side of the path, but is still walking inline of it.

My code to create the grid is a little involved since it is iso. I couldn't attach the files here because it isn't supported. I can send you my entire code. It is a very universal iso engine.

It would be possible to have a tag for every version? Bower complains if you declare the dependency with a specific version because there's no tag in the repo:

bower easystarjs#0.1.12   ENORESTARGET No tag found that was able to satisfy 0.1.12

I would like to get a path not to a point but to one tile beside it.

Is there a better way to do this but to calculate 9 path to all fields and pick the shortest?

I need my callback function passed in .findPath() to assign the completed path array as a property to the object which called the .findPath() function, but I can't figure out how to do it since the passed in calback function is out of scope. Any advice would be appreciated.

Lets get CI working in easy star. Possibly through Travis or CircleCI.

What I'm doing:
Running easystar on array 200 x 200 size with easystar.setAcceptableTiles([0]);.

What I expect:
I run the algorithm from start(136,195) to end(198,16) and expect a path back because it exists.

What happens:
It fails to return a path. However if I run the path from any point that is in the range X: [4,195] and y:[4,195]. It works. It cannot find paths with points in the range x:[0,199] and y:[0,199]. i.e. It wont visit the outermost 4 points.

Replicated Behavior:
See this fiddle: jsfiddle

I use the function findPath() to run the pathfinder.
when i input something like
findPath (1, 136, 180, 195, 16);
it will work. If I try something like this:
findPath (1, 136, 196, 198, 3);
It will fail.

I'm absolutely lost as to why this is happening.

easystar.setDirectionalCondition and EasyStar.TOP are undefined

Looks like commit 704dca7 accidentally moved the karma and jasmine references from devDependencies to depenencies. As a result, anyone using easystarjs 0.4.1 or 0.4.2 ends up installing a bunch of extra packages (including e.g. nodemailer and phantomjs). Testing packages should be confined to devDependencies.

It also makes easystarjs look unnecessarily bad on npms.io due to https://nodesecurity.io/check/easystarjs.

hey I'm working on a project where i have a numeric gird of weighted tiles. It would be cool to add some utilities for numeric grids.

I'm thinking functions like setWeightedGrid() which would take something like

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

and assign weight 0 to 0, 1 to 1 etc...

The other useful function i think would be to set a threshold for passable tiles, something like setAcceptableThreshold() so i could say setAcceptableThreshold(10) and that means any tile > 10 would be deemed impassable.

I plan to implement these features on top of easystar anyway so just wanted to get your two cents and see if you would be interested in these features.

I'm trying to benchmark easystarjs for an experiment, but keep running into Zalgo bugs due to easystar.js not implementing asynchronous calls correctly.

For example, in some executions of easystar it is possible for the callback to be called synchronously (!!!). See the following line for reference:

https://github.com/prettymuchbryce/easystarjs/blob/master/src/easystar.js#L149-L152

This can cause terrible problems if you aren't expecting the callback to execute until all calls to easystar have been dispatched. A simple fix would be to wrap these calls in a setTimeout, for example.

When adding a second element that is smaller than the first element, the order is wrong.
I believe the bug is in getParentOf.

pseudo code to reproduce

var p = new PriorityQueue("value", PriorityQueue.MIN_HEAP);

var object1 = {};
var object2 = {};

object1.value = 10;
object2.value = 5;

p.insert(object1);
assert.equal(p.peek(), object1);

p.insert(object2);
assert.equal(p.peek(), object2);

assert.equal(p.shiftHighestPriorityElement(), object2);

I followed your step by step guide, nevertheless after running node app.js
an error occurs :

module.js:340
    throw err;
          ^
Error: Cannot find module 'express'
    at Function.Module._resolveFilename (module.js:338:15)
    at Function.Module._load (module.js:280:25)
    at Module.require (module.js:364:17)
    at require (module.js:380:17)
    at Object.<anonymous> (../easystarjs/demo/app.js:1:77)
    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)

When I do npm install easystarjs I get:

npm ERR! Error: Invalid version: "0.1"
npm ERR!     at Object.module.exports.fixVersionField (C:\Program Files\nodejs\node_modules\npm\node_modules\read-packag
e-json\node_modules\normalize-package-data\lib\fixer.js:178:13)
npm ERR!     at C:\Program Files\nodejs\node_modules\npm\node_modules\read-package-json\node_modules\normalize-package-d
ata\lib\normalize.js:29:38
npm ERR!     at Array.forEach (native)
npm ERR!     at normalize (C:\Program Files\nodejs\node_modules\npm\node_modules\read-package-json\node_modules\normaliz
e-package-data\lib\normalize.js:28:15)
npm ERR!     at final (C:\Program Files\nodejs\node_modules\npm\node_modules\read-package-json\read-json.js:310:33)
npm ERR!     at then (C:\Program Files\nodejs\node_modules\npm\node_modules\read-package-json\read-json.js:124:33)
npm ERR!     at C:\Program Files\nodejs\node_modules\npm\node_modules\read-package-json\read-json.js:299:40
npm ERR!     at fs.js:266:14
npm ERR!     at C:\Program Files\nodejs\node_modules\npm\node_modules\graceful-fs\graceful-fs.js:103:5
npm ERR!     at Object.oncomplete (fs.js:107:15)
npm ERR! If you need help, you may report this log at:
npm ERR!     <http://github.com/isaacs/npm/issues>
npm ERR! or email it to:
npm ERR!     <[email protected]>

npm ERR! System Windows_NT 6.1.7601
npm ERR! command "C:\\Program Files\\nodejs\\\\node.exe" "C:\\Program Files\\nodejs\\node_modules\\npm\\bin\\npm-cli.js"
 "install" "easystarjs"
npm ERR! cwd C:\Users\jstaab\Dropbox\programming\node\tetroggle-desktop
npm ERR! node -v v0.10.21
npm ERR! npm -v 1.3.11
npm ERR!
npm ERR! Additional logging details can be found in:
npm ERR!     C:\Users\jstaab\Dropbox\programming\node\tetroggle-desktop\npm-debug.log
npm ERR! not ok code 0

I think the answer may be found here:
http://stackoverflow.com/a/16888025/1467342

This looks great, by the way!

It would be a nice addition to be able to assign costs to nodes.

This would allow the path finding to take into account the "price" of visiting certain nodes. It would, for instance, be advisable for a character to take the road path instead of the (also walkable) mud path. This provides clear benefits to the simplistic walkable/non-walkable map type.

Thanks :)

My grid is a hexagonal grid, so the traversal is different from square grid. As illustrated below:

I want to disable R-L diagonal traversal but can't find via the API. I would have to call . setDirectionalCondition to every cell in the grid which would degrade performance of my app.

Can an option be added to enable/disable L-R and R-L diagonals directly from the options?

Some directional condition combinations don't work properly.

The problem is in the if statements in calculateDirection(). For example:

        if (diffX === 0, diffY === -1) return EasyStar.BOTTOM

That should be && instead of ,. The effect is that some directions "override" others with the same diffY. This test case demonstrates the problem:

      var easyStar = new EasyStar.js();
      var grid = [
          [0, 1, 0],
          [0, 0, 0],
          [0, 0, 0],
      ];
      easyStar.setGrid(grid);
      easyStar.setAcceptableTiles([0]);
      easyStar.setDirectionalCondition(1,1, [EasyStar.RIGHT]);
      easyStar.findPath(2, 0, 0, 0, function (path) {
          expect(path.length).toEqual(5);
          done();
      });
      easyStar.calculate();

Perhaps I don't understand the API well enough yet - but at this point, it seems to me that the name "findPath" is a little awkward, since it doesn't really find a path until one calls the "calculate" function.

I would like to suggest that a better name for "findPath" might be something like "definePath".

Here's one:

• Open the example page.
• Move the character to the upper-right corner of the red "rug".
• Click on the 2nd row of the 1st column of the rug.
• The character moves down two space to the bottom of the rug, then left 2 spaces into the 1st column, then up to the selected square. This is not the shortest path.
• This can be duplicated with certain other open paths that should move down 1 space and left two spaces.

(Sorry I don't have time to debug the problem myself. This is a great concept! We need more open source mini-components like this in the games community.)

Hello, I have this code

`function checkPath() {
console.log(typeof path)
if(path[1] === undefined) console.log("Null")
else {
console.log("Exists")
powerValue = 1;
}
}

path = electrical_pathfind.findPath(coordX, coordY, powerSourceIndex[0][0], powerSourceIndex[0][1], checkPath);
electrical_pathfind.calculate();`

Notice the typeof path line. This reads "Number." Sure enough, when I log "path," an integer value is logged - NOT an array.

What causes findPath to return a number rather then... well... a path? I have another completely separate pathfind system elsewhere in my code that works flawlessly - it returns an actual path!

I can start a path calculation with findPath(), but once I've started one I don't see a way to cancel it.

Suppose that the path takes multiple passes to compute, and before it's finished circumstances change and (a) the moving entity dies or no longer needs to move, or (b) the entity needs to move to a different location.

In that case, to avoid wasted computation it would be nice to be able to cancel a findPath instance. For example, findPath could return an integer ID, and I could later call cancelFindPath() with that ID to cancel it.

As far as I can see, cancelling would be easy to implement by just finding the object in the instances array and splicing it out.

Sometimes i want to abort a searching task , how can i do that?

The code sample below doesn't return the optimal path.

    var star = new EasyStar.js();
    star.setAcceptableTiles([0]);
    star.enableDiagonals();
    star.setGrid([
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0]
    ]);

    star.findPath(0, 1, 2, 1, function(_path){
        console.log(_path);
    });

    star.calculate();

It looks like the PriorityQueue is getParentOf calc should be:

Math.floor((index-1)/2);

We could benefit from some tree shaking by switching our builds to webpack 2

I have a use case where I would like one instance of Easystar to be invoked by many different objects. In such a case, it would be very handy to be able to pass the path callback function to the calculate() function instead of the constructor.

I realize that the callback function is also used in e.g. the setPath() function for signalling an invalid start or end position. However, I feel that this is a misuse of the callback. It might be an alternative to return a status code or throw an error on invalid input.

Thanks :)

Hi,

I was wondering if there is any reason Easystar should not use Promise objects. My idea is that instead of using callbacks given to findPath(), the function calculate() would simply return an array of Promise (one for each path).

The only concern I see is the ES6 requirement, but Babel is here for that.

Promises are used today in a lot of libs and apps, they are normalized and quite easy to use. In my app I wrap the callback in a Promise, what is not very elegant.

I can do a PR, I just want some returns before digging the code.
What do you think ?

When using easystar.disableCornerCutting(); app crashes when asked to calculate a path with obstacles that are accessible only from certain directions.

As long as there's at least one easystar.setDirectionalCondition() the app will crash when trying to calculate a path through these tiles.

C:\Users\Teslov\Desktop\openscape\node_modules\easystarjs\src\easystar.js:472
            var direction = calculateDirection(sourceNode.x - x, sourceNode.y - y)
                                                         ^

TypeError: Cannot read property 'x' of undefined
    at isTileWalkable (C:\Users\Teslov\Desktop\openscape\node_modules\easystarjs\src\easystar.js:472:58)
    at calculate (C:\Users\Teslov\Desktop\openscape\node_modules\easystarjs\src\easystar.js:404:26)
    at Socket.<anonymous> (C:\Users\Teslov\Desktop\openscape\index.js:131:14)
    at emitOne (events.js:96:13)
    at Socket.emit (events.js:188:7)
    at C:\Users\Teslov\Desktop\openscape\node_modules\socket.io\lib\socket.js:513:12
    at _combinedTickCallback (internal/process/next_tick.js:67:7)
    at process._tickCallback (internal/process/next_tick.js:98:9)

I would be extremaly glad if someone would find a solution to this problem. This feature is crucial to my project and my expertise with advanced algorithms is lacking.

With corner cutting enabled characters are able to pass through walls.

My name is Hernan; with a group of colleagues we are conducting a research about unused code present in dependencies of JavaScript projects. We call this functions, UFF (Unused foreign functions). We found that in most projects there exist a great amount of UFF that are being included in the final bundle.

In the case of easystarjs (v 0.3.0) our tools detected approximately 19 unused function in the dependencies (heap). Removing those functions, the size of easystarjs bundled could be reduced at least 16% (All tests passed).
I’m attaching the reduced version of your project.
easystar-0.3.0(optimized).txt

I’ll be very grateful if you can answer me the following questions:
-Did you were aware of the existence of these unused functions in your projects?
-Do you think that this is a problem?
-Do you think that can be useful a tool for deal with this problem?

Thanks in advance.

Cheers,

I'm trying to import this plugin for construct 2 but when tried it says common.js is missing. Can you suggest how can I import it to Construct 2?

I'm actually using this library for a project with Phaser, and I would like to use this part of the library.. I need to calculate the distance between two tiles for getting the maximum distance where my unit can go !

Sorry for my english..

hi all, it's the first time that i use easystar, and now i suffer some problems.Below is a grid.
var grid = [ [0,0,0,0,0,0,0,0,0,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0], [1,1,1,1,1,1,1,1,1,0] ] finder.setGrid(grid); finder.setAcceptableTiles([0]);

Now i want the game object move to 9,6, so i do this:
finder.findPath(0, 0, 9, 6, ( path )=> { if (path === null) { console.warn("Path was not found."); } else { console.log(path) this.move(path) } })

The output by console.log is:
{x: 0, y: 0}
{x: 0, y: 0}
{x: 0, y: 0}
{x: 0, y: 0}
{x: 0, y: 0}
{x: 0, y: 0}
{x: 0, y: 0}

This will probably require a function in each object that takes a parameter that is a second object.
This also means evaluate in PriorityQueue will need to be modified to pass the second object to the first object.
This is the same as overriding compareTo in java.

I have an interesting request. I'd like to be able to declare the world in a non-grid fashion (eg: add nodes and neighbours: a tree) so I can make waypoint pathfinding that isn't on the grid.

Coupled with your upcoming variable costs, this could be used to, for example, pathfind for an RTS with arbitrarily-sized blocking sprites.

Imagine just defining nodes where "doors" are, rather than including a bazillion empty room tiles. Great for road networks or dealing with walls that are at floating-point x,y coordinates.

Keep up the WONDERFUL WORK!

Hey,
just found this library and its really great!

Would it be possible to add an additional cost for changing direction? This way I could avoid the zig zag (which is of course the correct shortest path).

The problem is explained by another user on stack overflow: https://stackoverflow.com/questions/26302126/efficient-path-finding-algorithm-avoiding-zigzags

• pakcage.json has "main" field of 0.1.6 while built file is 0.1.7
• The node.js detection is checking typeof window === 'undefined' for CommonJS exports, but it's possible for people to be using this library with Browserify and in that case the exports will be empty.

If you setup a grid were all tiles are 1 like [1,1,1,1,....], set tiles [1,2] as walkable and change the map during the game by setting one tile to 2 it will break the path finding. At first it will try to move around but if you keep recalculating the path it can't decide on one path and get stucked.

I am using the Phaser Plugin, I added a fix there: appsbu-de/phaser_plugin_pathfinding#1

Maybe you like to add it to your setAcceptableTiles(), too.

EasyStar.js doesn't seem to take the cost for diagonals into account in my testing, so for paths that should be straight lines it will often go up and then down the diagonals for no reason. Below is some example code where I'm trying to go from point [0,0] to [7,0], which you'd assume would be a straight line, but for some reason easyStar makes a detour to [6,1] instead of going through [6,0].

Am I doing something wrong here?

Code:

zeroGrid = [];
for (i = 0; i < 10; i++) {
zeroGrid[i] = [];
for (j = 0; j < 10; j++) {
zeroGrid[i][j] = 0;
}
}

easystar = new EasyStar.js();
easystar.enableDiagonals();
easystar.setGrid(zeroGrid);
easystar.setAcceptableTiles([0]);

var mypath;
easystar.findPath(0, 0, 7, 0, function( path ) {
if (path === null) {
//alert("Path was not found.");
} else {
mypath = path;
//alert("Path was found. The first Point is " + path[0].x + " " + path[0].y);
}
});

easystar.calculate();

for (i = 0; i < mypath.length; i++) {
console.log("Node " + i + ", x = " + mypath[i].x + ", y = " + mypath[i].y);
} // when i = 6 this prints "Node 6, x = 6, y = 1", I don't know why it doesn't just go through x = 6, y = 0.

Thanks for any help!

Hi Team,

I want to add a new feature to convert the easystar generated path points to SVG path element. Could you please let me know where and how to add this feature.

Thanks,
Arun