search

qiao / PathFinding.js

A comprehensive path-finding library for grid based games
http://qiao.github.io/PathFinding.js/visual/
8.35k stars 1.31k forks source link

3d #20

Closed timoxley closed 10 years ago

timoxley commented 11 years ago

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.

qiao commented 11 years ago

This library is built for 2d scenes and flexibility is sacrificed for performance. I'm afraid that you have to roll your own :(

rafaelcastrocouto commented 11 years ago

A javascript 3d pathfinding algorithm... that would be awsome... plz tell us if you find (or develop) anything like that!

hellow554 commented 11 years ago

As far as I see this, it's only a problem of "GetNeighbours" in the Grid class. The other search algorithmns should work just fine. You could pass a 3DGrid to one of those algorithmn and try it. Of course you have to create that class on your own, but shouldn't be a big problem

qiao commented 11 years ago

@punkkeks In fact the whole Grid class have to be redefined. The methods of this class currently accepts as arguments only x and y coordinates and should be extended to accept z as well. And the Heuristic function are also required to have a 3D version. Moreover, the JumpPointFinder does not use the getNeighbors method and has its own way to find neighbours and thus it will be a pain to write a 3d version for this finder.

rafaelcastrocouto commented 11 years ago

thats the reality of pathfinding ... it aways seens very simple ... but its not.

2013/2/4 Xueqiao Xu notifications@github.com

@punkkeks https://github.com/punkkeks In fact the whole Grid class have to be redefined. The methods of this class currently accepts as arguments only x and y coordinates and should be extended to accept z as well. And the Heuristic function are also required to have a 3D version. Moreover, the JumpPointFinder does not use the getNeighbors method and has its own way to find neighbours and thus it will be a pain to write a 3d version for this finder.

— Reply to this email directly or view it on GitHubhttps://github.com/qiao/PathFinding.js/issues/20#issuecomment-13082028.

rafaelcastrocouto.jsapp.us

vogonistic commented 11 years ago

I'm intrigued by the JumpPointFinder algorithm, but until it works in 3D, there is the algorithm used by mineflayer:

https://github.com/superjoe30/node-astar

Here is mineflayer's getNeighbors implementation: https://github.com/superjoe30/mineflayer-navigate/blob/master/index.js#L168

lorenzhs commented 11 years ago

If you want to generalise this, the most flexible approach would be to use a graph data structure. In this graph, you have a node for each "pixel" and edges to the "pixels" you can travel to. It has a bit more overhead, but no knowledge at all of any grid or whatever. The only thing you'd have to change is graph "generation".

schteppe commented 10 years ago

I've modified Pathfinding.js to work for 3D graphs (you can still use it for 2D by using z=0 for all nodes). See code here: https://github.com/schteppe/PathFinding.js All tests from the original code works, and the browser demo works. I removed the "jump" algorithm (since I didn't know how to "port" it), and everything that has to do with corner-crossing and diagonals (they do not make any sense in the general 3D graph case).

As @lorenzhs suggested, the new code involves nodes and edges/neighbors. The Grid class is now only a utility used to generate a grid structure of nodes and adding neighbors.

@qiao: what should I do with this new code? Merging it into your repo would be great, but you have 2D-specific things in it that makes this a hard task... Or maybe you have ideas on how to combine the 2D and 3D features?

qiao commented 10 years ago

@schteppe

Great work. But sorry it's not possible to directly merge your change into the master branch, since your implementation will have more overhead when used in a 2D scenario and the JumpPointFinder is gone.

As a workaround, I can add a link to your fork in my README file. Then if some one want to use PathFinding.js in a 3D scenario, he may use the code in your fork. Or I can merge your fork as a branch.

Thank you for the efforts.

timoxley commented 10 years ago

@schteppe why don't you release a new package with your fork called pathfinding3d??

schteppe commented 10 years ago

Thanks for the response @qiao and @timoxley. You are both right. Personally I think it is better to have an own fork/repo for the library since it probably will diverge more from the original code in the future. I've renamed my fork to PathFinding3D.js and added a link back to PathFinding.js in the README.

Happy pathfinding!