search

vleue / polyanya

Pathfinding using Polyanya
Apache License 2.0
218 stars 15 forks source link

Per-triangle movement cost #35

Open LeshaInc opened 1 year ago

LeshaInc commented 1 year ago

It would be nice to support non-uniform cost pathfinding. For instance, agents would be able to avoid crossing water or other difficult terrain.

I don't know much about the algorithm inner workings, but I would imagine this would require being able to compute movement cost along any given line, which may or may not need another acceleration structure, and will certainly hurt performance. To avoid that, navmeshes could be made generic over the movement cost, with () being default.

Another option would be to support pathfinding over multiple navmeshes, connected by links, where each navmesh would have its own movement cost. This would have an added benefit of supporting chunked worlds, as well as multiple 3d levels.

gmorenz commented 2 months ago

I've started working on implementing this, the headline request not gluing navigation meshes together. The basic idea behind the adjustment to the algorithm being "create virtual root-locations (equivalent to a virtual image in optics) to determine what is observable, and then patch up the actual distance calculation as needed". Note that optics is particularly relevant here because light always takes the shortest path*, so "observable" in polyana really is "can the root see you" in the optical sense.

Along the way I'm implementing #30 / a feature enabling non-planar meshes (allowing for navigation on 3d meshes projected into 2d, disabling methods that let you go from a point to a polygon). In addition I expect it would be easy to implement actual 3d navigation (with agents traversing the surface of a mesh of polygons) using the same technique - though I'm holding off on that because supporting both 2d and 3d has significant code organization issues.

Whether this gets merged into this crate or it ends up being a fork isn't entirely clear to me (and isn't really up to me), there are likely some small performance tradeoffs involved. Probably best to wait for me to get it working though before we make any decisions on that.

* Or more precisely a local minimum, but it's basically the same thing.