1 /*************************************************************************/ 2 /* navigation2d.h */ 3 /*************************************************************************/ 4 /* This file is part of: */ 5 /* GODOT ENGINE */ 6 /* https://godotengine.org */ 7 /*************************************************************************/ 8 /* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ 9 /* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ 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 #ifndef NAVIGATION_2D_H 31 #define NAVIGATION_2D_H 32 33 #include "scene/2d/navigation_polygon.h" 34 #include "scene/2d/node_2d.h" 35 36 class Navigation2D : public Node2D { 37 38 OBJ_TYPE(Navigation2D, Node2D); 39 40 union Point { 41 42 struct { 43 int64_t x : 32; 44 int64_t y : 32; 45 }; 46 47 uint64_t key; 48 bool operator<(const Point &p_key) const { return key < p_key.key; } 49 }; 50 51 struct EdgeKey { 52 53 Point a; 54 Point b; 55 56 bool operator<(const EdgeKey &p_key) const { 57 return (a.key == p_key.a.key) ? (b.key < p_key.b.key) : (a.key < p_key.a.key); 58 }; 59 60 EdgeKey(const Point &p_a = Point(), const Point &p_b = Point()) { 61 a = p_a; 62 b = p_b; 63 if (a.key > b.key) { 64 SWAP(a, b); 65 } 66 } 67 }; 68 69 struct NavMesh; 70 struct Polygon; 71 72 struct ConnectionPending { 73 74 Polygon *polygon; 75 int edge; 76 }; 77 78 struct Polygon { 79 80 struct Edge { 81 Point point; 82 Polygon *C; //connection 83 int C_edge; 84 List<ConnectionPending>::Element *P; EdgePolygon::Edge85 Edge() { 86 C = NULL; 87 C_edge = -1; 88 P = NULL; 89 } 90 }; 91 92 Vector<Edge> edges; 93 94 Vector2 center; 95 Vector2 entry; 96 97 float distance; 98 int prev_edge; 99 100 bool clockwise; 101 102 NavMesh *owner; 103 }; 104 105 struct Connection { 106 107 Polygon *A; 108 int A_edge; 109 Polygon *B; 110 int B_edge; 111 112 List<ConnectionPending> pending; 113 ConnectionConnection114 Connection() { 115 A = NULL; 116 B = NULL; 117 A_edge = -1; 118 B_edge = -1; 119 } 120 }; 121 122 Map<EdgeKey, Connection> connections; 123 124 struct NavMesh { 125 126 Object *owner; 127 Matrix32 xform; 128 bool linked; 129 Ref<NavigationPolygon> navpoly; 130 List<Polygon> polygons; 131 }; 132 _get_point(const Vector2 & p_pos)133 _FORCE_INLINE_ Point _get_point(const Vector2 &p_pos) const { 134 135 int x = int(Math::floor(p_pos.x / cell_size)); 136 int y = int(Math::floor(p_pos.y / cell_size)); 137 138 Point p; 139 p.key = 0; 140 p.x = x; 141 p.y = y; 142 return p; 143 } 144 _get_vertex(const Point & p_point)145 _FORCE_INLINE_ Vector2 _get_vertex(const Point &p_point) const { 146 147 return Vector2(p_point.x, p_point.y) * cell_size; 148 } 149 150 void _navpoly_link(int p_id); 151 void _navpoly_unlink(int p_id); 152 153 float cell_size; 154 Map<int, NavMesh> navpoly_map; 155 int last_id; 156 #if 0 157 void _clip_path(Vector<Vector2>& path,Polygon *from_poly, const Vector2& p_to_point, Polygon* p_to_poly); 158 #endif 159 protected: 160 static void _bind_methods(); 161 162 public: 163 //API should be as dynamic as possible 164 int navpoly_create(const Ref<NavigationPolygon> &p_mesh, const Matrix32 &p_xform, Object *p_owner = NULL); 165 void navpoly_set_transform(int p_id, const Matrix32 &p_xform); 166 void navpoly_remove(int p_id); 167 168 Vector<Vector2> get_simple_path(const Vector2 &p_start, const Vector2 &p_end, bool p_optimize = true); 169 Vector2 get_closest_point(const Vector2 &p_point); 170 Object *get_closest_point_owner(const Vector2 &p_point); 171 172 Navigation2D(); 173 }; 174 175 #endif // Navigation2D2D_H 176