summaryrefslogtreecommitdiffstats
path: root/modules/navigation
diff options
context:
space:
mode:
Diffstat (limited to 'modules/navigation')
-rw-r--r--modules/navigation/godot_navigation_server.cpp14
-rw-r--r--modules/navigation/godot_navigation_server.h3
-rw-r--r--modules/navigation/godot_navigation_server_2d.cpp11
-rw-r--r--modules/navigation/godot_navigation_server_2d.h2
-rw-r--r--modules/navigation/nav_map.cpp81
-rw-r--r--modules/navigation/nav_map.h2
-rw-r--r--modules/navigation/nav_mesh_generator_2d.cpp14
-rw-r--r--modules/navigation/nav_region.cpp140
-rw-r--r--modules/navigation/nav_region.h6
-rw-r--r--modules/navigation/nav_utils.h2
10 files changed, 256 insertions, 19 deletions
diff --git a/modules/navigation/godot_navigation_server.cpp b/modules/navigation/godot_navigation_server.cpp
index 6a3bf6793e..5a28f8b8ef 100644
--- a/modules/navigation/godot_navigation_server.cpp
+++ b/modules/navigation/godot_navigation_server.cpp
@@ -331,6 +331,13 @@ RID GodotNavigationServer::agent_get_map(RID p_agent) const {
return RID();
}
+Vector3 GodotNavigationServer::map_get_random_point(RID p_map, uint32_t p_navigation_layers, bool p_uniformly) const {
+ const NavMap *map = map_owner.get_or_null(p_map);
+ ERR_FAIL_NULL_V(map, Vector3());
+
+ return map->get_random_point(p_navigation_layers, p_uniformly);
+}
+
RID GodotNavigationServer::region_create() {
MutexLock lock(operations_mutex);
@@ -498,6 +505,13 @@ Vector3 GodotNavigationServer::region_get_connection_pathway_end(RID p_region, i
return region->get_connection_pathway_end(p_connection_id);
}
+Vector3 GodotNavigationServer::region_get_random_point(RID p_region, uint32_t p_navigation_layers, bool p_uniformly) const {
+ const NavRegion *region = region_owner.get_or_null(p_region);
+ ERR_FAIL_NULL_V(region, Vector3());
+
+ return region->get_random_point(p_navigation_layers, p_uniformly);
+}
+
RID GodotNavigationServer::link_create() {
MutexLock lock(operations_mutex);
diff --git a/modules/navigation/godot_navigation_server.h b/modules/navigation/godot_navigation_server.h
index 4ead4fc398..3a76f83b09 100644
--- a/modules/navigation/godot_navigation_server.h
+++ b/modules/navigation/godot_navigation_server.h
@@ -140,6 +140,8 @@ public:
virtual void map_force_update(RID p_map) override;
+ virtual Vector3 map_get_random_point(RID p_map, uint32_t p_navigation_layers, bool p_uniformly) const override;
+
virtual RID region_create() override;
COMMAND_2(region_set_enabled, RID, p_region, bool, p_enabled);
@@ -170,6 +172,7 @@ public:
virtual int region_get_connections_count(RID p_region) const override;
virtual Vector3 region_get_connection_pathway_start(RID p_region, int p_connection_id) const override;
virtual Vector3 region_get_connection_pathway_end(RID p_region, int p_connection_id) const override;
+ virtual Vector3 region_get_random_point(RID p_region, uint32_t p_navigation_layers, bool p_uniformly) const override;
virtual RID link_create() override;
COMMAND_2(link_set_map, RID, p_link, RID, p_map);
diff --git a/modules/navigation/godot_navigation_server_2d.cpp b/modules/navigation/godot_navigation_server_2d.cpp
index b54729e06f..142d6181a1 100644
--- a/modules/navigation/godot_navigation_server_2d.cpp
+++ b/modules/navigation/godot_navigation_server_2d.cpp
@@ -259,8 +259,12 @@ Vector<Vector2> FORWARD_5_R_C(vector_v3_to_v2, map_get_path, RID, p_map, Vector2
Vector2 FORWARD_2_R_C(v3_to_v2, map_get_closest_point, RID, p_map, const Vector2 &, p_point, rid_to_rid, v2_to_v3);
RID FORWARD_2_C(map_get_closest_point_owner, RID, p_map, const Vector2 &, p_point, rid_to_rid, v2_to_v3);
-RID FORWARD_0(region_create);
+Vector2 GodotNavigationServer2D::map_get_random_point(RID p_map, uint32_t p_naviation_layers, bool p_uniformly) const {
+ Vector3 result = NavigationServer3D::get_singleton()->map_get_random_point(p_map, p_naviation_layers, p_uniformly);
+ return v3_to_v2(result);
+}
+RID FORWARD_0(region_create);
void FORWARD_2(region_set_enabled, RID, p_region, bool, p_enabled, rid_to_rid, bool_to_bool);
bool FORWARD_1_C(region_get_enabled, RID, p_region, rid_to_rid);
void FORWARD_2(region_set_use_edge_connections, RID, p_region, bool, p_enabled, rid_to_rid, bool_to_bool);
@@ -287,6 +291,11 @@ int FORWARD_1_C(region_get_connections_count, RID, p_region, rid_to_rid);
Vector2 FORWARD_2_R_C(v3_to_v2, region_get_connection_pathway_start, RID, p_region, int, p_connection_id, rid_to_rid, int_to_int);
Vector2 FORWARD_2_R_C(v3_to_v2, region_get_connection_pathway_end, RID, p_region, int, p_connection_id, rid_to_rid, int_to_int);
+Vector2 GodotNavigationServer2D::region_get_random_point(RID p_region, uint32_t p_navigation_layers, bool p_uniformly) const {
+ Vector3 result = NavigationServer3D::get_singleton()->region_get_random_point(p_region, p_navigation_layers, p_uniformly);
+ return v3_to_v2(result);
+}
+
RID FORWARD_0(link_create);
void FORWARD_2(link_set_map, RID, p_link, RID, p_map, rid_to_rid, rid_to_rid);
diff --git a/modules/navigation/godot_navigation_server_2d.h b/modules/navigation/godot_navigation_server_2d.h
index 337f5f40d8..88dee0ce69 100644
--- a/modules/navigation/godot_navigation_server_2d.h
+++ b/modules/navigation/godot_navigation_server_2d.h
@@ -76,6 +76,7 @@ public:
virtual TypedArray<RID> map_get_agents(RID p_map) const override;
virtual TypedArray<RID> map_get_obstacles(RID p_map) const override;
virtual void map_force_update(RID p_map) override;
+ virtual Vector2 map_get_random_point(RID p_map, uint32_t p_navigation_layers, bool p_uniformly) const override;
virtual RID region_create() override;
virtual void region_set_enabled(RID p_region, bool p_enabled) override;
@@ -98,6 +99,7 @@ public:
virtual int region_get_connections_count(RID p_region) const override;
virtual Vector2 region_get_connection_pathway_start(RID p_region, int p_connection_id) const override;
virtual Vector2 region_get_connection_pathway_end(RID p_region, int p_connection_id) const override;
+ virtual Vector2 region_get_random_point(RID p_region, uint32_t p_navigation_layers, bool p_uniformly) const override;
virtual RID link_create() override;
diff --git a/modules/navigation/nav_map.cpp b/modules/navigation/nav_map.cpp
index 5ef0298eb4..3b875b7fa7 100644
--- a/modules/navigation/nav_map.cpp
+++ b/modules/navigation/nav_map.cpp
@@ -769,6 +769,70 @@ void NavMap::remove_agent_as_controlled(NavAgent *agent) {
}
}
+Vector3 NavMap::get_random_point(uint32_t p_navigation_layers, bool p_uniformly) const {
+ const LocalVector<NavRegion *> map_regions = get_regions();
+
+ if (map_regions.is_empty()) {
+ return Vector3();
+ }
+
+ LocalVector<const NavRegion *> accessible_regions;
+
+ for (const NavRegion *region : map_regions) {
+ if (!region->get_enabled() || (p_navigation_layers & region->get_navigation_layers()) == 0) {
+ continue;
+ }
+ accessible_regions.push_back(region);
+ }
+
+ if (accessible_regions.is_empty()) {
+ // All existing region polygons are disabled.
+ return Vector3();
+ }
+
+ if (p_uniformly) {
+ real_t accumulated_region_surface_area = 0;
+ RBMap<real_t, uint32_t> accessible_regions_area_map;
+
+ for (uint32_t accessible_region_index = 0; accessible_region_index < accessible_regions.size(); accessible_region_index++) {
+ const NavRegion *region = accessible_regions[accessible_region_index];
+
+ real_t region_surface_area = region->get_surface_area();
+
+ if (region_surface_area == 0.0f) {
+ continue;
+ }
+
+ accessible_regions_area_map[accumulated_region_surface_area] = accessible_region_index;
+ accumulated_region_surface_area += region_surface_area;
+ }
+ if (accessible_regions_area_map.is_empty() || accumulated_region_surface_area == 0) {
+ // All faces have no real surface / no area.
+ return Vector3();
+ }
+
+ real_t random_accessible_regions_area_map = Math::random(real_t(0), accumulated_region_surface_area);
+
+ RBMap<real_t, uint32_t>::Iterator E = accessible_regions_area_map.find_closest(random_accessible_regions_area_map);
+ ERR_FAIL_COND_V(!E, Vector3());
+ uint32_t random_region_index = E->value;
+ ERR_FAIL_UNSIGNED_INDEX_V(random_region_index, accessible_regions.size(), Vector3());
+
+ const NavRegion *random_region = accessible_regions[random_region_index];
+ ERR_FAIL_NULL_V(random_region, Vector3());
+
+ return random_region->get_random_point(p_navigation_layers, p_uniformly);
+
+ } else {
+ uint32_t random_region_index = Math::random(int(0), accessible_regions.size() - 1);
+
+ const NavRegion *random_region = accessible_regions[random_region_index];
+ ERR_FAIL_NULL_V(random_region, Vector3());
+
+ return random_region->get_random_point(p_navigation_layers, p_uniformly);
+ }
+}
+
void NavMap::sync() {
// Performance Monitor
int _new_pm_region_count = regions.size();
@@ -1107,8 +1171,14 @@ void NavMap::_update_rvo_obstacles_tree_2d() {
obstacle_vertex_count += obstacle->get_vertices().size();
}
+ // Cleaning old obstacles.
+ for (size_t i = 0; i < rvo_simulation_2d.obstacles_.size(); ++i) {
+ delete rvo_simulation_2d.obstacles_[i];
+ }
+ rvo_simulation_2d.obstacles_.clear();
+
// Cannot use LocalVector here as RVO library expects std::vector to build KdTree
- std::vector<RVO2D::Obstacle2D *> raw_obstacles;
+ std::vector<RVO2D::Obstacle2D *> &raw_obstacles = rvo_simulation_2d.obstacles_;
raw_obstacles.reserve(obstacle_vertex_count);
// The following block is modified copy from RVO2D::AddObstacle()
@@ -1125,8 +1195,14 @@ void NavMap::_update_rvo_obstacles_tree_2d() {
rvo_2d_vertices.reserve(_obstacle_vertices.size());
uint32_t _obstacle_avoidance_layers = obstacle->get_avoidance_layers();
+ real_t _obstacle_height = obstacle->get_height();
for (const Vector3 &_obstacle_vertex : _obstacle_vertices) {
+#ifdef TOOLS_ENABLED
+ if (_obstacle_vertex.y != 0) {
+ WARN_PRINT_ONCE("Y coordinates of static obstacle vertices are ignored. Please use obstacle position Y to change elevation of obstacle.");
+ }
+#endif
rvo_2d_vertices.push_back(RVO2D::Vector2(_obstacle_vertex.x + _obstacle_position.x, _obstacle_vertex.z + _obstacle_position.z));
}
@@ -1135,6 +1211,9 @@ void NavMap::_update_rvo_obstacles_tree_2d() {
for (size_t i = 0; i < rvo_2d_vertices.size(); i++) {
RVO2D::Obstacle2D *rvo_2d_obstacle = new RVO2D::Obstacle2D();
rvo_2d_obstacle->point_ = rvo_2d_vertices[i];
+ rvo_2d_obstacle->height_ = _obstacle_height;
+ rvo_2d_obstacle->elevation_ = _obstacle_position.y;
+
rvo_2d_obstacle->avoidance_layers_ = _obstacle_avoidance_layers;
if (i != 0) {
diff --git a/modules/navigation/nav_map.h b/modules/navigation/nav_map.h
index 5d78c14627..e8cbe7e247 100644
--- a/modules/navigation/nav_map.h
+++ b/modules/navigation/nav_map.h
@@ -190,6 +190,8 @@ public:
return map_update_id;
}
+ Vector3 get_random_point(uint32_t p_navigation_layers, bool p_uniformly) const;
+
void sync();
void step(real_t p_deltatime);
void dispatch_callbacks();
diff --git a/modules/navigation/nav_mesh_generator_2d.cpp b/modules/navigation/nav_mesh_generator_2d.cpp
index f8c12935b4..6dfafa4e91 100644
--- a/modules/navigation/nav_mesh_generator_2d.cpp
+++ b/modules/navigation/nav_mesh_generator_2d.cpp
@@ -591,13 +591,19 @@ void NavMeshGenerator2D::generator_parse_tilemap_node(const Ref<NavigationPolygo
continue;
}
+ // Transform flags.
+ const int alternative_id = tilemap->get_cell_alternative_tile(tilemap_layer, cell, false);
+ bool flip_h = (alternative_id & TileSetAtlasSource::TRANSFORM_FLIP_H);
+ bool flip_v = (alternative_id & TileSetAtlasSource::TRANSFORM_FLIP_V);
+ bool transpose = (alternative_id & TileSetAtlasSource::TRANSFORM_TRANSPOSE);
+
Transform2D tile_transform;
tile_transform.set_origin(tilemap->map_to_local(cell));
const Transform2D tile_transform_offset = tilemap_xform * tile_transform;
if (navigation_layers_count > 0) {
- Ref<NavigationPolygon> navigation_polygon = tile_data->get_navigation_polygon(tilemap_layer);
+ Ref<NavigationPolygon> navigation_polygon = tile_data->get_navigation_polygon(tilemap_layer, flip_h, flip_v, transpose);
if (navigation_polygon.is_valid()) {
for (int outline_index = 0; outline_index < navigation_polygon->get_outline_count(); outline_index++) {
const Vector<Vector2> &navigation_polygon_outline = navigation_polygon->get_outline(outline_index);
@@ -622,11 +628,15 @@ void NavMeshGenerator2D::generator_parse_tilemap_node(const Ref<NavigationPolygo
if (physics_layers_count > 0 && (parsed_geometry_type == NavigationPolygon::PARSED_GEOMETRY_STATIC_COLLIDERS || parsed_geometry_type == NavigationPolygon::PARSED_GEOMETRY_BOTH) && (tile_set->get_physics_layer_collision_layer(tilemap_layer) & parsed_collision_mask)) {
for (int collision_polygon_index = 0; collision_polygon_index < tile_data->get_collision_polygons_count(tilemap_layer); collision_polygon_index++) {
- const Vector<Vector2> &collision_polygon_points = tile_data->get_collision_polygon_points(tilemap_layer, collision_polygon_index);
+ PackedVector2Array collision_polygon_points = tile_data->get_collision_polygon_points(tilemap_layer, collision_polygon_index);
if (collision_polygon_points.size() == 0) {
continue;
}
+ if (flip_h || flip_v || transpose) {
+ collision_polygon_points = TileData::get_transformed_vertices(collision_polygon_points, flip_h, flip_v, transpose);
+ }
+
Vector<Vector2> obstruction_outline;
obstruction_outline.resize(collision_polygon_points.size());
diff --git a/modules/navigation/nav_region.cpp b/modules/navigation/nav_region.cpp
index 09697c7be0..9cb235d79f 100644
--- a/modules/navigation/nav_region.cpp
+++ b/modules/navigation/nav_region.cpp
@@ -100,6 +100,88 @@ Vector3 NavRegion::get_connection_pathway_end(int p_connection_id) const {
return connections[p_connection_id].pathway_end;
}
+Vector3 NavRegion::get_random_point(uint32_t p_navigation_layers, bool p_uniformly) const {
+ if (!get_enabled()) {
+ return Vector3();
+ }
+
+ const LocalVector<gd::Polygon> &region_polygons = get_polygons();
+
+ if (region_polygons.is_empty()) {
+ return Vector3();
+ }
+
+ if (p_uniformly) {
+ real_t accumulated_area = 0;
+ RBMap<real_t, uint32_t> region_area_map;
+
+ for (uint32_t rp_index = 0; rp_index < region_polygons.size(); rp_index++) {
+ const gd::Polygon &region_polygon = region_polygons[rp_index];
+ real_t polyon_area = region_polygon.surface_area;
+
+ if (polyon_area == 0.0) {
+ continue;
+ }
+ region_area_map[accumulated_area] = rp_index;
+ accumulated_area += polyon_area;
+ }
+ if (region_area_map.is_empty() || accumulated_area == 0) {
+ // All polygons have no real surface / no area.
+ return Vector3();
+ }
+
+ real_t region_area_map_pos = Math::random(real_t(0), accumulated_area);
+
+ RBMap<real_t, uint32_t>::Iterator region_E = region_area_map.find_closest(region_area_map_pos);
+ ERR_FAIL_COND_V(!region_E, Vector3());
+ uint32_t rrp_polygon_index = region_E->value;
+ ERR_FAIL_UNSIGNED_INDEX_V(rrp_polygon_index, region_polygons.size(), Vector3());
+
+ const gd::Polygon &rr_polygon = region_polygons[rrp_polygon_index];
+
+ real_t accumulated_polygon_area = 0;
+ RBMap<real_t, uint32_t> polygon_area_map;
+
+ for (uint32_t rpp_index = 2; rpp_index < rr_polygon.points.size(); rpp_index++) {
+ real_t face_area = Face3(rr_polygon.points[0].pos, rr_polygon.points[rpp_index - 1].pos, rr_polygon.points[rpp_index].pos).get_area();
+
+ if (face_area == 0.0) {
+ continue;
+ }
+ polygon_area_map[accumulated_polygon_area] = rpp_index;
+ accumulated_polygon_area += face_area;
+ }
+ if (polygon_area_map.is_empty() || accumulated_polygon_area == 0) {
+ // All faces have no real surface / no area.
+ return Vector3();
+ }
+
+ real_t polygon_area_map_pos = Math::random(real_t(0), accumulated_polygon_area);
+
+ RBMap<real_t, uint32_t>::Iterator polygon_E = polygon_area_map.find_closest(polygon_area_map_pos);
+ ERR_FAIL_COND_V(!polygon_E, Vector3());
+ uint32_t rrp_face_index = polygon_E->value;
+ ERR_FAIL_UNSIGNED_INDEX_V(rrp_face_index, rr_polygon.points.size(), Vector3());
+
+ const Face3 face(rr_polygon.points[0].pos, rr_polygon.points[rrp_face_index - 1].pos, rr_polygon.points[rrp_face_index].pos);
+
+ Vector3 face_random_position = face.get_random_point_inside();
+ return face_random_position;
+
+ } else {
+ uint32_t rrp_polygon_index = Math::random(int(0), region_polygons.size() - 1);
+
+ const gd::Polygon &rr_polygon = region_polygons[rrp_polygon_index];
+
+ uint32_t rrp_face_index = Math::random(int(2), rr_polygon.points.size() - 1);
+
+ const Face3 face(rr_polygon.points[0].pos, rr_polygon.points[rrp_face_index - 1].pos, rr_polygon.points[rrp_face_index].pos);
+
+ Vector3 face_random_position = face.get_random_point_inside();
+ return face_random_position;
+ }
+}
+
bool NavRegion::sync() {
bool something_changed = polygons_dirty /* || something_dirty? */;
@@ -113,6 +195,7 @@ void NavRegion::update_polygons() {
return;
}
polygons.clear();
+ surface_area = 0.0;
polygons_dirty = false;
if (map == nullptr) {
@@ -147,21 +230,46 @@ void NavRegion::update_polygons() {
polygons.resize(mesh->get_polygon_count());
+ real_t _new_region_surface_area = 0.0;
+
// Build
- for (size_t i(0); i < polygons.size(); i++) {
- gd::Polygon &p = polygons[i];
- p.owner = this;
+ int navigation_mesh_polygon_index = 0;
+ for (gd::Polygon &polygon : polygons) {
+ polygon.owner = this;
+ polygon.surface_area = 0.0;
- Vector<int> mesh_poly = mesh->get_polygon(i);
- const int *indices = mesh_poly.ptr();
+ Vector<int> navigation_mesh_polygon = mesh->get_polygon(navigation_mesh_polygon_index);
+ navigation_mesh_polygon_index += 1;
+
+ int navigation_mesh_polygon_size = navigation_mesh_polygon.size();
+ if (navigation_mesh_polygon_size < 3) {
+ continue;
+ }
+
+ const int *indices = navigation_mesh_polygon.ptr();
bool valid(true);
- p.points.resize(mesh_poly.size());
- p.edges.resize(mesh_poly.size());
- Vector3 center;
+ polygon.points.resize(navigation_mesh_polygon_size);
+ polygon.edges.resize(navigation_mesh_polygon_size);
+
+ real_t _new_polygon_surface_area = 0.0;
+
+ for (int j(2); j < navigation_mesh_polygon_size; j++) {
+ const Face3 face = Face3(
+ transform.xform(vertices_r[indices[0]]),
+ transform.xform(vertices_r[indices[j - 1]]),
+ transform.xform(vertices_r[indices[j]]));
+
+ _new_polygon_surface_area += face.get_area();
+ }
+
+ polygon.surface_area = _new_polygon_surface_area;
+ _new_region_surface_area += _new_polygon_surface_area;
+
+ Vector3 polygon_center;
real_t sum(0);
- for (int j(0); j < mesh_poly.size(); j++) {
+ for (int j(0); j < navigation_mesh_polygon_size; j++) {
int idx = indices[j];
if (idx < 0 || idx >= len) {
valid = false;
@@ -169,10 +277,10 @@ void NavRegion::update_polygons() {
}
Vector3 point_position = transform.xform(vertices_r[idx]);
- p.points[j].pos = point_position;
- p.points[j].key = map->get_point_key(point_position);
+ polygon.points[j].pos = point_position;
+ polygon.points[j].key = map->get_point_key(point_position);
- center += point_position; // Composing the center of the polygon
+ polygon_center += point_position; // Composing the center of the polygon
if (j >= 2) {
Vector3 epa = transform.xform(vertices_r[indices[j - 2]]);
@@ -186,9 +294,11 @@ void NavRegion::update_polygons() {
ERR_BREAK_MSG(!valid, "The navigation mesh set in this region is not valid!");
}
- p.clockwise = sum > 0;
- if (mesh_poly.size() != 0) {
- p.center = center / real_t(mesh_poly.size());
+ polygon.clockwise = sum > 0;
+ if (!navigation_mesh_polygon.is_empty()) {
+ polygon.center = polygon_center / real_t(navigation_mesh_polygon.size());
}
}
+
+ surface_area = _new_region_surface_area;
}
diff --git a/modules/navigation/nav_region.h b/modules/navigation/nav_region.h
index 6a8ebe5336..a9cfc53c7e 100644
--- a/modules/navigation/nav_region.h
+++ b/modules/navigation/nav_region.h
@@ -50,6 +50,8 @@ class NavRegion : public NavBase {
/// Cache
LocalVector<gd::Polygon> polygons;
+ real_t surface_area = 0.0;
+
public:
NavRegion() {
type = NavigationUtilities::PathSegmentType::PATH_SEGMENT_TYPE_REGION;
@@ -93,6 +95,10 @@ public:
return polygons;
}
+ Vector3 get_random_point(uint32_t p_navigation_layers, bool p_uniformly) const;
+
+ real_t get_surface_area() const { return surface_area; };
+
bool sync();
private:
diff --git a/modules/navigation/nav_utils.h b/modules/navigation/nav_utils.h
index 6ddd8b9078..aa5ccc96dc 100644
--- a/modules/navigation/nav_utils.h
+++ b/modules/navigation/nav_utils.h
@@ -112,6 +112,8 @@ struct Polygon {
/// The center of this `Polygon`
Vector3 center;
+
+ real_t surface_area = 0.0;
};
struct NavigationPoly {