[TRACKER] Navigation test plan

[Scony]

In the upcoming weeks, I'm going to work on test cases for the navigation area. I'm going to use this issue as a progress tracker but also as a place where anyone can propose scenarios to implement.

Please note that many scenarios will be tested in 3D only since quite a lot of navigation code is common for 2D and 3D so we don't need to duplicate test cases in many instances.

Server tests

NavigationServer3D

General

• [x] Server should be empty when initialized - checking if the internal state of server is correct after initialization
• [x] Server should release valid RIDs

Agent

• [x] Server should create a valid agent
• [x] Server should not report dangling agent in ProcessInfo
• [x] Server should not report removed agent in ProcessInfo
• [x] Server should report agent with active map in ProcessInfo
• [x] Server should be able to set/get basic agent params
• [ ] Server should be able to set/get all agent's params
• [ ] (...)

Map

• [x] Server should create a valid map
• [x] Server should yield default values in response to queries against empty map
• [x] Server should report active map in ProcessInfo
• [x] Server should not report active map in ProcessInfo
• [x] Server should be able to set/get all map's params
• [x] Server should report correct number of map's agents
• [x] Server should report correct number of map's obstacles
• [x] Server should report correct number of map's links
• [x] Server should report correct number of map's regions
• [ ] Server should emit map_changed
• [ ] Server should emit navigation_debug_changed
• [ ] (...)

Link

• [x] Server should create valid link
• [x] Server should not report dangling link in ProcessInfo
• [x] Server should report link with active map in ProcessInfo
• [x] Server should be able to set/get all link's params
• [ ] (...)

Region

• [x] Server should create valid region
• [x] Server should not report dangling region in ProcessInfo
• [x] Server should report region with active map in ProcessInfo
• [x] Server should yield default values in response to queries against empty region
• [ ] (...)

Obstacle

• [x] Server should create valid obstacle
• [ ] Server should be able to set/get all obstacle's params
• [ ] (...)

NavigationServer2D

• [x] Server should be empty when initialized - checking if the internal state of server is correct after initialization
• [ ] (...)

Node tests

NavigationRegion3D

• [x] New region should have valid RID
• [ ] Navigation region should bake navigation mesh correctly
• [ ] Navigation region should emit bake_finished
• [ ] Navigation region should emit navigation_mesh_changed
• [ ] (...)

NavigationRegion2D

• [x] New region should have valid RID
• [ ] (...)

NavigationAgent3D

• [x] New agent should have valid RID
• [x] New agent should attach to default map
• [ ] (...)

NavigationAgent2D

• [x] New agent should have valid RID
• [x] New agent should attach to default map
• [ ] (...)

NavigationObstacle3D

• [x] New obstacle should have valid RID
• [x] New obstacle should attach to default map
• [ ] Obstacle estimates radius correctly
• [ ] Obstacle uses hardcoded radius if not estimated
• [ ] Obstacle changes navigation map correctly
• [ ] Obstacle is avoided by agent correctly
• [ ] (...)

NavigationObstacle2D

• [x] New obstacle should have valid RID
• [x] New obstacle should attach to default map
• [ ] Obstacle changes navigation map correctly
• [ ] Obstacle is avoided by agent correctly
• [ ] (...)

NavigationLink3D

• [ ] (...)

NavigationLink2D

• [ ] (...)

PRs

• https://github.com/godotengine/godot/pull/73121
• https://github.com/godotengine/godot/pull/73700
• https://github.com/godotengine/godot/pull/78449
• https://github.com/godotengine/godot/pull/78480
• https://github.com/godotengine/godot/pull/78667

This issue supplements https://github.com/godotengine/godot/issues/43440

[smix8]

Looking for navigation related benchmark ideas.

Benchmark ideas are written in format like this: TYPE: [Groups it Belongs]: Name: Description

Examples:

• Exclusive:AStar3D: Create random map with 1000 inter connected points (probably using Delaunay3D), Benchmark solving it 1000 times from random 2 points
• Exclusive:Navigation: On a premade map, solve 1000 random paths between two points on the surface of the shapes.
• Agents: Benchmark 1000 moving agents in a map with local collision avoidance.

[Scony]

Looking for navigation related benchmark ideas.

Benchmark ideas are written in format like this: TYPE: [Groups it Belongs]: Name: Description

Examples:

• Exclusive:AStar3D: Create random map with 1000 inter connected points (probably using Delaunay3D), Benchmark solving it 1000 times from random 2 points
• Exclusive:Navigation: On a premade map, solve 1000 random paths between two points on the surface of the shapes.
• Agents: Benchmark 1000 moving agents in a map with local collision avoidance.

Some more examples to consider:

• Exclusive:Navigation[Agents]: Benchmark 10 maps with 100 moving agents each and with local collision avoidance.
• Exclusive:Navigation[Agents]: Benchmark 100 maps with 10 moving agents each and with local collision avoidance.
• Exclusive:Navigation[Agents]: Benchmark 1000 moving agents in a map with local collision avoidance and with 100 triangular, static obstacles spread across the map.
• Exclusive:Navigation[Agents/Queries]: Benchmark 1000 moving agents in a map with local collision avoidance while changing desired location (path recalculation) for 100 of them every second for 10 seconds.