summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/math/a_star.cpp55
-rw-r--r--core/math/a_star.h6
-rw-r--r--doc/classes/AStar.xml25
3 files changed, 69 insertions, 17 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index ffe1089965..f43af49754 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -42,8 +42,10 @@ int AStar::get_available_point_id() const {
}
void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) {
+
ERR_FAIL_COND(p_id < 0);
ERR_FAIL_COND(p_weight_scale < 1);
+
if (!points.has(p_id)) {
Point *pt = memnew(Point);
pt->id = p_id;
@@ -64,12 +66,29 @@ Vector3 AStar::get_point_position(int p_id) const {
return points[p_id]->pos;
}
+
+void AStar::set_point_position(int p_id, const Vector3 &p_pos) {
+
+ ERR_FAIL_COND(!points.has(p_id));
+
+ points[p_id]->pos = p_pos;
+}
+
real_t AStar::get_point_weight_scale(int p_id) const {
ERR_FAIL_COND_V(!points.has(p_id), 0);
return points[p_id]->weight_scale;
}
+
+void AStar::set_point_weight_scale(int p_id, real_t p_weight_scale) {
+
+ ERR_FAIL_COND(!points.has(p_id));
+ ERR_FAIL_COND(p_weight_scale < 1);
+
+ points[p_id]->weight_scale = p_weight_scale;
+}
+
void AStar::remove_point(int p_id) {
ERR_FAIL_COND(!points.has(p_id));
@@ -130,6 +149,7 @@ bool AStar::has_point(int p_id) const {
}
Array AStar::get_points() {
+
Array point_list;
for (const Map<int, Point *>::Element *E = points.front(); E; E = E->next()) {
@@ -171,6 +191,7 @@ int AStar::get_closest_point(const Vector3 &p_point) const {
return closest_id;
}
+
Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const {
real_t closest_dist = 1e20;
@@ -222,15 +243,15 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
while (!found_route) {
if (open_list.first() == NULL) {
- //could not find path sadly
+ // No path found
break;
}
- //check open list
+ // Check open list
SelfList<Point> *least_cost_point = NULL;
real_t least_cost = 1e30;
- //this could be faster (cache previous results)
+ // TODO: Cache previous results
for (SelfList<Point> *E = open_list.first(); E; E = E->next()) {
Point *p = E->self();
@@ -246,7 +267,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
}
Point *p = least_cost_point->self();
- //open the neighbours for search
+ // Open the neighbours for search
int es = p->neighbours.size();
for (int i = 0; i < es; i++) {
@@ -256,7 +277,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
real_t distance = _compute_cost(p->id, e->id) * e->weight_scale + p->distance;
if (e->last_pass == pass) {
- //oh this was visited already, can we win the cost?
+ // Already visited, is this cheaper?
if (e->distance > distance) {
@@ -264,15 +285,15 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
e->distance = distance;
}
} else {
- //add to open neighbours
+ // Add to open neighbours
e->prev_point = p;
e->distance = distance;
- e->last_pass = pass; //mark as used
+ e->last_pass = pass; // Mark as used
open_list.add(&e->list);
if (e == end_point) {
- //oh my reached end! stop algorithm
+ // End reached; stop algorithm
found_route = true;
break;
}
@@ -285,7 +306,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
open_list.remove(least_cost_point);
}
- //clear the openf list
+ // Clear the openf list
while (open_list.first()) {
open_list.remove(open_list.first());
}
@@ -294,6 +315,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) {
}
float AStar::_estimate_cost(int p_from_id, int p_to_id) {
+
if (get_script_instance() && get_script_instance()->has_method(SceneStringNames::get_singleton()->_estimate_cost))
return get_script_instance()->call(SceneStringNames::get_singleton()->_estimate_cost, p_from_id, p_to_id);
@@ -301,6 +323,7 @@ float AStar::_estimate_cost(int p_from_id, int p_to_id) {
}
float AStar::_compute_cost(int p_from_id, int p_to_id) {
+
if (get_script_instance() && get_script_instance()->has_method(SceneStringNames::get_singleton()->_compute_cost))
return get_script_instance()->call(SceneStringNames::get_singleton()->_compute_cost, p_from_id, p_to_id);
@@ -331,9 +354,9 @@ PoolVector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) {
if (!found_route)
return PoolVector<Vector3>();
- //midpoints
+ // Midpoints
Point *p = end_point;
- int pc = 1; //begin point
+ int pc = 1; // Begin point
while (p != begin_point) {
pc++;
p = p->prev_point;
@@ -352,7 +375,7 @@ PoolVector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) {
p = p->prev_point;
}
- w[0] = p->pos; //assign first
+ w[0] = p->pos; // Assign first
}
return path;
@@ -382,9 +405,9 @@ PoolVector<int> AStar::get_id_path(int p_from_id, int p_to_id) {
if (!found_route)
return PoolVector<int>();
- //midpoints
+ // Midpoints
Point *p = end_point;
- int pc = 1; //begin point
+ int pc = 1; // Begin point
while (p != begin_point) {
pc++;
p = p->prev_point;
@@ -403,7 +426,7 @@ PoolVector<int> AStar::get_id_path(int p_from_id, int p_to_id) {
p = p->prev_point;
}
- w[0] = p->id; //assign first
+ w[0] = p->id; // Assign first
}
return path;
@@ -414,7 +437,9 @@ void AStar::_bind_methods() {
ClassDB::bind_method(D_METHOD("get_available_point_id"), &AStar::get_available_point_id);
ClassDB::bind_method(D_METHOD("add_point", "id", "position", "weight_scale"), &AStar::add_point, DEFVAL(1.0));
ClassDB::bind_method(D_METHOD("get_point_position", "id"), &AStar::get_point_position);
+ ClassDB::bind_method(D_METHOD("set_point_position", "id", "position"), &AStar::set_point_position);
ClassDB::bind_method(D_METHOD("get_point_weight_scale", "id"), &AStar::get_point_weight_scale);
+ ClassDB::bind_method(D_METHOD("set_point_weight_scale", "id", "weight_scale"), &AStar::set_point_weight_scale);
ClassDB::bind_method(D_METHOD("remove_point", "id"), &AStar::remove_point);
ClassDB::bind_method(D_METHOD("has_point", "id"), &AStar::has_point);
ClassDB::bind_method(D_METHOD("get_points"), &AStar::get_points);
diff --git a/core/math/a_star.h b/core/math/a_star.h
index 2c1e2e2cf7..23773e82e2 100644
--- a/core/math/a_star.h
+++ b/core/math/a_star.h
@@ -33,6 +33,8 @@
#include "reference.h"
#include "self_list.h"
/**
+ A* pathfinding algorithm
+
@author Juan Linietsky <reduzio@gmail.com>
*/
@@ -53,7 +55,7 @@ class AStar : public Reference {
Vector<Point *> neighbours;
- //used for pathfinding
+ // Used for pathfinding
Point *prev_point;
real_t distance;
@@ -102,7 +104,9 @@ public:
void add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale = 1);
Vector3 get_point_position(int p_id) const;
+ void set_point_position(int p_id, const Vector3 &p_pos);
real_t get_point_weight_scale(int p_id) const;
+ void set_point_weight_scale(int p_id, real_t p_weight_scale);
void remove_point(int p_id);
bool has_point(int p_id) const;
Array get_points();
diff --git a/doc/classes/AStar.xml b/doc/classes/AStar.xml
index 9b15afbbd4..baeeddcd1a 100644
--- a/doc/classes/AStar.xml
+++ b/doc/classes/AStar.xml
@@ -50,6 +50,7 @@
as.add_point(1, Vector3(1,0,0), 4) # Adds the point (1,0,0) with weight_scale=4 and id=1
[/codeblock]
+ If there already exists a point for the given id, its position and weight scale are updated to the given values.
</description>
</method>
<method name="are_points_connected" qualifiers="const">
@@ -107,7 +108,7 @@
<return type="int">
</return>
<description>
- Returns an id with no point associated to it.
+ Returns the next available point id with no point associated to it.
</description>
</method>
<method name="get_closest_point" qualifiers="const">
@@ -220,6 +221,28 @@
Removes the point associated with the given id from the points pool.
</description>
</method>
+ <method name="set_point_position">
+ <return type="void">
+ </return>
+ <argument index="0" name="id" type="int">
+ </argument>
+ <argument index="1" name="position" type="Vector3">
+ </argument>
+ <description>
+ Sets the position for the point with the given id.
+ </description>
+ </method>
+ <method name="set_point_weight_scale">
+ <return type="void">
+ </return>
+ <argument index="0" name="id" type="int">
+ </argument>
+ <argument index="1" name="weight_scale" type="float">
+ </argument>
+ <description>
+ Sets the [code]weight_scale[/code] for the point with the given id.
+ </description>
+ </method>
</methods>
<constants>
</constants>
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 05:57:53 +0000