Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NavigationAgent2D gives incorrect path #74696

Closed
JustMog opened this issue Mar 10, 2023 · 7 comments · Fixed by #79228
Closed

NavigationAgent2D gives incorrect path #74696

JustMog opened this issue Mar 10, 2023 · 7 comments · Fixed by #79228

Comments

@JustMog
Copy link

JustMog commented Mar 10, 2023

Godot version

v4.0.stable.official [92bee43]

System information

windows 10

Issue description

best explained with pictures:
image
precise position of target:
image
as you can see, when the target is on the seam between triangles that runs from one hole to another, the path gains an erroneous point at the corner of one of the holes, before doubling back to the target.
only happens at very precise target positions.

seems related to #67480. hopefully the more minimal repro can be of help.

Steps to reproduce

run repro project, enable visible navigation, and try to position the mouse as shown in the above image.
i tried printing out the mouse position when the bug was occurring and setting the target to that value, but wasn't able to reproduce the bug that way.

Minimal reproduction project

bug.zip

@smix8
Copy link
Contributor

smix8 commented Mar 12, 2023

The 4th and unwanted path point is added by the path postprocessing corridorfunnel.

@smix8
Copy link
Contributor

smix8 commented Mar 13, 2023

Fixed in an internal build scheduled for the pathfinding rework.

postprocessing_fix

@MajikalExplosions
Copy link

Hi! I'm facing this issue too; glad to see it's fixed. Is there a resource you could point to regarding the pathfinding rework? I can't seem to find any references to it, and as I'm working on a small project that uses Godot navigation, I was hoping to get an idea about how much will be changing so that I don't waste (too much) time learning a possibly obsolete API.

@MajikalExplosions
Copy link

Nevermind; I think this is it? #73566

@smix8
Copy link
Contributor

smix8 commented Mar 30, 2023

@MajikalExplosions It is internal and not public yet. It also consists primarily of internal changes to the NavigationServer and not changes to the user interaction with the navigation system and API. You don't need to worry about it for your project.

@smix8 smix8 added this to the 4.x milestone May 26, 2023
@smix8
Copy link
Contributor

smix8 commented May 26, 2023

I mentioned before that this was fixed in an internal build, and while it was for those particular situations, it now still shows up randomly in some other rare constellations. Fixing it for one case will shift it to another as at core it is a precision issue where the dot products used in the corridorfunnel just end up with a result that is technically "correct" but that does not match with what is expected.

As mentioned before the main issue is that the corridorfunnel postprocessing is designed for a triangulated mesh, which is the case in 3D but not always in 2D. I think what will happen at some point to truly solve this is that as soon as a single agent is requesting a path using the corridorfunnel postprocessing the navigation map will make sure that all navmeshes on the map are triangulated for the user. Because doing a lot of extra calculations on each single step in the postprocessing is worse for performance than having a few extra polygon edges.

@smix8
Copy link
Contributor

smix8 commented Jul 9, 2023

@JustMog @MajikalExplosions
If you are still around please try to test the linked pr #79228 to confirm if it fixes the issue.

@smix8 smix8 self-assigned this Jul 9, 2023
@YuriSizov YuriSizov modified the milestones: 4.x, 4.2 Aug 2, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants