1 /*************************************************************************/
2 /*  polygon_path_finder.h                                                */
3 /*************************************************************************/
4 /*                       This file is part of:                           */
5 /*                           GODOT ENGINE                                */
6 /*                      https://godotengine.org                          */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur.                 */
9 /* Copyright (c) 2014-2020 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 
31 #ifndef POLYGON_PATH_FINDER_H
32 #define POLYGON_PATH_FINDER_H
33 
34 #include "core/resource.h"
35 
36 class PolygonPathFinder : public Resource {
37 
38 	GDCLASS(PolygonPathFinder, Resource);
39 
40 	struct Point {
41 		Vector2 pos;
42 		Set<int> connections;
43 		float distance;
44 		float penalty;
45 		int prev;
46 	};
47 
48 	struct Edge {
49 
50 		int points[2];
51 
52 		_FORCE_INLINE_ bool operator<(const Edge &p_edge) const {
53 
54 			if (points[0] == p_edge.points[0])
55 				return points[1] < p_edge.points[1];
56 			else
57 				return points[0] < p_edge.points[0];
58 		}
59 
60 		Edge(int a = 0, int b = 0) {
61 
62 			if (a > b) {
63 				SWAP(a, b);
64 			}
65 			points[0] = a;
66 			points[1] = b;
67 		}
68 	};
69 
70 	Vector2 outside_point;
71 	Rect2 bounds;
72 
73 	Vector<Point> points;
74 	Set<Edge> edges;
75 
76 	bool _is_point_inside(const Vector2 &p_point) const;
77 
78 	void _set_data(const Dictionary &p_data);
79 	Dictionary _get_data() const;
80 
81 protected:
82 	static void _bind_methods();
83 
84 public:
85 	void setup(const Vector<Vector2> &p_points, const Vector<int> &p_connections);
86 	Vector<Vector2> find_path(const Vector2 &p_from, const Vector2 &p_to);
87 
88 	void set_point_penalty(int p_point, float p_penalty);
89 	float get_point_penalty(int p_point) const;
90 
91 	bool is_point_inside(const Vector2 &p_point) const;
92 	Vector2 get_closest_point(const Vector2 &p_point) const;
93 	Vector<Vector2> get_intersections(const Vector2 &p_from, const Vector2 &p_to) const;
94 	Rect2 get_bounds() const;
95 
96 	PolygonPathFinder();
97 };
98 
99 #endif // POLYGON_PATH_FINDER_H
100