andriyDev / landmass

A navigation system for video games written in Rust.
Apache License 2.0
14 stars 1 forks source link

Exit early from pathfinding when nodes are not connected. #34

Closed andriyDev closed 3 weeks ago

andriyDev commented 3 weeks ago

Previously if two nodes had no path between them, the search would look through the entire connected graph before giving up. Now, if there is no path, we immediately exit!

This still leaves open the door that if there is a path, but one that takes a very long detour, the search could explore nearly all of the graph before finding any path at all. Another problem is that if there is no path, agents will just sit and do nothing. Instead, we may want to find a path getting "close" to the target, and follow that. Regardless, this is a good first step and something we likely always want to support.

This is part of #6.

codecov-commenter commented 3 weeks ago

Codecov Report

Attention: Patch coverage is 98.85714% with 2 lines in your changes missing coverage. Please review.

Project coverage is 98.3%. Comparing base (c3cc143) to head (cd1373d).

Additional details and impacted files | [Files](https://app.codecov.io/gh/andriyDev/landmass/pull/34?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | | |---|---|---| | [src/nav\_mesh.rs](https://app.codecov.io/gh/andriyDev/landmass/pull/34?src=pr&el=tree&filepath=src%2Fnav_mesh.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL25hdl9tZXNoLnJz) | `99.5% <100.0%> (+<0.1%)` | :arrow_up: | | [src/nav\_mesh\_test.rs](https://app.codecov.io/gh/andriyDev/landmass/pull/34?src=pr&el=tree&filepath=src%2Fnav_mesh_test.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL25hdl9tZXNoX3Rlc3QucnM=) | `96.1% <100.0%> (+0.3%)` | :arrow_up: | | [src/pathfinding.rs](https://app.codecov.io/gh/andriyDev/landmass/pull/34?src=pr&el=tree&filepath=src%2Fpathfinding.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL3BhdGhmaW5kaW5nLnJz) | `100.0% <100.0%> (ø)` | | | [src/nav\_data.rs](https://app.codecov.io/gh/andriyDev/landmass/pull/34?src=pr&el=tree&filepath=src%2Fnav_data.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL25hdl9kYXRhLnJz) | `99.3% <98.2%> (-0.2%)` | :arrow_down: | | [src/pathfinding\_test.rs](https://app.codecov.io/gh/andriyDev/landmass/pull/34?src=pr&el=tree&filepath=src%2Fpathfinding_test.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL3BhdGhmaW5kaW5nX3Rlc3QucnM=) | `99.7% <98.2%> (-0.3%)` | :arrow_down: |