summaryrefslogtreecommitdiff
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/error_macros.h2
-rw-r--r--core/io/http_client.cpp2
-rw-r--r--core/io/resource_importer.cpp3
-rw-r--r--core/io/resource_importer.h2
-rw-r--r--core/io/zip_io.h2
-rw-r--r--core/math/a_star.cpp91
-rw-r--r--core/math/a_star.h22
-rw-r--r--core/math/geometry.h2
-rw-r--r--core/undo_redo.cpp16
-rw-r--r--core/undo_redo.h4
10 files changed, 62 insertions, 84 deletions
diff --git a/core/error_macros.h b/core/error_macros.h
index 78e29551d4..f72e987e23 100644
--- a/core/error_macros.h
+++ b/core/error_macros.h
@@ -41,7 +41,7 @@
*/
/**
- * Pointer to the error macro priting function. Reassign to any function to have errors printed
+ * Pointer to the error macro printing function. Reassign to any function to have errors printed
*/
/** Function used by the error macros */
diff --git a/core/io/http_client.cpp b/core/io/http_client.cpp
index e5c6d2a4f2..ce2054db36 100644
--- a/core/io/http_client.cpp
+++ b/core/io/http_client.cpp
@@ -429,7 +429,7 @@ Error HTTPClient::poll() {
response_num = RESPONSE_OK;
// Per the HTTP 1.1 spec, keep-alive is the default.
- // Not following that specification breaks standard implemetations.
+ // Not following that specification breaks standard implementations.
// Broken web servers should be fixed.
bool keep_alive = true;
diff --git a/core/io/resource_importer.cpp b/core/io/resource_importer.cpp
index 038a34ed51..4a58d37ca5 100644
--- a/core/io/resource_importer.cpp
+++ b/core/io/resource_importer.cpp
@@ -301,8 +301,7 @@ String ResourceFormatImporter::get_import_group_file(const String &p_path) const
bool valid = true;
PathAndType pat;
_get_path_and_type(p_path, pat, &valid);
- return valid?pat.group_file:String();
-
+ return valid ? pat.group_file : String();
}
bool ResourceFormatImporter::is_import_valid(const String &p_path) const {
diff --git a/core/io/resource_importer.h b/core/io/resource_importer.h
index bdbdde6df6..2e01989564 100644
--- a/core/io/resource_importer.h
+++ b/core/io/resource_importer.h
@@ -126,7 +126,7 @@ public:
virtual Error import(const String &p_source_file, const String &p_save_path, const Map<StringName, Variant> &p_options, List<String> *r_platform_variants, List<String> *r_gen_files = NULL, Variant *r_metadata = NULL) = 0;
- virtual Error import_group_file(const String& p_group_file,const Map<String,Map<StringName, Variant> >&p_source_file_options, const Map<String,String>& p_base_paths) { return ERR_UNAVAILABLE; }
+ virtual Error import_group_file(const String &p_group_file, const Map<String, Map<StringName, Variant> > &p_source_file_options, const Map<String, String> &p_base_paths) { return ERR_UNAVAILABLE; }
virtual bool are_import_settings_valid(const String &p_path) const { return true; }
virtual String get_import_settings_string() const { return String(); }
};
diff --git a/core/io/zip_io.h b/core/io/zip_io.h
index fb63878a4c..4eb1c8b46c 100644
--- a/core/io/zip_io.h
+++ b/core/io/zip_io.h
@@ -33,7 +33,7 @@
#include "core/os/file_access.h"
-// Not direclty used in this header, but assumed available in downstream users
+// Not directly used in this header, but assumed available in downstream users
// like platform/*/export/export.cpp. Could be fixed, but probably better to have
// thirdparty includes in as little headers as possible.
#include "thirdparty/minizip/unzip.h"
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index e1388ad2ac..3d71e66f80 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -54,7 +54,8 @@ void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) {
pt->pos = p_pos;
pt->weight_scale = p_weight_scale;
pt->prev_point = NULL;
- pt->last_pass = 0;
+ pt->open_pass = 0;
+ pt->closed_pass = 0;
pt->enabled = true;
points[p_id] = pt;
} else {
@@ -246,86 +247,62 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
if (!end_point->enabled)
return false;
- SelfList<Point>::List open_list;
-
bool found_route = false;
- for (Set<Point *>::Element *E = begin_point->neighbours.front(); E; E = E->next()) {
-
- Point *n = E->get();
+ Vector<Point *> open_list;
+ SortArray<Point *, SortPoints> sorter;
- if (!n->enabled)
- continue;
+ begin_point->g_score = 0;
+ begin_point->f_score = _estimate_cost(begin_point->id, end_point->id);
- n->prev_point = begin_point;
- n->distance = _compute_cost(begin_point->id, n->id) * n->weight_scale;
- n->last_pass = pass;
- open_list.add(&n->list);
- }
+ open_list.push_back(begin_point);
while (true) {
- if (open_list.first() == NULL) {
- // No path found
+ if (open_list.size() == 0) // No path found
break;
- }
- // Check open list
-
- SelfList<Point> *least_cost_point = open_list.first();
- real_t least_cost = Math_INF;
- // TODO: Cache previous results
- for (SelfList<Point> *E = open_list.first(); E; E = E->next()) {
-
- Point *p = E->self();
-
- real_t cost = p->distance;
- cost += _estimate_cost(p->id, end_point->id);
-
- if (cost < least_cost) {
- least_cost_point = E;
- least_cost = cost;
- }
- }
+ Point *p = open_list[0]; // The currently processed point
- Point *p = least_cost_point->self();
if (p == end_point) {
found_route = true;
break;
}
+ sorter.pop_heap(0, open_list.size(), open_list.ptrw()); // Remove the current point from the open list
+ open_list.remove(open_list.size() - 1);
+ p->closed_pass = pass; // Mark the point as closed
+
for (Set<Point *>::Element *E = p->neighbours.front(); E; E = E->next()) {
- Point *e = E->get();
+ Point *e = E->get(); // The neighbour point
- if (!e->enabled)
+ if (!e->enabled || e->closed_pass == pass)
continue;
- real_t distance = _compute_cost(p->id, e->id) * e->weight_scale + p->distance;
+ real_t tentative_g_score = p->g_score + _compute_cost(p->id, e->id) * e->weight_scale;
+
+ bool new_point = false;
- if (e->last_pass == pass) {
- // Already visited, is this cheaper?
+ if (e->open_pass != pass) { // The point wasn't inside the open list
- if (e->distance > distance) {
- e->prev_point = p;
- e->distance = distance;
- }
- } else {
- // Add to open neighbours
+ e->open_pass = pass;
+ open_list.push_back(e);
+ new_point = true;
+ } else if (tentative_g_score >= e->g_score) { // The new path is worse than the previous
- e->prev_point = p;
- e->distance = distance;
- e->last_pass = pass; // Mark as used
- open_list.add(&e->list);
+ continue;
}
- }
- open_list.remove(least_cost_point);
- }
+ e->prev_point = p;
+ e->g_score = tentative_g_score;
+ e->f_score = e->g_score + _estimate_cost(e->id, end_point->id);
- // Clear the openf list
- while (open_list.first()) {
- open_list.remove(open_list.first());
+ if (new_point) // The position of the new points is already known
+ sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptrw());
+ else
+ sorter.push_heap(0, open_list.find(e), 0, e, open_list.ptrw());
+ }
}
return found_route;
@@ -352,8 +329,6 @@ PoolVector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) {
ERR_FAIL_COND_V(!points.has(p_from_id), PoolVector<Vector3>());
ERR_FAIL_COND_V(!points.has(p_to_id), PoolVector<Vector3>());
- pass++;
-
Point *a = points[p_from_id];
Point *b = points[p_to_id];
@@ -403,8 +378,6 @@ PoolVector<int> AStar::get_id_path(int p_from_id, int p_to_id) {
ERR_FAIL_COND_V(!points.has(p_from_id), PoolVector<int>());
ERR_FAIL_COND_V(!points.has(p_to_id), PoolVector<int>());
- pass++;
-
Point *a = points[p_from_id];
Point *b = points[p_to_id];
diff --git a/core/math/a_star.h b/core/math/a_star.h
index c63e1aa4dc..fac8a9d312 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -48,26 +48,34 @@ class AStar : public Reference {
struct Point {
- SelfList<Point> list;
-
int id;
Vector3 pos;
real_t weight_scale;
- uint64_t last_pass;
bool enabled;
Set<Point *> neighbours;
// Used for pathfinding
Point *prev_point;
- real_t distance;
-
- Point() :
- list(this) {}
+ real_t g_score;
+ real_t f_score;
+ uint64_t open_pass;
+ uint64_t closed_pass;
};
Map<int, Point *> points;
+ struct SortPoints {
+ _FORCE_INLINE_ bool operator()(const Point *A, const Point *B) const { // Returns true when the Point A is worse than Point B
+ if (A->f_score > B->f_score)
+ return true;
+ else if (A->f_score < B->f_score)
+ return false;
+ else
+ return A->g_score < B->g_score; // If the f_costs are the same then prioritize the points that are further away from the start
+ }
+ };
+
struct Segment {
union {
struct {
diff --git a/core/math/geometry.h b/core/math/geometry.h
index f3a671aa9a..0b2adf9513 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -833,7 +833,7 @@ public:
further_away_opposite.y = MIN(p[i].y, further_away_opposite.y);
}
- further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312); // make point outside that wont intersect with points in segment from p_point
+ further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312); // make point outside that won't intersect with points in segment from p_point
int intersections = 0;
for (int i = 0; i < c; i++) {
diff --git a/core/undo_redo.cpp b/core/undo_redo.cpp
index 69581e4115..f7ca6d3bde 100644
--- a/core/undo_redo.cpp
+++ b/core/undo_redo.cpp
@@ -239,8 +239,8 @@ void UndoRedo::_pop_history_tail() {
}
}
-bool UndoRedo::is_commiting_action() const {
- return commiting > 0;
+bool UndoRedo::is_committing_action() const {
+ return committing > 0;
}
void UndoRedo::commit_action() {
@@ -255,9 +255,9 @@ void UndoRedo::commit_action() {
merging = false;
}
- commiting++;
+ committing++;
redo(); // perform action
- commiting--;
+ committing--;
if (callback && actions.size() > 0) {
callback(callback_ud, actions[actions.size() - 1].name);
}
@@ -396,7 +396,7 @@ void UndoRedo::set_property_notify_callback(PropertyNotifyCallback p_property_ca
UndoRedo::UndoRedo() {
- commiting = 0;
+ committing = 0;
version = 1;
action_level = 0;
current_action = -1;
@@ -496,10 +496,8 @@ void UndoRedo::_bind_methods() {
ClassDB::bind_method(D_METHOD("create_action", "name", "merge_mode"), &UndoRedo::create_action, DEFVAL(MERGE_DISABLE));
ClassDB::bind_method(D_METHOD("commit_action"), &UndoRedo::commit_action);
- ClassDB::bind_method(D_METHOD("is_commiting_action"), &UndoRedo::is_commiting_action);
-
- //ClassDB::bind_method(D_METHOD("add_do_method","p_object", "p_method", "VARIANT_ARG_LIST"),&UndoRedo::add_do_method);
- //ClassDB::bind_method(D_METHOD("add_undo_method","p_object", "p_method", "VARIANT_ARG_LIST"),&UndoRedo::add_undo_method);
+ // FIXME: Typo in "commiting", fix in 4.0 when breaking compat.
+ ClassDB::bind_method(D_METHOD("is_commiting_action"), &UndoRedo::is_committing_action);
{
MethodInfo mi;
diff --git a/core/undo_redo.h b/core/undo_redo.h
index 6293e77acc..e2cc6c659b 100644
--- a/core/undo_redo.h
+++ b/core/undo_redo.h
@@ -95,7 +95,7 @@ private:
MethodNotifyCallback method_callback;
PropertyNotifyCallback property_callback;
- int commiting;
+ int committing;
protected:
static void _bind_methods();
@@ -110,7 +110,7 @@ public:
void add_do_reference(Object *p_object);
void add_undo_reference(Object *p_object);
- bool is_commiting_action() const;
+ bool is_committing_action() const;
void commit_action();
bool redo();
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-27 19:01:19 +0000