prettymuchbryce / easystarjs Goto Github PK
View Code? Open in Web Editor NEWAn asynchronous A* pathfinding API written in Javascript.
License: MIT License
An asynchronous A* pathfinding API written in Javascript.
License: MIT License
pakcage.json
has "main" field of 0.1.6 while built file is 0.1.7typeof 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.Hi,
I was wondering if there is any reason Easystar should not use Promise
objects. My idea is that instead of using callback
s 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 ?
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..
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.
Sometimes i want to abort a searching task , how can i do that?
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?
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.
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!
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.
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?
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.
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.
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?
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
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
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!
I would like to set allowed directions for each tile, to force desired path and not the shortest path.
Need to figure out why
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.
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".
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?
Why not have a bower package?
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'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?
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 :)
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,
Lets get CI working in easy star. Possibly through Travis or CircleCI.
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}
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)
We should provide a typescript definition file for the folks who prefer to use TypeScript.
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 :)
#16 strikes back!
Another:
Coordinates for reproduce:
Start point (4,4)
End point (2, 2)
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
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);
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.
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
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!
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.
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.
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 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 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 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.
easystar.setDirectionalCondition and EasyStar.TOP are undefined
Let's explore the possibility of converting the code base to Standard JS, along with adding a .editorconfig
file.
Here's one:
(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.)
We could benefit from some tree shaking by switching our builds to webpack 2
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.