search

mikewesthad / navmesh

A plugin for path-finding in JS using navmeshes, with wrappers for Phaser 3 and Phaser 2
MIT License
356 stars 40 forks source link

Shortest Path #18

Open Wenish opened 4 years ago

Wenish commented 4 years ago

I saw this on the Todo list:

The astar heuristic & cost functions need another pass. They don't always produce the shortest path. Implement incomplete funneling while building the astar path?

besides that it works really great. Is there any chance this library will see an update which fixes this?

mikewesthad commented 4 years ago

There are a few todos to tackle in the next update, including that and upgrading everything to TS. If you wanted to tackle any in a PR, they'd be more than welcome! I have the TS update in progress, but it's slow going.

Just to clarify on the heuristic there, in case you felt like jumping in. The astar algorithm calculates the cost of moving between two polygons as the distance between the centers of the polygons, which is an OK approximation that's fast to compute. A more accurate and likely slower approach would be to calculate the length of the actual path the agent would travel from polygon 1 to polygon 2 and use that as the cost.

KonradLinkowski commented 3 years ago

I wanted to create a new issue related to that, but I will just post this image image

mikewesthad commented 3 years ago

Thanks for sharing. I forgot to update this thread when I was doing some research recently. NavMesh doesn't find the absolute shortest path - it finds a good path very fast. The smaller and more uniform the polygons in the mesh are, the more likely it is to find the shortest. So, you can mitigate issues via the design of the polygons in your navigation mesh.

I'm still doing research on fast ways to find the shortest path that don't sacrifice the speed gains of using a navmesh. Dropping a paper in here for future reference.

ogrotten commented 2 years ago

I would also like to add: the demo level is exactly a demo.

In my xp, navmesh generally need to be optimized by hand following certain guidelines. One of the first guidelines designers learn is that the node size should be be as consistent as possible. Bethesda games Skyrim and Fallout use navmesh. On their tutorial page, here's examples of inefficient and here it is cleaned up.

In @KonradLinkowski screenshot above, the path shown crosses 3 borders while the direct route would cross 5. That's likely why that choice was made. It does this because this demo level has a large diversity of sizes and shapes, which can make navigation difficult. It does however make the point that this module can do custom pathfinding in phaser 3.

Optimally, you'd have the 5 voids (the major spaces between all the blocks) each be a single node.

Also, There's ~30 nodes on the demo. I'll bet the system would be much more reasonable with ~60 nodes, but with no measurable difference in time.

In other words, the demo shows the viability of this module. It'll take a little diligence to create a navmesh that is optimal for various use case.