diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/math/a_star_grid_2d.cpp | 20 | ||||
| -rw-r--r-- | core/math/a_star_grid_2d.h | 4 |
2 files changed, 24 insertions, 0 deletions
diff --git a/core/math/a_star_grid_2d.cpp b/core/math/a_star_grid_2d.cpp index df269a5c36..5b08fb2c55 100644 --- a/core/math/a_star_grid_2d.cpp +++ b/core/math/a_star_grid_2d.cpp @@ -179,6 +179,14 @@ bool AStarGrid2D::is_jumping_enabled() const { return jumping_enabled; } +int64_t AStarGrid2D::get_max_traversals() const { + return max_traversals; +} + +void AStarGrid2D::set_max_traversals(int64_t p_max_traversals) { + max_traversals = p_max_traversals; +} + void AStarGrid2D::set_diagonal_mode(DiagonalMode p_diagonal_mode) { ERR_FAIL_INDEX((int)p_diagonal_mode, (int)DIAGONAL_MODE_MAX); diagonal_mode = p_diagonal_mode; @@ -461,6 +469,7 @@ bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) { } bool found_route = false; + int64_t traversal_count = 0; LocalVector<Point *> open_list; SortArray<Point *, SortPoints> sorter; @@ -485,6 +494,14 @@ bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) { break; } + // If we have a limit on traversals, increment and stop once we reach the threshold. + if (max_traversals > 0 && traversal_count >= max_traversals) { + break; + } + + // Increment traversals for each node we process. + traversal_count++; + sorter.pop_heap(0, open_list.size(), open_list.ptr()); // Remove the current point from the open list. open_list.remove_at(open_list.size() - 1); p->closed_pass = pass; // Mark the point as closed. @@ -685,6 +702,8 @@ void AStarGrid2D::_bind_methods() { ClassDB::bind_method(D_METHOD("update"), &AStarGrid2D::update); ClassDB::bind_method(D_METHOD("set_jumping_enabled", "enabled"), &AStarGrid2D::set_jumping_enabled); ClassDB::bind_method(D_METHOD("is_jumping_enabled"), &AStarGrid2D::is_jumping_enabled); + ClassDB::bind_method(D_METHOD("set_max_traversals", "max_traversals"), &AStarGrid2D::set_max_traversals); + ClassDB::bind_method(D_METHOD("get_max_traversals"), &AStarGrid2D::get_max_traversals); ClassDB::bind_method(D_METHOD("set_diagonal_mode", "mode"), &AStarGrid2D::set_diagonal_mode); ClassDB::bind_method(D_METHOD("get_diagonal_mode"), &AStarGrid2D::get_diagonal_mode); ClassDB::bind_method(D_METHOD("set_default_compute_heuristic", "heuristic"), &AStarGrid2D::set_default_compute_heuristic); @@ -713,6 +732,7 @@ void AStarGrid2D::_bind_methods() { ADD_PROPERTY(PropertyInfo(Variant::INT, "cell_shape", PROPERTY_HINT_ENUM, "Square,IsometricRight,IsometricDown"), "set_cell_shape", "get_cell_shape"); ADD_PROPERTY(PropertyInfo(Variant::BOOL, "jumping_enabled"), "set_jumping_enabled", "is_jumping_enabled"); + ADD_PROPERTY(PropertyInfo(Variant::INT, "max_traversals", PROPERTY_HINT_RANGE, "0,65536,0"), "set_max_traversals", "get_max_traversals"); ADD_PROPERTY(PropertyInfo(Variant::INT, "default_compute_heuristic", PROPERTY_HINT_ENUM, "Euclidean,Manhattan,Octile,Chebyshev"), "set_default_compute_heuristic", "get_default_compute_heuristic"); ADD_PROPERTY(PropertyInfo(Variant::INT, "default_estimate_heuristic", PROPERTY_HINT_ENUM, "Euclidean,Manhattan,Octile,Chebyshev"), "set_default_estimate_heuristic", "get_default_estimate_heuristic"); ADD_PROPERTY(PropertyInfo(Variant::INT, "diagonal_mode", PROPERTY_HINT_ENUM, "Never,Always,At Least One Walkable,Only If No Obstacles"), "set_diagonal_mode", "get_diagonal_mode"); diff --git a/core/math/a_star_grid_2d.h b/core/math/a_star_grid_2d.h index 38cc8d466b..509ace8c7e 100644 --- a/core/math/a_star_grid_2d.h +++ b/core/math/a_star_grid_2d.h @@ -73,6 +73,7 @@ private: CellShape cell_shape = CELL_SHAPE_SQUARE; bool jumping_enabled = false; + int64_t max_traversals = 0; DiagonalMode diagonal_mode = DIAGONAL_MODE_ALWAYS; Heuristic default_compute_heuristic = HEURISTIC_EUCLIDEAN; Heuristic default_estimate_heuristic = HEURISTIC_EUCLIDEAN; @@ -190,6 +191,9 @@ public: void set_jumping_enabled(bool p_enabled); bool is_jumping_enabled() const; + void set_max_traversals(int64_t p_max_traversals); + int64_t get_max_traversals() const; + void set_diagonal_mode(DiagonalMode p_diagonal_mode); DiagonalMode get_diagonal_mode() const; |