summaryrefslogtreecommitdiff
path: root/modules/navigation/nav_map.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'modules/navigation/nav_map.cpp')
-rw-r--r--modules/navigation/nav_map.cpp170
1 files changed, 96 insertions, 74 deletions
diff --git a/modules/navigation/nav_map.cpp b/modules/navigation/nav_map.cpp
index 8d58c9335d..b1674c8fc5 100644
--- a/modules/navigation/nav_map.cpp
+++ b/modules/navigation/nav_map.cpp
@@ -1,39 +1,39 @@
-/*************************************************************************/
-/* nav_map.cpp */
-/*************************************************************************/
-/* This file is part of: */
-/* GODOT ENGINE */
-/* https://godotengine.org */
-/*************************************************************************/
-/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */
-/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */
-/* */
-/* Permission is hereby granted, free of charge, to any person obtaining */
-/* a copy of this software and associated documentation files (the */
-/* "Software"), to deal in the Software without restriction, including */
-/* without limitation the rights to use, copy, modify, merge, publish, */
-/* distribute, sublicense, and/or sell copies of the Software, and to */
-/* permit persons to whom the Software is furnished to do so, subject to */
-/* the following conditions: */
-/* */
-/* The above copyright notice and this permission notice shall be */
-/* included in all copies or substantial portions of the Software. */
-/* */
-/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
-/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
-/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
-/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
-/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
-/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
-/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
-/*************************************************************************/
+/**************************************************************************/
+/* nav_map.cpp */
+/**************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/**************************************************************************/
#include "nav_map.h"
#include "core/object/worker_thread_pool.h"
+#include "nav_agent.h"
#include "nav_link.h"
#include "nav_region.h"
-#include "rvo_agent.h"
#include <algorithm>
#define THREE_POINTS_CROSS_PRODUCT(m_a, m_b, m_c) (((m_c) - (m_a)).cross((m_b) - (m_a)))
@@ -103,9 +103,7 @@ Vector<Vector3> NavMap::get_path(Vector3 p_origin, Vector3 p_destination, bool p
float begin_d = 1e20;
float end_d = 1e20;
// Find the initial poly and the end poly on this map.
- for (size_t i(0); i < polygons.size(); i++) {
- const gd::Polygon &p = polygons[i];
-
+ for (const gd::Polygon &p : polygons) {
// Only consider the polygon if it in a region with compatible layers.
if ((p_navigation_layers & p.owner->get_navigation_layers()) == 0) {
continue;
@@ -190,9 +188,7 @@ Vector<Vector3> NavMap::get_path(Vector3 p_origin, Vector3 p_destination, bool p
while (true) {
// Takes the current least_cost_poly neighbors (iterating over its edges) and compute the traveled_distance.
- for (size_t i = 0; i < navigation_polys[least_cost_id].poly->edges.size(); i++) {
- const gd::Edge &edge = navigation_polys[least_cost_id].poly->edges[i];
-
+ for (const gd::Edge &edge : navigation_polys[least_cost_id].poly->edges) {
// Iterate over connections in this edge, then compute the new optimized travel distance assigned to this polygon.
for (int connection_index = 0; connection_index < edge.connections.size(); connection_index++) {
const gd::Edge::Connection &connection = edge.connections[connection_index];
@@ -229,7 +225,7 @@ Vector<Vector3> NavMap::get_path(Vector3 p_origin, Vector3 p_destination, bool p
avp.entry = new_entry;
}
} else {
- // Add the neighbour polygon to the reachable ones.
+ // Add the neighbor polygon to the reachable ones.
gd::NavigationPoly new_navigation_poly = gd::NavigationPoly(connection.polygon);
new_navigation_poly.self_id = navigation_polys.size();
new_navigation_poly.back_navigation_poly_id = least_cost_id;
@@ -240,7 +236,7 @@ Vector<Vector3> NavMap::get_path(Vector3 p_origin, Vector3 p_destination, bool p
new_navigation_poly.entry = new_entry;
navigation_polys.push_back(new_navigation_poly);
- // Add the neighbour polygon to the polygons to visit.
+ // Add the neighbor polygon to the polygons to visit.
to_visit.push_back(navigation_polys.size() - 1);
}
}
@@ -465,9 +461,7 @@ Vector3 NavMap::get_closest_point_to_segment(const Vector3 &p_from, const Vector
Vector3 closest_point;
real_t closest_point_d = 1e20;
- for (size_t i(0); i < polygons.size(); i++) {
- const gd::Polygon &p = polygons[i];
-
+ for (const gd::Polygon &p : polygons) {
// For each face check the distance to the segment
for (size_t point_id = 2; point_id < p.points.size(); point_id += 1) {
const Face3 f(p.points[0].pos, p.points[point_id - 1].pos, p.points[point_id].pos);
@@ -574,18 +568,18 @@ void NavMap::remove_link(NavLink *p_link) {
}
}
-bool NavMap::has_agent(RvoAgent *agent) const {
+bool NavMap::has_agent(NavAgent *agent) const {
return (agents.find(agent) != -1);
}
-void NavMap::add_agent(RvoAgent *agent) {
+void NavMap::add_agent(NavAgent *agent) {
if (!has_agent(agent)) {
agents.push_back(agent);
agents_dirty = true;
}
}
-void NavMap::remove_agent(RvoAgent *agent) {
+void NavMap::remove_agent(NavAgent *agent) {
remove_agent_as_controlled(agent);
int64_t agent_index = agents.find(agent);
if (agent_index != -1) {
@@ -594,7 +588,7 @@ void NavMap::remove_agent(RvoAgent *agent) {
}
}
-void NavMap::set_agent_as_controlled(RvoAgent *agent) {
+void NavMap::set_agent_as_controlled(NavAgent *agent) {
const bool exist = (controlled_agents.find(agent) != -1);
if (!exist) {
ERR_FAIL_COND(!has_agent(agent));
@@ -602,7 +596,7 @@ void NavMap::set_agent_as_controlled(RvoAgent *agent) {
}
}
-void NavMap::remove_agent_as_controlled(RvoAgent *agent) {
+void NavMap::remove_agent_as_controlled(NavAgent *agent) {
int64_t active_avoidance_agent_index = controlled_agents.find(agent);
if (active_avoidance_agent_index != -1) {
controlled_agents.remove_at_unordered(active_avoidance_agent_index);
@@ -611,54 +605,70 @@ void NavMap::remove_agent_as_controlled(RvoAgent *agent) {
}
void NavMap::sync() {
+ // Performance Monitor
+ int _new_pm_region_count = regions.size();
+ int _new_pm_agent_count = agents.size();
+ int _new_pm_link_count = links.size();
+ int _new_pm_polygon_count = pm_polygon_count;
+ int _new_pm_edge_count = pm_edge_count;
+ int _new_pm_edge_merge_count = pm_edge_merge_count;
+ int _new_pm_edge_connection_count = pm_edge_connection_count;
+ int _new_pm_edge_free_count = pm_edge_free_count;
+
// Check if we need to update the links.
if (regenerate_polygons) {
- for (uint32_t r = 0; r < regions.size(); r++) {
- regions[r]->scratch_polygons();
+ for (NavRegion *region : regions) {
+ region->scratch_polygons();
}
regenerate_links = true;
}
- for (uint32_t r = 0; r < regions.size(); r++) {
- if (regions[r]->sync()) {
+ for (NavRegion *region : regions) {
+ if (region->sync()) {
regenerate_links = true;
}
}
- for (uint32_t l = 0; l < links.size(); l++) {
- if (links[l]->check_dirty()) {
+ for (NavLink *link : links) {
+ if (link->check_dirty()) {
regenerate_links = true;
}
}
if (regenerate_links) {
+ _new_pm_polygon_count = 0;
+ _new_pm_edge_count = 0;
+ _new_pm_edge_merge_count = 0;
+ _new_pm_edge_connection_count = 0;
+ _new_pm_edge_free_count = 0;
+
// Remove regions connections.
- for (uint32_t r = 0; r < regions.size(); r++) {
- regions[r]->get_connections().clear();
+ for (NavRegion *region : regions) {
+ region->get_connections().clear();
}
// Resize the polygon count.
int count = 0;
- for (uint32_t r = 0; r < regions.size(); r++) {
- count += regions[r]->get_polygons().size();
+ for (const NavRegion *region : regions) {
+ count += region->get_polygons().size();
}
polygons.resize(count);
// Copy all region polygons in the map.
count = 0;
- for (uint32_t r = 0; r < regions.size(); r++) {
- const LocalVector<gd::Polygon> &polygons_source = regions[r]->get_polygons();
+ for (const NavRegion *region : regions) {
+ const LocalVector<gd::Polygon> &polygons_source = region->get_polygons();
for (uint32_t n = 0; n < polygons_source.size(); n++) {
polygons[count + n] = polygons_source[n];
}
- count += regions[r]->get_polygons().size();
+ count += region->get_polygons().size();
}
+ _new_pm_polygon_count = polygons.size();
+
// Group all edges per key.
HashMap<gd::EdgeKey, Vector<gd::Edge::Connection>, gd::EdgeKey> connections;
- for (uint32_t poly_id = 0; poly_id < polygons.size(); poly_id++) {
- gd::Polygon &poly(polygons[poly_id]);
-
+ for (gd::Polygon &poly : polygons) {
for (uint32_t p = 0; p < poly.points.size(); p++) {
int next_point = (p + 1) % poly.points.size();
gd::EdgeKey ek(poly.points[p].key, poly.points[next_point].key);
@@ -666,6 +676,7 @@ void NavMap::sync() {
HashMap<gd::EdgeKey, Vector<gd::Edge::Connection>, gd::EdgeKey>::Iterator connection = connections.find(ek);
if (!connection) {
connections[ek] = Vector<gd::Edge::Connection>();
+ _new_pm_edge_count += 1;
}
if (connections[ek].size() <= 1) {
// Add the polygon/edge tuple to this key.
@@ -691,6 +702,7 @@ void NavMap::sync() {
c1.polygon->edges[c1.edge].connections.push_back(c2);
c2.polygon->edges[c2.edge].connections.push_back(c1);
// Note: The pathway_start/end are full for those connection and do not need to be modified.
+ _new_pm_edge_merge_count += 1;
} else {
CRASH_COND_MSG(E.value.size() != 1, vformat("Number of connection != 1. Found: %d", E.value.size()));
free_edges.push_back(E.value[0]);
@@ -704,6 +716,8 @@ void NavMap::sync() {
// to be connected, create new polygons to remove that small gap is
// not really useful and would result in wasteful computation during
// connection, integration and path finding.
+ _new_pm_edge_free_count = free_edges.size();
+
for (int i = 0; i < free_edges.size(); i++) {
const gd::Edge::Connection &free_edge = free_edges[i];
Vector3 edge_p1 = free_edge.polygon->points[free_edge.edge].pos;
@@ -757,6 +771,7 @@ void NavMap::sync() {
// Add the connection to the region_connection map.
((NavRegion *)free_edge.polygon->owner)->get_connections().push_back(new_connection);
+ _new_pm_edge_connection_count += 1;
}
}
@@ -764,10 +779,9 @@ void NavMap::sync() {
link_polygons.resize(links.size());
// Search for polygons within range of a nav link.
- for (uint32_t l = 0; l < links.size(); l++) {
- const NavLink *link = links[l];
- const Vector3 start = link->get_start_location();
- const Vector3 end = link->get_end_location();
+ for (const NavLink *link : links) {
+ const Vector3 start = link->get_start_position();
+ const Vector3 end = link->get_end_position();
gd::Polygon *closest_start_polygon = nullptr;
real_t closest_start_distance = link_connection_radius;
@@ -797,9 +811,7 @@ void NavMap::sync() {
}
// Find any polygons within the search radius of the end point.
- for (uint32_t end_index = 0; end_index < polygons.size(); end_index++) {
- gd::Polygon &end_poly = polygons[end_index];
-
+ for (gd::Polygon &end_poly : polygons) {
// For each face check the distance to the end
for (uint32_t end_point_id = 2; end_point_id < end_poly.points.size(); end_point_id += 1) {
const Face3 end_face(end_poly.points[0].pos, end_poly.points[end_point_id - 1].pos, end_poly.points[end_point_id].pos);
@@ -883,8 +895,8 @@ void NavMap::sync() {
// cannot use LocalVector here as RVO library expects std::vector to build KdTree
std::vector<RVO::Agent *> raw_agents;
raw_agents.reserve(agents.size());
- for (size_t i(0); i < agents.size(); i++) {
- raw_agents.push_back(agents[i]->get_agent());
+ for (NavAgent *agent : agents) {
+ raw_agents.push_back(agent->get_agent());
}
rvo.buildAgentTree(raw_agents);
}
@@ -892,9 +904,19 @@ void NavMap::sync() {
regenerate_polygons = false;
regenerate_links = false;
agents_dirty = false;
+
+ // Performance Monitor
+ pm_region_count = _new_pm_region_count;
+ pm_agent_count = _new_pm_agent_count;
+ pm_link_count = _new_pm_link_count;
+ pm_polygon_count = _new_pm_polygon_count;
+ pm_edge_count = _new_pm_edge_count;
+ pm_edge_merge_count = _new_pm_edge_merge_count;
+ pm_edge_connection_count = _new_pm_edge_connection_count;
+ pm_edge_free_count = _new_pm_edge_free_count;
}
-void NavMap::compute_single_step(uint32_t index, RvoAgent **agent) {
+void NavMap::compute_single_step(uint32_t index, NavAgent **agent) {
(*(agent + index))->get_agent()->computeNeighbors(&rvo);
(*(agent + index))->get_agent()->computeNewVelocity(deltatime);
}
@@ -908,8 +930,8 @@ void NavMap::step(real_t p_deltatime) {
}
void NavMap::dispatch_callbacks() {
- for (int i(0); i < static_cast<int>(controlled_agents.size()); i++) {
- controlled_agents[i]->dispatch_callback();
+ for (NavAgent *agent : controlled_agents) {
+ agent->dispatch_callback();
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-05 09:46:21 +0000