Solution Not always the Shortest Path

zicklag commented 3 years ago

Hey there! It seems you've got the only Rust navmesh library I can find! :D

I'm testing out this library for use in my game for enemy pathfinding and it seems like it's working pretty well, but there are some questions I have. It seems to not be taking the shortest path to the target sometimes, like not taking a straight path to the target when there is nothing in the way. Here are a couple screenshots. I can give you my exact navmesh or whatever you might need for debugging if that helps, too.

In all these screenshots, the black mesh is my navmesh, the green line is the path identified by this library, and the red are my annotations on the screenshots. The blue radish is always trying to get to the cowbow dog.

Here we have a straight shot to the dog, but the radish wants to take a multi-segmented path to the dog.
Here it seems like the radish should have cut the corner a bit and taken the path along the red line, instead of going a a longer way around.

I'm using the highest accuracy modes while finding the path:

mesh.find_path(
    enemy_pos.into_nav(),
    character_pos.into_nav(),
    navmesh::NavQuery::Accuracy,
    navmesh::NavPathMode::Accuracy,
)

I'm wonding whether or not my nav mesh is too high resolution? Like maybe the algorithm expects there to be larger triangles filling the large open areas, instead of a bunch of small, tile-sized triangles?

I wanted to do a lower-resolution nav-mesh, but I'm generating the nav-mesh automatically by creating the triangle mesh and then using the physics engine to shape-cast along the eges and delete any triangles where I could not move an object the size of my enemy from one vertice to the other without hitting something. Using this strategy, I don't know what sort of algorithms or techniques that I could use to simplify the mesh geometry. It seems like I could do some sort of edge-collapsing or something, but I know nothing about the actual algorithms involved so I just tried using the high-res mesh without simplification.

PsichiX commented 3 years ago

hi! :D i had a lot of work today, let me answer all your questions and propose a solution tomorrow. just to want to let you know i've read them and gonna take a look at this problem ;D

PsichiX commented 3 years ago

i greatly apologize for not responding in a while, lots of work - anyway, during that time i've used my spare hours to test the crate on big scale scenarios and i've found what's wrong: altho broad phase searching thru triangles seems work fine except few rare cases, but the simplification of the path is broken in general and i'll be remaking it after i'm done with new oxygengine's renderer. sorry for the problems, solution will have to wait for some time :<

zicklag commented 3 years ago

It's no problem. :) I too got pretty busy and I don't need this solved right away, so don't worry about it.

PsichiX / navmesh

Solution Not always the Shortest Path #3