+- 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: Implementing Pathfinding - LogicParrot - 04-25-2015
Quote:But why bother with a shared pointer? The vast majority of paths are not going to be shared so the memory overhead of the shared_ptr reference count is likely to use more memory overall than just copying the path when needed.A cPath instance will usually have dozens of Vector3d's, I think the overhead of copying it is not to be underestimated.
RE: Implementing Pathfinding - LogicParrot - 04-25-2015
(04-24-2015, 10:29 PM)xoft Wrote: If it was just one function, there would be no way for it to signal an error, such as an unreachable destination. (exceptions are a big no-no in MCS!). other than that, I agree.
I actually like worktycho's idea of enforced safety. the unified function could return a status code (still calculating, failed to find path, path found, etc), and it could return ia cPath in a parameter reference/pointer.
RE: Implementing Pathfinding - LogicParrot - 04-25-2015
Quote:...The cPathFinder should have a cPath object in it that should wrap the path being calculated, it should return a const reference to that internal object in GetPath() (and GetPath should not modify it). Calling StartPathfinding (former findPath) should clear the path and start calculating, calling Step (former isCalculationFinished) will calculate a few steps of the path and return true if the calculation is finished. Calling Step after the calculation finishes is not an error; calling StartPathfinding before a path is found resets the current path and starts another search....
Quote:xoft you proposed API would have issues and I think the pathfinder will need to create a new path object each time. The problem is that if you have a zombie pathing to a player from a distance, then you want to be continually recaclulating the path. But you want to continue along the old path until the new one is finished, or else you get weird pauses. So the old path can not be deleted until the new one is ready. So using an internal path object is problematic.How about creating a cPathFinder for every single path?
That way, cPathFinder can be thought of as a "non inflated path", it would receive the src and dest when constructed, StartPathFinding would no longer exist. Step would be called until the cPathFinder is ready, then its internal cPath would be used, and the client is free to store or discard cPathFinder when finished. (Along with its internal path)
In that sense, we could actually rename cPathFinder to cPath, (And former cPath would be an invisible internal class).
RE: Implementing Pathfinding - LogicParrot - 04-25-2015
Also, when a client decides to re-calculate a new path while an old one is being calculated, there is little data we can salvage from the old calculation, so destroying the whole cPathFinder is fine, most (if not all) of its internals will be cleaned upon recalculation anyways.
Codestyle fixed? - LogicParrot - 04-25-2015
Regarding coding style:
I've done some changes. @xoft, feel free to inspect my latest code and tell me if I've missed something. I really hope I haven't missed any of your remarks. I'll do a second pass later just in case.
I do hope I get used to the project's code style quickly. I learned a thing or two and I think I'll personally adopt most of your conventions. But it isn't easy to break old habits, so bear with me and point out my errors, I'll learn fast.
RE: Implementing Pathfinding - sphinxc0re - 04-26-2015
You could get rid of the sqrt function by using the octile search function.
here is an example: https://github.com/qiao/PathFinding.js/blob/19572d2bf8ecd1f4c51e456d44d3c239ad89c06f/src/core/Heuristic.js#L33-L36
a friend of mine coded this. the SQRT-1 is a constant
RE: Implementing Pathfinding - LogicParrot - 04-26-2015
(04-26-2015, 12:06 AM)SphinxC0re Wrote: You could get rid of the sqrt function by using the octile search function.
here is an example: https://github.com/qiao/PathFinding.js/blob/19572d2bf8ecd1f4c51e456d44d3c239ad89c06f/src/core/Heuristic.js#L33-L36
a friend of mine coded this. the SQRT-1 is a constant
Swapping euclidean distance with some other distance function will enhance performance at the cost of accuracy, there's also Manhatten distance which I think is even lighter. That's a possiblity, but I've been thinking about preserving euclidean distance AND enhancing performance, here's my thought:
I don't care about the F values, I only care about comparing F's, so I only care about their relative values.
Now, I thought of manipulating the math to get rid of sqrts, something along the lines of:
F=G+sqrt(stuff)
F^2=(G+sqrt(stuff))^2
F^2=g^2+2*g*stuff+stuff^2
F^2=g^2+stuff*(2*g+stuff)
Then I could store F^2 instead of F.
I need to check if there are some caveats here, and if this is actually faster, and if there's a cleverer math trick.
RE: Implementing Pathfinding - LogicParrot - 04-26-2015
Tycho and xoft, what's your opinion regarding https://forum.cuberite.org/showthread.php?tid=1571&pid=19643#pid19643 ?
Just bumping this because it got buried a bit behind.
RE: Implementing Pathfinding - worktycho - 04-26-2015
I like it. It seems to manage the state change really well and makes cleaning up easier. And in c++ it should be a zero cost abstraction.
RE: Implementing Pathfinding - xoft - 04-26-2015
Yes, sounds good.
I think even wrapping a generic Lua API around it shouldn't be too difficult, so that plugins could actually use pathfinding without mobs
