TheGrimsey / oxidized_navigation

A runtime Nav-Mesh generation plugin for Bevy Engine in Rust.
Apache License 2.0
169 stars 12 forks source link

Pathfinder algorithm avoids large triangles. #12

Open Jeff425 opened 1 year ago

Jeff425 commented 1 year ago

We have discussed this before @TheGrimsey but due to the pathfinder algorithm deciding the cost of a triangle based on mid-point to mid-point the algorithm will avoid large triangles in the navmesh if possible.

This can lead to suboptimal paths being chosen, the paths will still work but it will be obvious that there is a better path.

Below is an example of an agent choosing a much longer route due to the short route containing two large triangles

https://github.com/TheGrimsey/oxidized_navigation/assets/4962118/ab5eeec1-4d6a-4749-b01b-f2402dfba50b