search

godotengine / godot

Godot Engine – Multi-platform 2D and 3D game engine
https://godotengine.org
MIT License
91.13k stars 21.19k forks source link

Pathfinding doesn't produce shortest path on vertical surfaces #89700

Open lupuchard opened 8 months ago

lupuchard commented 8 months ago

Tested versions

Tested in 4.2.1

System information

Godot v4.2.1.stable - Linux Mint 21.3 (Virginia) - X11 - Vulkan (Forward+) - dedicated NVIDIA GeForce GTX 1070 (nvidia; 545.29.06) - AMD Ryzen 5 3600 6-Core Processor (12 Threads)

Issue description

3D pathfinding doesn't seem to produce the shortest path when you have vertical surfaces, often snapping to corners instead of going directly to the destination. path1 path2 This is using NavigationServer3D.map_get_path with optimized=true (but results are similar with optimized=false). The navigation mesh was made in blender since it doesn't seem to be possible to bake a navigation mesh with vertical surfaces.

Steps to reproduce

  1. Make a navigation mesh with some vertical surfaces.
  2. Call NavigationServer3D.map_get_path between two points on walls.
  3. Observe results.

Minimal reproduction project (MRP)

aaru-minimal.zip

smix8 commented 8 months ago

Make a navigation mesh with some vertical surfaces.

No because it is not supported.

A navigation mesh is a resource, it has no transform, it always needs to face towards the default up vector, hence why it is also not supported in any other way by the baking.

What can be changed are the region transforms and the navigation map up vector but not the mesh.

The regions still need to stay within an angular limit towards the current navigation map up or else things will start to break.

nav_mesh_orientation

lupuchard commented 8 months ago

No because it is not supported.

Ah ok. I didn't see this restriction documented. Is this because the 3D pathfinding is actually like 2D but projected onto a 3D surface or something?

For my use case, I don't think simply rotating the up vector would work since the nav mesh connects together all the walls and the floor.

smix8 commented 8 months ago

Is this because the 3D pathfinding is actually like 2D but projected onto a 3D surface or something?

The two-dimensional navmesh surfaces can still be layered in 3D, they just can not overlap or intersect.

The baking is done with a voxel grid using span logic and y-axis aligned layers so it is a technical limit that it can not be rotated.

The pathfinding has calculations where vertical overlap starts to break things e.g. with path clipping or angles. That is why the orientation of all navmesh surfaces can not be rotated at or over 90° away from the navigatio map up.

Now having pathfinding for ground, wall and ceiliing is possible, just not with the default NavigationAgent. You basically use a navigation map for each major orientation and a waypoint system, e.g. AStar3D, for the general path.

Query the general path with the waypoints and the more detailed path from the navigation map that fits the current waypoint orientation.