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