1 package com.mygdx.game.AI;
2
3 import com.badlogic.gdx.ai.pfa.Connection;
4 import com.badlogic.gdx.ai.pfa.DefaultGraphPath;
5 import com.badlogic.gdx.ai.pfa.GraphPath;
6 import com.badlogic.gdx.ai.pfa.indexed.IndexedAStarPathFinder;
7 import com.badlogic.gdx.ai.pfa.indexed.IndexedGraph;
8 import com.badlogic.gdx.maps.MapLayer;
9 import com.badlogic.gdx.maps.MapLayers;
10 import com.badlogic.gdx.maps.tiled.TiledMap;
11 import com.badlogic.gdx.maps.tiled.TiledMapTileLayer;
12 import com.badlogic.gdx.math.Vector2;
13 import com.badlogic.gdx.utils.Array;
14 import com.badlogic.gdx.utils.ObjectMap;
15 import com.mygdx.utils.QueueFIFO;
16
17 import static com.mygdx.utils.TileMapCells.OBSTACLE;
18 import static com.mygdx.utils.TileMapCells.PASSABLE;
19
20 /**
21 * The Graphical representation of the tilemap with each cell being bidirectionally to the adjacent nodes.
22 */
23 public class TileMapGraph implements IndexedGraph<Node> {
24 private final NodeHeuristic heuristic;
25 private final Array<Node> nodes;
26 private final Array<Path> paths;
27 private final Vector2 mapDim;
28
29 private final ObjectMap<Node, Array<Connection<Node>>> nodePaths;
30
31 private TileMapGraph() {
32
33 heuristic = new NodeHeuristic();
34 nodes = new Array<>();
35 paths = new Array<>();
36 nodePaths = new ObjectMap<>();
37 mapDim = new Vector2();
38 }
39
40 /**
41 * Creates a Graph from the given tilemap
42 *
43 * @param map the source tilemap
44 */
45 public TileMapGraph(TiledMap map) {
46 this();
47
48 MapLayers layers = map.getLayers();
49 TiledMapTileLayer layer = null;
50
51 // find the collision layer
52 for (MapLayer l : layers) {
53 if (l.getName().equals("Collision")) {
54 layer = (TiledMapTileLayer) l;
55 }
56 }
57 // if there is no collision layer
58 if (layer == null) {
59 return;
60 }
61 // the map dimensions
62 mapDim.set(layer.getWidth(), layer.getHeight());
63
64 nodes.ensureCapacity((int) mapDim.x * (int) mapDim.y);
65
66 // create all the nodes
67 for (int i = 0; i < mapDim.x * mapDim.y; i++) {
68 nodes.add(new Node(0, 0));
69 }
70
71 // for each column
72 for (int x = 0; x < layer.getWidth(); x++) {
73 // for each row
74 for (int y = 0; y < layer.getHeight(); y++) {
75 TiledMapTileLayer.Cell center = layer.getCell(x, y);
76
77 if (getType(center) == OBSTACLE) {
78 continue;
79 }
80 // the central node
81 addNode(x, y);
82
83 // all surrounding nodes
84 for (int i = -1; i < 2; i++) {
85 for (int j = -1; j < 2; j++) {
86
87 // prevents the node pathing to its self
88 if (i == 0 && j == 0) {
89 continue;
90 }
91
92 TiledMapTileLayer.Cell cell = layer.getCell(x + i, y + j);
93 // is cell outside the map
94 if (cell == null) {
95 continue;
96 }
97
98 // is the cell passable
99 if (cell.getTile().getId() == PASSABLE) {
100
101 addNode(x + i, y + j);
102 addPath(x, y, x + i, y + j);
103 }
104 }
105 }
106 }
107 }
108 }
109
110 /**
111 * Node a position (x, y)
112 *
113 * @param x co-ord
114 * @param y co-ord
115 * @return Node at (x, y) or null
116 */
117 public Node getNode(float x, float y) {
118 Node n = nodes.get(getIndex(x, y));
119 if (n.cost == -1) {
120 return null;
121 }
122 return n;
123 }
124
125 private int getIndex(float x, float y) {
126 return (int) (mapDim.x * y + x);
127 }
128
129 /**
130 * @return type of cell as far as the tile map is condensed
131 */
132 private int getType(TiledMapTileLayer.Cell c) {
133 return c.getTile().getId();
134 }
135
136 private int getIndex(int x, int y) {
137 return (int) mapDim.x * y + x;
138 }
139
140 /**
141 * doesn't add if already there
142 *
143 * @param x x pos
144 * @param y y pos
145 */
146 private void addNode(float x, float y) {
147 Node n = nodes.get(getIndex((int) x, (int) y));
148 if (n.cost > 0) {
149 return;
150 }
151 n.set(x, y);
152 n.cost = 1;
153 }
154
155 /**
156 * Adds path to map doesn't check for duplicates
157 *
158 * @param a src
159 * @param b dst
160 */
161 private void addPath(Node a, Node b) {
162 Path path = new Path(a, b);
163
164 if (!nodePaths.containsKey(a)) {
165 nodePaths.put(a, new Array<>());
166 }
167 nodePaths.get(a).add(path);
168 paths.add(path);
169 }
170
171 /**
172 * Adds path to map doesn't check for duplicates
173 *
174 * @param x1 src.x
175 * @param y1 src.y
176 * @param x2 dst.x
177 * @param y2 dst.y
178 */
179 private void addPath(float x1, float y1, float x2, float y2) {
180 Node a = getNode(x1, y1);
181 Node b = getNode(x2, y2);
182
183 addPath(a, b);
184 }
185
186 /**
187 * Finds the path
188 *
189 * @param start the starting node
190 * @param goal the ending node
191 * @return a queue of the nodes to visit null if no path id found
192 */
193 public GraphPath<Node> findPath(Node start, Node goal) {
194 if (start == null || goal == null) {
195 return null;
196 }
197 GraphPath<Node> path = new DefaultGraphPath<>();
198 new IndexedAStarPathFinder<>(this).searchNodePath(start, goal, heuristic, path);
199 return path;
200 }
201
202 /**
203 * Finds a sequence of locations which can be travelled to without collision
204 *
205 * @param a starting node
206 * @param b destination node
207 * @return queue of location to travel to in order
208 */
209 public QueueFIFO<Vector2> findOptimisedPath(Node a, Node b) {
210 GraphPath<Node> path = findPath(a, b);
211 QueueFIFO<Vector2> res = new QueueFIFO<>();
212 Vector2 delta = new Vector2();
213 float sequenceLength = 0; // the amount of times a
214 Vector2 cur = new Vector2();
215
216 Vector2 prev = path.get(0).getPosition();
217 for (int i = 1; i < path.getCount(); i++) {
218 Node n = path.get(i);
219 cur.set(n.getPosition());
220 // d contains the current vector between the current pos an prev
221 Vector2 d = cur.cpy();
222 d.sub(prev);
223
224
225 if (delta.x == d.x && delta.y == d.y) {
226 sequenceLength++;
227 } else {
228 res.add(delta.scl(sequenceLength));
229 delta = d;
230 sequenceLength = 1;
231 }
232 prev.set(cur);
233 }
234 res.remove(0);
235 res.add(delta.scl(sequenceLength));
236 return res;
237 }
238
239 /**
240 * Finds a sequence on locations which can be travelled to without collision
241 *
242 * @param a starting node location
243 * @param b destination node location
244 * @return queue of location to travel to in order
245 */
246 public QueueFIFO<Vector2> findOptimisedPath(Vector2 a, Vector2 b) {
247 Node n1 = getNode(a.x, a.y);
248 Node n2 = getNode(b.x, b.y);
249 return findOptimisedPath(n1, n2);
250 }
251
252 /**
253 * Finds a sequence on locations which can be travelled to without collision
254 *
255 * @param x1 starting node x co-ords tile space
256 * @param y1 starting node y co-ords tile space
257 * @param x2 destination node x co-ords tile space
258 * @param y2 destination node y co-ords tile space
259 * @return queue of location to travel to in order
260 */
261 public QueueFIFO<Vector2> findOptimisedPath(float x1, float y1, float x2, float y2) {
262 Node a = getNode(x1, y1);
263 Node b = getNode(x2, y2);
264 return findOptimisedPath(a, b);
265 }
266
267
268 // The Interface
269 @Override
270 public int getIndex(Node node) {
271 return getIndex(node.getPosition().x, node.getPosition().y);
272 }
273
274 @Override
275 public int getNodeCount() {
276 return (int) (mapDim.x * mapDim.y);
277 }
278
279 @Override
280 public Array<Connection<Node>> getConnections(Node fromNode) {
281 if (nodePaths.containsKey(fromNode)) {
282 return nodePaths.get(fromNode);
283 }
284
285 return new Array<>();
286 }
287 }