summaryrefslogtreecommitdiffstats
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/a_star.compat.inc59
-rw-r--r--core/math/a_star.cpp65
-rw-r--r--core/math/a_star.h25
-rw-r--r--core/math/a_star_grid_2d.compat.inc48
-rw-r--r--core/math/a_star_grid_2d.cpp34
-rw-r--r--core/math/a_star_grid_2d.h15
-rw-r--r--core/math/aabb.h2
-rw-r--r--core/math/delaunay_3d.h12
-rw-r--r--core/math/dynamic_bvh.h9
-rw-r--r--core/math/geometry_2d.h6
-rw-r--r--core/math/projection.cpp7
-rw-r--r--core/math/projection.h2
-rw-r--r--core/math/random_pcg.cpp2
-rw-r--r--core/math/rect2.h14
-rw-r--r--core/math/rect2i.h14
-rw-r--r--core/math/transform_interpolator.cpp76
-rw-r--r--core/math/transform_interpolator.h46
17 files changed, 368 insertions, 68 deletions
diff --git a/core/math/a_star.compat.inc b/core/math/a_star.compat.inc
new file mode 100644
index 0000000000..664d7ffd5e
--- /dev/null
+++ b/core/math/a_star.compat.inc
@@ -0,0 +1,59 @@
+/**************************************************************************/
+/* a_star.compat.inc */
+/**************************************************************************/
+/* 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. */
+/**************************************************************************/
+
+#ifndef DISABLE_DEPRECATED
+
+Vector<int64_t> AStar3D::_get_id_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id) {
+ return get_id_path(p_from_id, p_to_id, false);
+}
+
+Vector<Vector3> AStar3D::_get_point_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id) {
+ return get_point_path(p_from_id, p_to_id, false);
+}
+
+void AStar3D::_bind_compatibility_methods() {
+ ClassDB::bind_compatibility_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar3D::_get_id_path_bind_compat_88047);
+ ClassDB::bind_compatibility_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar3D::_get_point_path_bind_compat_88047);
+}
+
+Vector<int64_t> AStar2D::_get_id_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id) {
+ return get_id_path(p_from_id, p_to_id, false);
+}
+
+Vector<Vector2> AStar2D::_get_point_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id) {
+ return get_point_path(p_from_id, p_to_id, false);
+}
+
+void AStar2D::_bind_compatibility_methods() {
+ ClassDB::bind_compatibility_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar2D::_get_id_path_bind_compat_88047);
+ ClassDB::bind_compatibility_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar2D::_get_point_path_bind_compat_88047);
+}
+
+#endif // DISABLE_DEPRECATED
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index fb54058bd9..4497604947 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -29,6 +29,7 @@
/**************************************************************************/
#include "a_star.h"
+#include "a_star.compat.inc"
#include "core/math/geometry_3d.h"
#include "core/object/script_language.h"
@@ -319,6 +320,7 @@ Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const {
}
bool AStar3D::_solve(Point *begin_point, Point *end_point) {
+ last_closest_point = nullptr;
pass++;
if (!end_point->enabled) {
@@ -332,11 +334,18 @@ bool AStar3D::_solve(Point *begin_point, Point *end_point) {
begin_point->g_score = 0;
begin_point->f_score = _estimate_cost(begin_point->id, end_point->id);
+ begin_point->abs_g_score = 0;
+ begin_point->abs_f_score = _estimate_cost(begin_point->id, end_point->id);
open_list.push_back(begin_point);
while (!open_list.is_empty()) {
Point *p = open_list[0]; // The currently processed point.
+ // Find point closer to end_point, or same distance to end_point but closer to begin_point.
+ if (last_closest_point == nullptr || last_closest_point->abs_f_score > p->abs_f_score || (last_closest_point->abs_f_score >= p->abs_f_score && last_closest_point->abs_g_score > p->abs_g_score)) {
+ last_closest_point = p;
+ }
+
if (p == end_point) {
found_route = true;
break;
@@ -368,6 +377,8 @@ bool AStar3D::_solve(Point *begin_point, Point *end_point) {
e->prev_point = p;
e->g_score = tentative_g_score;
e->f_score = e->g_score + _estimate_cost(e->id, end_point->id);
+ e->abs_g_score = tentative_g_score;
+ e->abs_f_score = e->f_score - e->g_score;
if (new_point) { // The position of the new points is already known.
sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptr());
@@ -414,7 +425,7 @@ real_t AStar3D::_compute_cost(int64_t p_from_id, int64_t p_to_id) {
return from_point->pos.distance_to(to_point->pos);
}
-Vector<Vector3> AStar3D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
+Vector<Vector3> AStar3D::get_point_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path) {
Point *a = nullptr;
bool from_exists = points.lookup(p_from_id, a);
ERR_FAIL_COND_V_MSG(!from_exists, Vector<Vector3>(), vformat("Can't get point path. Point with id: %d doesn't exist.", p_from_id));
@@ -434,7 +445,12 @@ Vector<Vector3> AStar3D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return Vector<Vector3>();
+ if (!p_allow_partial_path || last_closest_point == nullptr) {
+ return Vector<Vector3>();
+ }
+
+ // Use closest point instead.
+ end_point = last_closest_point;
}
Point *p = end_point;
@@ -463,7 +479,7 @@ Vector<Vector3> AStar3D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
return path;
}
-Vector<int64_t> AStar3D::get_id_path(int64_t p_from_id, int64_t p_to_id) {
+Vector<int64_t> AStar3D::get_id_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path) {
Point *a = nullptr;
bool from_exists = points.lookup(p_from_id, a);
ERR_FAIL_COND_V_MSG(!from_exists, Vector<int64_t>(), vformat("Can't get id path. Point with id: %d doesn't exist.", p_from_id));
@@ -483,7 +499,12 @@ Vector<int64_t> AStar3D::get_id_path(int64_t p_from_id, int64_t p_to_id) {
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return Vector<int64_t>();
+ if (!p_allow_partial_path || last_closest_point == nullptr) {
+ return Vector<int64_t>();
+ }
+
+ // Use closest point instead.
+ end_point = last_closest_point;
}
Point *p = end_point;
@@ -555,8 +576,8 @@ void AStar3D::_bind_methods() {
ClassDB::bind_method(D_METHOD("get_closest_point", "to_position", "include_disabled"), &AStar3D::get_closest_point, DEFVAL(false));
ClassDB::bind_method(D_METHOD("get_closest_position_in_segment", "to_position"), &AStar3D::get_closest_position_in_segment);
- ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar3D::get_point_path);
- ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar3D::get_id_path);
+ ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id", "allow_partial_path"), &AStar3D::get_point_path, DEFVAL(false));
+ ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id", "allow_partial_path"), &AStar3D::get_id_path, DEFVAL(false));
GDVIRTUAL_BIND(_estimate_cost, "from_id", "to_id")
GDVIRTUAL_BIND(_compute_cost, "from_id", "to_id")
@@ -688,7 +709,7 @@ real_t AStar2D::_compute_cost(int64_t p_from_id, int64_t p_to_id) {
return from_point->pos.distance_to(to_point->pos);
}
-Vector<Vector2> AStar2D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
+Vector<Vector2> AStar2D::get_point_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path) {
AStar3D::Point *a = nullptr;
bool from_exists = astar.points.lookup(p_from_id, a);
ERR_FAIL_COND_V_MSG(!from_exists, Vector<Vector2>(), vformat("Can't get point path. Point with id: %d doesn't exist.", p_from_id));
@@ -707,7 +728,12 @@ Vector<Vector2> AStar2D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return Vector<Vector2>();
+ if (!p_allow_partial_path || astar.last_closest_point == nullptr) {
+ return Vector<Vector2>();
+ }
+
+ // Use closest point instead.
+ end_point = astar.last_closest_point;
}
AStar3D::Point *p = end_point;
@@ -736,7 +762,7 @@ Vector<Vector2> AStar2D::get_point_path(int64_t p_from_id, int64_t p_to_id) {
return path;
}
-Vector<int64_t> AStar2D::get_id_path(int64_t p_from_id, int64_t p_to_id) {
+Vector<int64_t> AStar2D::get_id_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path) {
AStar3D::Point *a = nullptr;
bool from_exists = astar.points.lookup(p_from_id, a);
ERR_FAIL_COND_V_MSG(!from_exists, Vector<int64_t>(), vformat("Can't get id path. Point with id: %d doesn't exist.", p_from_id));
@@ -756,7 +782,12 @@ Vector<int64_t> AStar2D::get_id_path(int64_t p_from_id, int64_t p_to_id) {
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return Vector<int64_t>();
+ if (!p_allow_partial_path || astar.last_closest_point == nullptr) {
+ return Vector<int64_t>();
+ }
+
+ // Use closest point instead.
+ end_point = astar.last_closest_point;
}
AStar3D::Point *p = end_point;
@@ -786,6 +817,7 @@ Vector<int64_t> AStar2D::get_id_path(int64_t p_from_id, int64_t p_to_id) {
}
bool AStar2D::_solve(AStar3D::Point *begin_point, AStar3D::Point *end_point) {
+ astar.last_closest_point = nullptr;
astar.pass++;
if (!end_point->enabled) {
@@ -799,11 +831,18 @@ bool AStar2D::_solve(AStar3D::Point *begin_point, AStar3D::Point *end_point) {
begin_point->g_score = 0;
begin_point->f_score = _estimate_cost(begin_point->id, end_point->id);
+ begin_point->abs_g_score = 0;
+ begin_point->abs_f_score = _estimate_cost(begin_point->id, end_point->id);
open_list.push_back(begin_point);
while (!open_list.is_empty()) {
AStar3D::Point *p = open_list[0]; // The currently processed point.
+ // Find point closer to end_point, or same distance to end_point but closer to begin_point.
+ if (astar.last_closest_point == nullptr || astar.last_closest_point->abs_f_score > p->abs_f_score || (astar.last_closest_point->abs_f_score >= p->abs_f_score && astar.last_closest_point->abs_g_score > p->abs_g_score)) {
+ astar.last_closest_point = p;
+ }
+
if (p == end_point) {
found_route = true;
break;
@@ -835,6 +874,8 @@ bool AStar2D::_solve(AStar3D::Point *begin_point, AStar3D::Point *end_point) {
e->prev_point = p;
e->g_score = tentative_g_score;
e->f_score = e->g_score + _estimate_cost(e->id, end_point->id);
+ e->abs_g_score = tentative_g_score;
+ e->abs_f_score = e->f_score - e->g_score;
if (new_point) { // The position of the new points is already known.
sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptr());
@@ -874,8 +915,8 @@ void AStar2D::_bind_methods() {
ClassDB::bind_method(D_METHOD("get_closest_point", "to_position", "include_disabled"), &AStar2D::get_closest_point, DEFVAL(false));
ClassDB::bind_method(D_METHOD("get_closest_position_in_segment", "to_position"), &AStar2D::get_closest_position_in_segment);
- ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar2D::get_point_path);
- ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar2D::get_id_path);
+ ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id", "allow_partial_path"), &AStar2D::get_point_path, DEFVAL(false));
+ ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id", "allow_partial_path"), &AStar2D::get_id_path, DEFVAL(false));
GDVIRTUAL_BIND(_estimate_cost, "from_id", "to_id")
GDVIRTUAL_BIND(_compute_cost, "from_id", "to_id")
diff --git a/core/math/a_star.h b/core/math/a_star.h
index 0758500c8a..8e054c4789 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -60,6 +60,10 @@ class AStar3D : public RefCounted {
real_t f_score = 0;
uint64_t open_pass = 0;
uint64_t closed_pass = 0;
+
+ // Used for getting closest_point_of_last_pathing_call.
+ real_t abs_g_score = 0;
+ real_t abs_f_score = 0;
};
struct SortPoints {
@@ -109,6 +113,7 @@ class AStar3D : public RefCounted {
OAHashMap<int64_t, Point *> points;
HashSet<Segment, Segment> segments;
+ Point *last_closest_point = nullptr;
bool _solve(Point *begin_point, Point *end_point);
@@ -121,6 +126,12 @@ protected:
GDVIRTUAL2RC(real_t, _estimate_cost, int64_t, int64_t)
GDVIRTUAL2RC(real_t, _compute_cost, int64_t, int64_t)
+#ifndef DISABLE_DEPRECATED
+ Vector<int64_t> _get_id_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id);
+ Vector<Vector3> _get_point_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id);
+ static void _bind_compatibility_methods();
+#endif
+
public:
int64_t get_available_point_id() const;
@@ -149,8 +160,8 @@ public:
int64_t get_closest_point(const Vector3 &p_point, bool p_include_disabled = false) const;
Vector3 get_closest_position_in_segment(const Vector3 &p_point) const;
- Vector<Vector3> get_point_path(int64_t p_from_id, int64_t p_to_id);
- Vector<int64_t> get_id_path(int64_t p_from_id, int64_t p_to_id);
+ Vector<Vector3> get_point_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path = false);
+ Vector<int64_t> get_id_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path = false);
AStar3D() {}
~AStar3D();
@@ -171,6 +182,12 @@ protected:
GDVIRTUAL2RC(real_t, _estimate_cost, int64_t, int64_t)
GDVIRTUAL2RC(real_t, _compute_cost, int64_t, int64_t)
+#ifndef DISABLE_DEPRECATED
+ Vector<int64_t> _get_id_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id);
+ Vector<Vector2> _get_point_path_bind_compat_88047(int64_t p_from_id, int64_t p_to_id);
+ static void _bind_compatibility_methods();
+#endif
+
public:
int64_t get_available_point_id() const;
@@ -199,8 +216,8 @@ public:
int64_t get_closest_point(const Vector2 &p_point, bool p_include_disabled = false) const;
Vector2 get_closest_position_in_segment(const Vector2 &p_point) const;
- Vector<Vector2> get_point_path(int64_t p_from_id, int64_t p_to_id);
- Vector<int64_t> get_id_path(int64_t p_from_id, int64_t p_to_id);
+ Vector<Vector2> get_point_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path = false);
+ Vector<int64_t> get_id_path(int64_t p_from_id, int64_t p_to_id, bool p_allow_partial_path = false);
AStar2D() {}
~AStar2D() {}
diff --git a/core/math/a_star_grid_2d.compat.inc b/core/math/a_star_grid_2d.compat.inc
new file mode 100644
index 0000000000..e7124c2477
--- /dev/null
+++ b/core/math/a_star_grid_2d.compat.inc
@@ -0,0 +1,48 @@
+/**************************************************************************/
+/* a_star_grid_2d.compat.inc */
+/**************************************************************************/
+/* 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. */
+/**************************************************************************/
+
+#ifndef DISABLE_DEPRECATED
+
+#include "core/variant/typed_array.h"
+
+TypedArray<Vector2i> AStarGrid2D::_get_id_path_bind_compat_88047(const Vector2i &p_from_id, const Vector2i &p_to_id) {
+ return get_id_path(p_from_id, p_to_id, false);
+}
+
+Vector<Vector2> AStarGrid2D::_get_point_path_bind_compat_88047(const Vector2i &p_from_id, const Vector2i &p_to_id) {
+ return get_point_path(p_from_id, p_to_id, false);
+}
+
+void AStarGrid2D::_bind_compatibility_methods() {
+ ClassDB::bind_compatibility_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStarGrid2D::_get_id_path_bind_compat_88047);
+ ClassDB::bind_compatibility_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStarGrid2D::_get_point_path_bind_compat_88047);
+}
+
+#endif // DISABLE_DEPRECATED
diff --git a/core/math/a_star_grid_2d.cpp b/core/math/a_star_grid_2d.cpp
index d17f465ab8..f272407869 100644
--- a/core/math/a_star_grid_2d.cpp
+++ b/core/math/a_star_grid_2d.cpp
@@ -29,6 +29,7 @@
/**************************************************************************/
#include "a_star_grid_2d.h"
+#include "a_star_grid_2d.compat.inc"
#include "core/variant/typed_array.h"
@@ -446,6 +447,7 @@ void AStarGrid2D::_get_nbors(Point *p_point, LocalVector<Point *> &r_nbors) {
}
bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) {
+ last_closest_point = nullptr;
pass++;
if (p_end_point->solid) {
@@ -459,12 +461,19 @@ bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) {
p_begin_point->g_score = 0;
p_begin_point->f_score = _estimate_cost(p_begin_point->id, p_end_point->id);
+ p_begin_point->abs_g_score = 0;
+ p_begin_point->abs_f_score = _estimate_cost(p_begin_point->id, p_end_point->id);
open_list.push_back(p_begin_point);
end = p_end_point;
while (!open_list.is_empty()) {
Point *p = open_list[0]; // The currently processed point.
+ // Find point closer to end_point, or same distance to end_point but closer to begin_point.
+ if (last_closest_point == nullptr || last_closest_point->abs_f_score > p->abs_f_score || (last_closest_point->abs_f_score >= p->abs_f_score && last_closest_point->abs_g_score > p->abs_g_score)) {
+ last_closest_point = p;
+ }
+
if (p == p_end_point) {
found_route = true;
break;
@@ -508,6 +517,9 @@ bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) {
e->g_score = tentative_g_score;
e->f_score = e->g_score + _estimate_cost(e->id, p_end_point->id);
+ e->abs_g_score = tentative_g_score;
+ e->abs_f_score = e->f_score - e->g_score;
+
if (new_point) { // The position of the new points is already known.
sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptr());
} else {
@@ -546,7 +558,7 @@ Vector2 AStarGrid2D::get_point_position(const Vector2i &p_id) const {
return _get_point_unchecked(p_id)->pos;
}
-Vector<Vector2> AStarGrid2D::get_point_path(const Vector2i &p_from_id, const Vector2i &p_to_id) {
+Vector<Vector2> AStarGrid2D::get_point_path(const Vector2i &p_from_id, const Vector2i &p_to_id, bool p_allow_partial_path) {
ERR_FAIL_COND_V_MSG(dirty, Vector<Vector2>(), "Grid is not initialized. Call the update method.");
ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_from_id), Vector<Vector2>(), vformat("Can't get id path. Point %s out of bounds %s.", p_from_id, region));
ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_to_id), Vector<Vector2>(), vformat("Can't get id path. Point %s out of bounds %s.", p_to_id, region));
@@ -565,7 +577,12 @@ Vector<Vector2> AStarGrid2D::get_point_path(const Vector2i &p_from_id, const Vec
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return Vector<Vector2>();
+ if (!p_allow_partial_path || last_closest_point == nullptr) {
+ return Vector<Vector2>();
+ }
+
+ // Use closest point instead.
+ end_point = last_closest_point;
}
Point *p = end_point;
@@ -594,7 +611,7 @@ Vector<Vector2> AStarGrid2D::get_point_path(const Vector2i &p_from_id, const Vec
return path;
}
-TypedArray<Vector2i> AStarGrid2D::get_id_path(const Vector2i &p_from_id, const Vector2i &p_to_id) {
+TypedArray<Vector2i> AStarGrid2D::get_id_path(const Vector2i &p_from_id, const Vector2i &p_to_id, bool p_allow_partial_path) {
ERR_FAIL_COND_V_MSG(dirty, TypedArray<Vector2i>(), "Grid is not initialized. Call the update method.");
ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_from_id), TypedArray<Vector2i>(), vformat("Can't get id path. Point %s out of bounds %s.", p_from_id, region));
ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_to_id), TypedArray<Vector2i>(), vformat("Can't get id path. Point %s out of bounds %s.", p_to_id, region));
@@ -613,7 +630,12 @@ TypedArray<Vector2i> AStarGrid2D::get_id_path(const Vector2i &p_from_id, const V
bool found_route = _solve(begin_point, end_point);
if (!found_route) {
- return TypedArray<Vector2i>();
+ if (!p_allow_partial_path || last_closest_point == nullptr) {
+ return TypedArray<Vector2i>();
+ }
+
+ // Use closest point instead.
+ end_point = last_closest_point;
}
Point *p = end_point;
@@ -672,8 +694,8 @@ void AStarGrid2D::_bind_methods() {
ClassDB::bind_method(D_METHOD("clear"), &AStarGrid2D::clear);
ClassDB::bind_method(D_METHOD("get_point_position", "id"), &AStarGrid2D::get_point_position);
- ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStarGrid2D::get_point_path);
- ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStarGrid2D::get_id_path);
+ ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id", "allow_partial_path"), &AStarGrid2D::get_point_path, DEFVAL(false));
+ ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id", "allow_partial_path"), &AStarGrid2D::get_id_path, DEFVAL(false));
GDVIRTUAL_BIND(_estimate_cost, "from_id", "to_id")
GDVIRTUAL_BIND(_compute_cost, "from_id", "to_id")
diff --git a/core/math/a_star_grid_2d.h b/core/math/a_star_grid_2d.h
index 69cb77dd3e..1a9f6dcc11 100644
--- a/core/math/a_star_grid_2d.h
+++ b/core/math/a_star_grid_2d.h
@@ -89,6 +89,10 @@ private:
uint64_t open_pass = 0;
uint64_t closed_pass = 0;
+ // Used for getting last_closest_point.
+ real_t abs_g_score = 0;
+ real_t abs_f_score = 0;
+
Point() {}
Point(const Vector2i &p_id, const Vector2 &p_pos) :
@@ -109,6 +113,7 @@ private:
LocalVector<LocalVector<Point>> points;
Point *end = nullptr;
+ Point *last_closest_point = nullptr;
uint64_t pass = 1;
@@ -152,6 +157,12 @@ protected:
GDVIRTUAL2RC(real_t, _estimate_cost, Vector2i, Vector2i)
GDVIRTUAL2RC(real_t, _compute_cost, Vector2i, Vector2i)
+#ifndef DISABLE_DEPRECATED
+ TypedArray<Vector2i> _get_id_path_bind_compat_88047(const Vector2i &p_from, const Vector2i &p_to);
+ Vector<Vector2> _get_point_path_bind_compat_88047(const Vector2i &p_from, const Vector2i &p_to);
+ static void _bind_compatibility_methods();
+#endif
+
public:
void set_region(const Rect2i &p_region);
Rect2i get_region() const;
@@ -198,8 +209,8 @@ public:
void clear();
Vector2 get_point_position(const Vector2i &p_id) const;
- Vector<Vector2> get_point_path(const Vector2i &p_from, const Vector2i &p_to);
- TypedArray<Vector2i> get_id_path(const Vector2i &p_from, const Vector2i &p_to);
+ Vector<Vector2> get_point_path(const Vector2i &p_from, const Vector2i &p_to, bool p_allow_partial_path = false);
+ TypedArray<Vector2i> get_id_path(const Vector2i &p_from, const Vector2i &p_to, bool p_allow_partial_path = false);
};
VARIANT_ENUM_CAST(AStarGrid2D::DiagonalMode);
diff --git a/core/math/aabb.h b/core/math/aabb.h
index 7927c431eb..48a883e64c 100644
--- a/core/math/aabb.h
+++ b/core/math/aabb.h
@@ -101,7 +101,7 @@ struct _NO_DISCARD_ AABB {
_FORCE_INLINE_ void expand_to(const Vector3 &p_vector); /** expand to contain a point if necessary */
_FORCE_INLINE_ AABB abs() const {
- return AABB(Vector3(position.x + MIN(size.x, (real_t)0), position.y + MIN(size.y, (real_t)0), position.z + MIN(size.z, (real_t)0)), size.abs());
+ return AABB(position + size.min(Vector3()), size.abs());
}
Variant intersects_segment_bind(const Vector3 &p_from, const Vector3 &p_to) const;
diff --git a/core/math/delaunay_3d.h b/core/math/delaunay_3d.h
index 7df8c37e3c..846acdecc3 100644
--- a/core/math/delaunay_3d.h
+++ b/core/math/delaunay_3d.h
@@ -281,9 +281,7 @@ public:
}
Vector3i grid_pos = Vector3i(points[i] * ACCEL_GRID_SIZE);
- grid_pos.x = CLAMP(grid_pos.x, 0, ACCEL_GRID_SIZE - 1);
- grid_pos.y = CLAMP(grid_pos.y, 0, ACCEL_GRID_SIZE - 1);
- grid_pos.z = CLAMP(grid_pos.z, 0, ACCEL_GRID_SIZE - 1);
+ grid_pos = grid_pos.clamp(Vector3i(), Vector3i(ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1));
for (List<Simplex *>::Element *E = acceleration_grid[grid_pos.x][grid_pos.y][grid_pos.z].front(); E;) {
List<Simplex *>::Element *N = E->next(); //may be deleted
@@ -339,12 +337,8 @@ public:
Vector3 extents = Vector3(radius2, radius2, radius2);
Vector3i from = Vector3i((center - extents) * ACCEL_GRID_SIZE);
Vector3i to = Vector3i((center + extents) * ACCEL_GRID_SIZE);
- from.x = CLAMP(from.x, 0, ACCEL_GRID_SIZE - 1);
- from.y = CLAMP(from.y, 0, ACCEL_GRID_SIZE - 1);
- from.z = CLAMP(from.z, 0, ACCEL_GRID_SIZE - 1);
- to.x = CLAMP(to.x, 0, ACCEL_GRID_SIZE - 1);
- to.y = CLAMP(to.y, 0, ACCEL_GRID_SIZE - 1);
- to.z = CLAMP(to.z, 0, ACCEL_GRID_SIZE - 1);
+ from = from.clamp(Vector3i(), Vector3i(ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1));
+ to = to.clamp(Vector3i(), Vector3i(ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1, ACCEL_GRID_SIZE - 1));
for (int32_t x = from.x; x <= to.x; x++) {
for (int32_t y = from.y; y <= to.y; y++) {
diff --git a/core/math/dynamic_bvh.h b/core/math/dynamic_bvh.h
index f586b845c3..26fc517f7f 100644
--- a/core/math/dynamic_bvh.h
+++ b/core/math/dynamic_bvh.h
@@ -376,13 +376,8 @@ void DynamicBVH::convex_query(const Plane *p_planes, int p_plane_count, const Ve
volume.min = p_points[0];
volume.max = p_points[0];
} else {
- volume.min.x = MIN(volume.min.x, p_points[i].x);
- volume.min.y = MIN(volume.min.y, p_points[i].y);
- volume.min.z = MIN(volume.min.z, p_points[i].z);
-
- volume.max.x = MAX(volume.max.x, p_points[i].x);
- volume.max.y = MAX(volume.max.y, p_points[i].y);
- volume.max.z = MAX(volume.max.z, p_points[i].z);
+ volume.min = volume.min.min(p_points[i]);
+ volume.max = volume.max.max(p_points[i]);
}
}
diff --git a/core/math/geometry_2d.h b/core/math/geometry_2d.h
index fbcaa018a8..1502b2807c 100644
--- a/core/math/geometry_2d.h
+++ b/core/math/geometry_2d.h
@@ -377,10 +377,8 @@ public:
Vector2 further_away_opposite(1e20, 1e20);
for (int i = 0; i < c; i++) {
- further_away.x = MAX(p[i].x, further_away.x);
- further_away.y = MAX(p[i].y, further_away.y);
- further_away_opposite.x = MIN(p[i].x, further_away_opposite.x);
- further_away_opposite.y = MIN(p[i].y, further_away_opposite.y);
+ further_away = further_away.max(p[i]);
+ further_away_opposite = further_away_opposite.min(p[i]);
}
// Make point outside that won't intersect with points in segment from p_point.
diff --git a/core/math/projection.cpp b/core/math/projection.cpp
index 9d5dc8b4d6..d3cf11f91a 100644
--- a/core/math/projection.cpp
+++ b/core/math/projection.cpp
@@ -719,7 +719,8 @@ Projection Projection::operator*(const Projection &p_matrix) const {
return new_matrix;
}
-void Projection::set_depth_correction(bool p_flip_y) {
+void Projection::set_depth_correction(bool p_flip_y, bool p_reverse_z, bool p_remap_z) {
+ // p_remap_z is used to convert from OpenGL-style clip space (-1 - 1) to Vulkan style (0 - 1).
real_t *m = &columns[0][0];
m[0] = 1;
@@ -732,11 +733,11 @@ void Projection::set_depth_correction(bool p_flip_y) {
m[7] = 0.0;
m[8] = 0.0;
m[9] = 0.0;
- m[10] = 0.5;
+ m[10] = p_remap_z ? (p_reverse_z ? -0.5 : 0.5) : (p_reverse_z ? -1.0 : 1.0);
m[11] = 0.0;
m[12] = 0.0;
m[13] = 0.0;
- m[14] = 0.5;
+ m[14] = p_remap_z ? 0.5 : 0.0;
m[15] = 1.0;
}
diff --git a/core/math/projection.h b/core/math/projection.h
index b98f636344..7bba9b337e 100644
--- a/core/math/projection.h
+++ b/core/math/projection.h
@@ -69,7 +69,7 @@ struct _NO_DISCARD_ Projection {
void set_identity();
void set_zero();
void set_light_bias();
- void set_depth_correction(bool p_flip_y = true);
+ void set_depth_correction(bool p_flip_y = true, bool p_reverse_z = true, bool p_remap_z = true);
void set_light_atlas_rect(const Rect2 &p_rect);
void set_perspective(real_t p_fovy_degrees, real_t p_aspect, real_t p_z_near, real_t p_z_far, bool p_flip_fov = false);
diff --git a/core/math/random_pcg.cpp b/core/math/random_pcg.cpp
index e083820494..55787a0b57 100644
--- a/core/math/random_pcg.cpp
+++ b/core/math/random_pcg.cpp
@@ -52,7 +52,7 @@ int64_t RandomPCG::rand_weighted(const Vector<float> &p_weights) {
weights_sum += weights[i];
}
- float remaining_distance = Math::randf() * weights_sum;
+ float remaining_distance = randf() * weights_sum;
for (int64_t i = 0; i < weights_size; ++i) {
remaining_distance -= weights[i];
if (remaining_distance < 0) {
diff --git a/core/math/rect2.h b/core/math/rect2.h
index 0f874d4857..497ed8cf04 100644
--- a/core/math/rect2.h
+++ b/core/math/rect2.h
@@ -152,14 +152,12 @@ struct _NO_DISCARD_ Rect2 {
return Rect2();
}
- new_rect.position.x = MAX(p_rect.position.x, position.x);
- new_rect.position.y = MAX(p_rect.position.y, position.y);
+ new_rect.position = p_rect.position.max(position);
Point2 p_rect_end = p_rect.position + p_rect.size;
Point2 end = position + size;
- new_rect.size.x = MIN(p_rect_end.x, end.x) - new_rect.position.x;
- new_rect.size.y = MIN(p_rect_end.y, end.y) - new_rect.position.y;
+ new_rect.size = p_rect_end.min(end) - new_rect.position;
return new_rect;
}
@@ -172,11 +170,9 @@ struct _NO_DISCARD_ Rect2 {
#endif
Rect2 new_rect;
- new_rect.position.x = MIN(p_rect.position.x, position.x);
- new_rect.position.y = MIN(p_rect.position.y, position.y);
+ new_rect.position = p_rect.position.min(position);
- new_rect.size.x = MAX(p_rect.position.x + p_rect.size.x, position.x + size.x);
- new_rect.size.y = MAX(p_rect.position.y + p_rect.size.y, position.y + size.y);
+ new_rect.size = (p_rect.position + p_rect.size).max(position + size);
new_rect.size = new_rect.size - new_rect.position; // Make relative again.
@@ -282,7 +278,7 @@ struct _NO_DISCARD_ Rect2 {
}
_FORCE_INLINE_ Rect2 abs() const {
- return Rect2(Point2(position.x + MIN(size.x, (real_t)0), position.y + MIN(size.y, (real_t)0)), size.abs());
+ return Rect2(position + size.min(Point2()), size.abs());
}
_FORCE_INLINE_ Rect2 round() const {
diff --git a/core/math/rect2i.h b/core/math/rect2i.h
index 205b2c7198..64806414c7 100644
--- a/core/math/rect2i.h
+++ b/core/math/rect2i.h
@@ -95,14 +95,12 @@ struct _NO_DISCARD_ Rect2i {
return Rect2i();
}
- new_rect.position.x = MAX(p_rect.position.x, position.x);
- new_rect.position.y = MAX(p_rect.position.y, position.y);
+ new_rect.position = p_rect.position.max(position);
Point2i p_rect_end = p_rect.position + p_rect.size;
Point2i end = position + size;
- new_rect.size.x = MIN(p_rect_end.x, end.x) - new_rect.position.x;
- new_rect.size.y = MIN(p_rect_end.y, end.y) - new_rect.position.y;
+ new_rect.size = p_rect_end.min(end) - new_rect.position;
return new_rect;
}
@@ -115,11 +113,9 @@ struct _NO_DISCARD_ Rect2i {
#endif
Rect2i new_rect;
- new_rect.position.x = MIN(p_rect.position.x, position.x);
- new_rect.position.y = MIN(p_rect.position.y, position.y);
+ new_rect.position = p_rect.position.min(position);
- new_rect.size.x = MAX(p_rect.position.x + p_rect.size.x, position.x + size.x);
- new_rect.size.y = MAX(p_rect.position.y + p_rect.size.y, position.y + size.y);
+ new_rect.size = (p_rect.position + p_rect.size).max(position + size);
new_rect.size = new_rect.size - new_rect.position; // Make relative again.
@@ -217,7 +213,7 @@ struct _NO_DISCARD_ Rect2i {
}
_FORCE_INLINE_ Rect2i abs() const {
- return Rect2i(Point2i(position.x + MIN(size.x, 0), position.y + MIN(size.y, 0)), size.abs());
+ return Rect2i(position + size.min(Point2i()), size.abs());
}
_FORCE_INLINE_ void set_end(const Vector2i &p_end) {
diff --git a/core/math/transform_interpolator.cpp b/core/math/transform_interpolator.cpp
new file mode 100644
index 0000000000..7cfe880b5a
--- /dev/null
+++ b/core/math/transform_interpolator.cpp
@@ -0,0 +1,76 @@
+/**************************************************************************/
+/* transform_interpolator.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 "transform_interpolator.h"
+
+#include "core/math/transform_2d.h"
+
+void TransformInterpolator::interpolate_transform_2d(const Transform2D &p_prev, const Transform2D &p_curr, Transform2D &r_result, real_t p_fraction) {
+ // Extract parameters.
+ Vector2 p1 = p_prev.get_origin();
+ Vector2 p2 = p_curr.get_origin();
+
+ // Special case for physics interpolation, if flipping, don't interpolate basis.
+ // If the determinant polarity changes, the handedness of the coordinate system changes.
+ if (_sign(p_prev.determinant()) != _sign(p_curr.determinant())) {
+ r_result.columns[0] = p_curr.columns[0];
+ r_result.columns[1] = p_curr.columns[1];
+ r_result.set_origin(p1.lerp(p2, p_fraction));
+ return;
+ }
+
+ real_t r1 = p_prev.get_rotation();
+ real_t r2 = p_curr.get_rotation();
+
+ Size2 s1 = p_prev.get_scale();
+ Size2 s2 = p_curr.get_scale();
+
+ // Slerp rotation.
+ Vector2 v1(Math::cos(r1), Math::sin(r1));
+ Vector2 v2(Math::cos(r2), Math::sin(r2));
+
+ real_t dot = v1.dot(v2);
+
+ dot = CLAMP(dot, -1, 1);
+
+ Vector2 v;
+
+ if (dot > 0.9995f) {
+ v = v1.lerp(v2, p_fraction).normalized(); // Linearly interpolate to avoid numerical precision issues.
+ } else {
+ real_t angle = p_fraction * Math::acos(dot);
+ Vector2 v3 = (v2 - v1 * dot).normalized();
+ v = v1 * Math::cos(angle) + v3 * Math::sin(angle);
+ }
+
+ // Construct matrix.
+ r_result = Transform2D(Math::atan2(v.y, v.x), p1.lerp(p2, p_fraction));
+ r_result.scale_basis(s1.lerp(s2, p_fraction));
+}
diff --git a/core/math/transform_interpolator.h b/core/math/transform_interpolator.h
new file mode 100644
index 0000000000..a9bce2bd7f
--- /dev/null
+++ b/core/math/transform_interpolator.h
@@ -0,0 +1,46 @@
+/**************************************************************************/
+/* transform_interpolator.h */
+/**************************************************************************/
+/* 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. */
+/**************************************************************************/
+
+#ifndef TRANSFORM_INTERPOLATOR_H
+#define TRANSFORM_INTERPOLATOR_H
+
+#include "core/math/math_defs.h"
+
+struct Transform2D;
+
+class TransformInterpolator {
+private:
+ static bool _sign(real_t p_val) { return p_val >= 0; }
+
+public:
+ static void interpolate_transform_2d(const Transform2D &p_prev, const Transform2D &p_curr, Transform2D &r_result, real_t p_fraction);
+};
+
+#endif // TRANSFORM_INTERPOLATOR_H