1 /*
2 pathfinder.h
3 Copyright (C) 2013 sapier, sapier at gmx dot net
4 */
5
6 /*
7 This file is part of Freeminer.
8
9 Freeminer is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Freeminer is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Freeminer. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23 #ifndef PATHFINDER_H_
24 #define PATHFINDER_H_
25
26 /******************************************************************************/
27 /* Includes */
28 /******************************************************************************/
29 #include <vector>
30 #include <string>
31 #include <map>
32 #include <cstdlib>
33
34 #include "irr_v3d.h"
35
36
37 /******************************************************************************/
38 /* Forward declarations */
39 /******************************************************************************/
40
41 class ServerEnvironment;
42
43 /******************************************************************************/
44 /* Typedefs and macros */
45 /******************************************************************************/
46
47 /** List of supported algorithms */
48 enum Algorithm
49 {
50 A_STAR
51 };
52
53 enum Adjacency
54 {
55 ADJACENCY_4,
56 ADJACENCY_8
57 };
58
59 /******************************************************************************/
60 /* declarations */
61 /******************************************************************************/
62
63 /** c wrapper function to use from scriptapi */
64 std::vector<v3POS> getPath(ServerEnvironment* env,
65 v3POS source,
66 v3POS destination,
67 unsigned int searchdistance,
68 unsigned int max_jump,
69 unsigned int max_drop,
70 Algorithm algo,
71 Adjacency adjacency);
72
73 struct OpenElement
74 {
75 OpenElement();
76 OpenElement(unsigned int _f_value, unsigned int _distance, v3POS _pos, v3POS _prev_pos);
77 OpenElement& operator=(const OpenElement& e);
78 bool operator<(const OpenElement& e) const;
79
80 unsigned int f_value;
81 unsigned int start_cost;
82 v3POS pos;
83 v3POS prev_pos;
84 };
85
86 /** class doing pathfinding */
87 class PathFinder
88 {
89 public:
90 PathFinder();
91
92 /**
93 * path evaluation function
94 * @param env environment to look for path
95 * @param source origin of path
96 * @param destination end position of path
97 * @param searchdistance maximum number of nodes to look in each direction
98 * @param max_jump maximum number of blocks a path may jump up
99 * @param max_drop maximum number of blocks a path may drop
100 * @param algo algorithm to use for finding a path
101 */
102 std::vector<v3POS> getPath(ServerEnvironment* env,
103 v3POS source,
104 v3POS destination,
105 unsigned int searchdistance,
106 unsigned int max_jump,
107 unsigned int max_drop,
108 Algorithm algo,
109 Adjacency adjacency);
110
111 private:
112 struct limits {
113 struct limit {
114 int min;
115 int max;
116 };
117
118 limit X;
119 limit Y;
120 limit Z;
121 };
122
123 unsigned int getDirectionCost(unsigned int id);
124
125 /* algorithm functions */
126
127 /**
128 * calculate 2d manahttan distance to target
129 * @param pos position to calc distance
130 * @return integer distance
131 */
132 inline static unsigned int getManhattanDistance(v3POS pos1, v3POS pos2);
133
134 /**
135 * This method finds closest path to the target
136 */
137
138 bool findPathHeuristic(v3POS pos, std::vector <v3POS>& adjacencies,
139 unsigned int (*heuristicFunction)(v3POS, v3POS));
140
141 /**
142 * Create a vector containing all nodes from source to destination
143 * @param path vector to add nodes to
144 * @param pos pos to check next
145 * @param level recursion depth
146 */
147 void buildPath(std::vector<v3POS>& path, v3POS start_pos, v3POS end_pos);
148
149 int m_searchdistance; /**< max distance to search in each direction */
150 int m_maxdrop; /**< maximum number of blocks a path may drop */
151 int m_maxjump; /**< maximum number of blocks a path may jump */
152
153 v3POS m_start; /**< source position */
154 v3POS m_destination; /**< destination position */
155
156 limits m_limits; /**< position limits in real map coordinates */
157
158 ServerEnvironment* m_env; /**< minetest environment pointer */
159
160 Adjacency m_adjacency;
161
162 std::vector <v3POS> m_adjacency_4;
163 std::vector <v3POS> m_adjacency_8;
164
165 std::vector <unsigned int> m_adjacency_4_cost;
166 std::vector <unsigned int> m_adjacency_8_cost;
167
168 std::map <v3POS, std::pair <v3POS, unsigned int> > used;
169 };
170
getManhattanDistance(v3POS pos1,v3POS pos2)171 inline unsigned int PathFinder::getManhattanDistance(v3POS pos1, v3POS pos2)
172 {
173 return abs(pos1.X - pos2.X) + abs(pos1.Z - pos2.Z);
174 }
175
176 #endif /* PATHFINDER_H_ */
177