1/**************************************************************************/
2/* a_star_grid_2d.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef A_STAR_GRID_2D_H
32#define A_STAR_GRID_2D_H
33
34#include "core/object/gdvirtual.gen.inc"
35#include "core/object/ref_counted.h"
36#include "core/templates/list.h"
37#include "core/templates/local_vector.h"
38
39class AStarGrid2D : public RefCounted {
40 GDCLASS(AStarGrid2D, RefCounted);
41
42public:
43 enum DiagonalMode {
44 DIAGONAL_MODE_ALWAYS,
45 DIAGONAL_MODE_NEVER,
46 DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE,
47 DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES,
48 DIAGONAL_MODE_MAX,
49 };
50
51 enum Heuristic {
52 HEURISTIC_EUCLIDEAN,
53 HEURISTIC_MANHATTAN,
54 HEURISTIC_OCTILE,
55 HEURISTIC_CHEBYSHEV,
56 HEURISTIC_MAX,
57 };
58
59private:
60 Rect2i region;
61 Vector2 offset;
62 Size2 cell_size = Size2(1, 1);
63 bool dirty = false;
64
65 bool jumping_enabled = false;
66 DiagonalMode diagonal_mode = DIAGONAL_MODE_ALWAYS;
67 Heuristic default_compute_heuristic = HEURISTIC_EUCLIDEAN;
68 Heuristic default_estimate_heuristic = HEURISTIC_EUCLIDEAN;
69
70 struct Point {
71 Vector2i id;
72
73 bool solid = false;
74 Vector2 pos;
75 real_t weight_scale = 1.0;
76
77 // Used for pathfinding.
78 Point *prev_point = nullptr;
79 real_t g_score = 0;
80 real_t f_score = 0;
81 uint64_t open_pass = 0;
82 uint64_t closed_pass = 0;
83
84 Point() {}
85
86 Point(const Vector2i &p_id, const Vector2 &p_pos) :
87 id(p_id), pos(p_pos) {}
88 };
89
90 struct SortPoints {
91 _FORCE_INLINE_ bool operator()(const Point *A, const Point *B) const { // Returns true when the Point A is worse than Point B.
92 if (A->f_score > B->f_score) {
93 return true;
94 } else if (A->f_score < B->f_score) {
95 return false;
96 } else {
97 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.
98 }
99 }
100 };
101
102 LocalVector<LocalVector<Point>> points;
103 Point *end = nullptr;
104
105 uint64_t pass = 1;
106
107private: // Internal routines.
108 _FORCE_INLINE_ bool _is_walkable(int64_t p_x, int64_t p_y) const {
109 if (region.has_point(Vector2i(p_x, p_y))) {
110 return !points[p_y - region.position.y][p_x - region.position.x].solid;
111 }
112 return false;
113 }
114
115 _FORCE_INLINE_ Point *_get_point(int64_t p_x, int64_t p_y) {
116 if (region.has_point(Vector2i(p_x, p_y))) {
117 return &points[p_y - region.position.y][p_x - region.position.x];
118 }
119 return nullptr;
120 }
121
122 _FORCE_INLINE_ Point *_get_point_unchecked(int64_t p_x, int64_t p_y) {
123 return &points[p_y - region.position.y][p_x - region.position.x];
124 }
125
126 void _get_nbors(Point *p_point, LocalVector<Point *> &r_nbors);
127 Point *_jump(Point *p_from, Point *p_to);
128 bool _solve(Point *p_begin_point, Point *p_end_point);
129
130protected:
131 static void _bind_methods();
132
133 virtual real_t _estimate_cost(const Vector2i &p_from_id, const Vector2i &p_to_id);
134 virtual real_t _compute_cost(const Vector2i &p_from_id, const Vector2i &p_to_id);
135
136 GDVIRTUAL2RC(real_t, _estimate_cost, Vector2i, Vector2i)
137 GDVIRTUAL2RC(real_t, _compute_cost, Vector2i, Vector2i)
138
139public:
140 void set_region(const Rect2i &p_region);
141 Rect2i get_region() const;
142
143 void set_size(const Size2i &p_size);
144 Size2i get_size() const;
145
146 void set_offset(const Vector2 &p_offset);
147 Vector2 get_offset() const;
148
149 void set_cell_size(const Size2 &p_cell_size);
150 Size2 get_cell_size() const;
151
152 void update();
153
154 int get_width() const;
155 int get_height() const;
156
157 bool is_in_bounds(int p_x, int p_y) const;
158 bool is_in_boundsv(const Vector2i &p_id) const;
159 bool is_dirty() const;
160
161 void set_jumping_enabled(bool p_enabled);
162 bool is_jumping_enabled() const;
163
164 void set_diagonal_mode(DiagonalMode p_diagonal_mode);
165 DiagonalMode get_diagonal_mode() const;
166
167 void set_default_compute_heuristic(Heuristic p_heuristic);
168 Heuristic get_default_compute_heuristic() const;
169
170 void set_default_estimate_heuristic(Heuristic p_heuristic);
171 Heuristic get_default_estimate_heuristic() const;
172
173 void set_point_solid(const Vector2i &p_id, bool p_solid = true);
174 bool is_point_solid(const Vector2i &p_id) const;
175
176 void set_point_weight_scale(const Vector2i &p_id, real_t p_weight_scale);
177 real_t get_point_weight_scale(const Vector2i &p_id) const;
178
179 void fill_solid_region(const Rect2i &p_region, bool p_solid = true);
180 void fill_weight_scale_region(const Rect2i &p_region, real_t p_weight_scale);
181
182 void clear();
183
184 Vector2 get_point_position(const Vector2i &p_id) const;
185 Vector<Vector2> get_point_path(const Vector2i &p_from, const Vector2i &p_to);
186 TypedArray<Vector2i> get_id_path(const Vector2i &p_from, const Vector2i &p_to);
187};
188
189VARIANT_ENUM_CAST(AStarGrid2D::DiagonalMode);
190VARIANT_ENUM_CAST(AStarGrid2D::Heuristic);
191
192#endif // A_STAR_GRID_2D_H
193