+- Cuberite Forum (https://forum.cuberite.org)
+-- Forum: Cuberite (https://forum.cuberite.org/forum-4.html)
+--- Forum: Development (https://forum.cuberite.org/forum-13.html)
+--- Thread: PathFinder status (/thread-1571.html)
RE: PathFinder status - jan64 - 06-03-2015
These might be textured heads.
RE: PathFinder status - LogicParrot - 06-05-2015
I'm currently refactoring cMonster.cpp's pathfinding. I'd like to move all the the path recalculation logic out of monster.cpp to a new class which wraps cPath.
RE: PathFinder status - LogicParrot - 08-06-2015
Exams done. Hopefully work will resume soon
RE: PathFinder status - DiamondToaster - 08-06-2015
:O He's not ded.
RE: PathFinder status - worktycho - 09-30-2015
If pathfinding ever gets a bit slow, we might want to implement D* lite: http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf
D* is for static goals - LogicParrot - 10-02-2015
D* Lite doesn't work well for moving targets, there may be some variant which does though.
RE: PathFinder status - NiLSPACE - 10-02-2015
Here is a nice 2D visual representation of multiple pathfind algorithms: https://qiao.github.io/PathFinding.js/visual/ (After a while the IDA* started to freeze my browser though. It was using 900MB RAM)
If possible the Best-First-Search or Trace would be really fast. I'm not sure how they would work in a 3D environment though.
But of course the speed depends on the environment you put the algorithm in. If there simply is a wall between the start and end Trace seems to be the fastest, but in for example a maze A* seems to be faster.
We have BFS - LogicParrot - 10-02-2015
(10-02-2015, 07:28 PM)NiLSPACE Wrote: Here is a nice 2D visual representation of multiple pathfind algorithms: https://qiao.github.io/PathFinding.js/visual/ (After a while the IDA* started to freeze my browser though. It was using 900MB RAM)
If possible the Best-First-Search or Trace would be really fast. I'm not sure how they would work in a 3D environment though.
BFS does not guarantee finding the shortest path. A* is a bit slower but guarantees finding the shortest path. The code at Path.cpp already has a flag for switching to BFS. But it doesn't seem to be worth the tradeoff.
JPS sounds attractive. It's on the "potential todo" list @ first post.
RE: PathFinder status - NiLSPACE - 10-02-2015
JPS is doing really bad when trying in the representation. Is it really that good?
Oh, wait, when switching to JPS Octile it's really fast.
RE: PathFinder status - LogicParrot - 10-02-2015
(10-02-2015, 08:10 PM)NiLSPACE Wrote: JPS is doing really bad when trying in the representation. Is it really that good?
Oh, wait, when switching to JPS Octile it's really fast.
Keep the Manhatten distance, but untick "Visualize recursion".