diff options
Diffstat (limited to 'modules/navigation/nav_region.cpp')
| -rw-r--r-- | modules/navigation/nav_region.cpp | 140 |
1 files changed, 125 insertions, 15 deletions
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> ®ion_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 ®ion_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; } |