PathFinder status

jan64 · 06-03-2015, 01:03 AM

These might be textured heads.

LogicParrot · (This post was last modified: 06-05-2015, 05:34 PM by LogicParrot.)

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.

LogicParrot · 08-06-2015, 04:21 AM

Exams done. Hopefully work will resume soon Smile

DiamondToaster · 08-06-2015, 04:39 AM

:O He's not ded.

worktycho · 09-30-2015, 11:43 PM

If pathfinding ever gets a bit slow, we might want to implement D* lite: http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf

LogicParrot · 10-02-2015, 06:52 PM

D* Lite doesn't work well for moving targets, there may be some variant which does though.

NiLSPACE · (This post was last modified: 10-02-2015, 07:54 PM by NiLSPACE.)

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.

LogicParrot · 10-02-2015, 08:03 PM

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

NiLSPACE · (This post was last modified: 10-02-2015, 08:12 PM by NiLSPACE.)

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.

LogicParrot · 10-02-2015, 08:18 PM

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