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