1 package cz.cuni.amis.pogamut.defcon.utils.closestpoints;
2
3 import java.util.ArrayList;
4 import java.util.Iterator;
5 import java.util.List;
6 import java.util.Map.Entry;
7 import java.util.PriorityQueue;
8 import java.util.Queue;
9 import java.util.SortedMap;
10 import java.util.TreeMap;
11 import java.util.logging.Logger;
12
13 import cz.cuni.amis.pogamut.defcon.agent.module.sensor.GameInfo;
14 import cz.cuni.amis.pogamut.defcon.base3d.worldview.object.DefConLocation;
15 import cz.cuni.amis.pogamut.defcon.utils.Pair;
16 import cz.cuni.amis.pogamut.defcon.utils.quadtree.QuadTree;
17 import cz.cuni.amis.pogamut.defcon.utils.quadtree.QuadTreeBFSIterator;
18 import cz.cuni.amis.pogamut.defcon.utils.quadtree.QuadTreeNode;
19 import cz.cuni.amis.pogamut.defcon.utils.quadtree.WidthLimitedQuadTreePostorderIterator;
20
21
22
23
24
25
26
27 public class ClosestPointsLookUp {
28
29 private GameInfo gameInfo;
30 private Logger log;
31 private SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> enemyQuadTrees;
32 private SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> ownQuadTrees;
33
34 private boolean isFinished = false;
35
36 private Iterator<Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>>> enemyTerritoryIterator;
37 private Iterator<QuadTree> enemyQuadTreeIterator;
38 private Iterator<Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>>> ownTerritoriesIterator;
39
40 private Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>> enemyTerritory;
41 private QuadTree enemyQuadTree;
42 private int enemyId;
43
44 private final SortedMap<Integer, SortedMap<Integer, List<ClosestPoints>>> closestPointsToEnemyTerritories =
45 new TreeMap<Integer, SortedMap<Integer, List<ClosestPoints>>>();
46 private SortedMap<Integer, List<ClosestPoints>> closestPointsToAnEnemyTerritory;
47 private int pointsLimit;
48
49 public static final SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> prepareEnemyQuadTrees(
50 SortedMap<Integer, SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>>> enemyQuadTrees) {
51
52 SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> output = new TreeMap<Integer, Pair<List<QuadTree>, List<QuadTree>>>();
53
54 for (SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> territory : enemyQuadTrees
55 .values()) {
56 output.putAll(territory);
57 }
58
59 return output;
60 }
61
62 public ClosestPointsLookUp(
63 GameInfo gameInfo,
64 Logger log,
65 SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> enemyQuadTrees,
66 SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> ownQuadTrees) {
67
68 this(gameInfo, log, enemyQuadTrees, ownQuadTrees, 20);
69 }
70
71 public ClosestPointsLookUp(
72 GameInfo gameInfo,
73 Logger log,
74 SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> enemyQuadTrees,
75 SortedMap<Integer, Pair<List<QuadTree>, List<QuadTree>>> ownQuadTrees,
76 int pointsLimit) {
77
78 this.gameInfo = gameInfo;
79 this.log = log;
80 this.enemyQuadTrees = enemyQuadTrees;
81 this.ownQuadTrees = ownQuadTrees;
82 this.enemyTerritoryIterator = enemyQuadTrees.entrySet().iterator();
83 this.pointsLimit = pointsLimit;
84 }
85
86
87
88
89
90
91
92
93 public ClosestPointsManager getTickedClosestPoints() {
94 tickGetClosestPointsWorker();
95 return (isFinished) ? new ClosestPointsManager(
96 closestPointsToEnemyTerritories, log)
97 : null;
98 }
99
100
101
102
103
104
105
106
107 public ClosestPointsManager getClosestPoints() {
108
109 for (Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>> enemy_territory : enemyQuadTrees
110 .entrySet()) {
111
112 enemyId = gameInfo.getTerritoryOwner(enemy_territory.getKey());
113
114
115
116
117 closestPointsToAnEnemyTerritory = new TreeMap<Integer, List<ClosestPoints>>();
118
119 closestPointsToEnemyTerritories.put(
120 enemy_territory.getKey(),
121 closestPointsToAnEnemyTerritory);
122
123
124 for (QuadTree enemy_sea : enemy_territory.getValue().first) {
125
126
127 for (Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>> own_territory : ownQuadTrees
128 .entrySet()) {
129
130
131 List<ClosestPoints> points;
132
133 if (closestPointsToAnEnemyTerritory
134 .containsKey(own_territory.getKey())) {
135 points = closestPointsToAnEnemyTerritory
136 .get(own_territory.getKey());
137 } else {
138 points = new ArrayList<ClosestPoints>();
139 closestPointsToAnEnemyTerritory.put(
140 own_territory.getKey(),
141 points);
142 }
143
144
145
146
147
148
149 for (QuadTree own_sea : own_territory.getValue().first) {
150
151
152 ClosestPoints result = findClosestPointsBetweenTwoTrees(
153 enemy_sea,
154 own_sea);
155
156 if (result != null) {
157 boolean found = false;
158 for (ClosestPoints point : points) {
159 if (point.getTarget()
160 .equals(result.getTarget())) {
161 found = true;
162 point.addOrigins(result
163 .getCompleteOrigins());
164 break;
165 }
166 }
167
168 if (!found) {
169 points.add(result);
170 }
171 }
172 }
173 }
174 }
175 }
176
177 return new ClosestPointsManager(
178 closestPointsToEnemyTerritories, log);
179 }
180
181 public class ClosestPoints {
182 private DefConLocation target;
183
184 private List<DistanceOrigin> completeOrigins = new ArrayList<DistanceOrigin>(
185 pointsLimit);
186
187 private List<DefConLocation> origins = new ArrayList<DefConLocation>(
188 pointsLimit);
189
190 public ClosestPoints(DefConLocation target) {
191 this.target = target;
192 }
193
194 public final DefConLocation getTarget() {
195 return target;
196 }
197
198 public final List<DistanceOrigin> getCompleteOrigins() {
199 return completeOrigins;
200 }
201
202 public final List<DefConLocation> getOrigins() {
203 return origins;
204 }
205
206
207
208
209
210
211 public void initOrigins(Queue<DistanceOrigin> origins) {
212
213 if (origins == null)
214 throw new IllegalArgumentException("Origins cannot be null.");
215
216 while (this.completeOrigins.size() < pointsLimit
217 && !origins.isEmpty()) {
218
219 DistanceOrigin origin = origins.poll();
220 this.completeOrigins.add(origin);
221 this.origins.add(origin.getOrigin());
222 }
223 }
224
225
226
227
228
229
230 public void addOrigins(List<DistanceOrigin> origins) {
231
232 if (origins == null)
233 throw new IllegalArgumentException("Origins cannot be null.");
234
235 ArrayList<DistanceOrigin> tmp = new ArrayList<DistanceOrigin>(10);
236
237 this.origins.clear();
238
239 int completeOriginsIndex = 0;
240 int originsIndex = 0;
241 int counter = 0;
242 while (counter < pointsLimit && originsIndex < origins.size()
243 && completeOriginsIndex < completeOrigins.size()) {
244
245 DistanceOrigin origin;
246
247 if (origins.get(originsIndex).compareTo(
248 completeOrigins.get(completeOriginsIndex)) < 0) {
249 origin = origins.get(originsIndex);
250 ++originsIndex;
251 } else {
252 origin = completeOrigins.get(completeOriginsIndex);
253 ++completeOriginsIndex;
254 }
255
256 tmp.add(origin);
257 this.origins.add(origin.getOrigin());
258 ++counter;
259 }
260
261 this.completeOrigins = tmp;
262 }
263
264 }
265
266 public class DistanceOrigin implements Comparable<DistanceOrigin> {
267 public double distance;
268 public DefConLocation origin;
269
270 public DistanceOrigin(double distance, DefConLocation origin) {
271 this.distance = distance;
272 this.origin = origin;
273 }
274
275 public final double getDistance() {
276 return distance;
277 }
278
279 public final DefConLocation getOrigin() {
280 return origin;
281 }
282
283 @Override
284 public int compareTo(DistanceOrigin o) {
285 return Double.compare(distance, o.distance);
286 }
287 }
288
289 private ClosestPoints findClosestPointsBetweenTwoTrees(
290 QuadTree enemyTerritory, QuadTree myTerritory) {
291
292 QuadTreeNode outer_closest = null;
293
294 if (enemyTerritory.getRoot().getSize() <= 5d)
295 return null;
296
297 if (myTerritory.getRoot().getSize() <= gameInfo
298 .getFleetDiameter(6))
299 return null;
300
301 Iterator<QuadTreeNode> nodeIterator = new QuadTreeBFSIterator(
302 enemyTerritory);
303 while (nodeIterator.hasNext()) {
304
305 QuadTreeNode node = nodeIterator.next();
306
307 if (!gameInfo.isValidTerritory(
308 enemyId,
309 node.getCenter(),
310 true))
311 continue;
312
313 outer_closest = node;
314
315
316
317
318 break;
319 }
320
321 if (outer_closest == null)
322 return null;
323
324 ClosestPoints closest = new ClosestPoints(new DefConLocation(
325 outer_closest.getCenter()));
326 PriorityQueue<DistanceOrigin> origins = new PriorityQueue<DistanceOrigin>();
327
328 WidthLimitedQuadTreePostorderIterator inner_iter =
329 new WidthLimitedQuadTreePostorderIterator(
330 myTerritory,
331 gameInfo
332 .getFleetDiameter(6));
333
334 while (inner_iter.hasNext()) {
335 QuadTreeNode inner_node = inner_iter.next();
336
337 if (!inner_node.isLabeled() || !gameInfo.isValidFleetPlacement(
338 inner_node.getCenter(),
339 6)) {
340 continue;
341 }
342
343 double dist = gameInfo.getSailDistance(
344 inner_node.getCenter(),
345 outer_closest.getCenter());
346
347 origins.add(new DistanceOrigin(dist, new DefConLocation(inner_node
348 .getCenter())));
349
350
351
352
353 }
354
355 closest.initOrigins(origins);
356
357 return closest;
358 }
359
360 private void tickGetClosestPointsWorker() {
361 if (ownTerritoriesIterator != null
362 && ownTerritoriesIterator.hasNext()) {
363
364 Entry<Integer, Pair<List<QuadTree>, List<QuadTree>>> ownTerritory = ownTerritoriesIterator
365 .next();
366
367 log.info("MyTerritory: " + ownTerritory.getKey());
368
369 List<ClosestPoints> points;
370 if (!closestPointsToAnEnemyTerritory.containsKey(ownTerritory
371 .getKey())) {
372 points = new ArrayList<ClosestPoints>();
373
374 closestPointsToAnEnemyTerritory.put(
375 ownTerritory.getKey(),
376 points);
377 } else {
378 points = closestPointsToAnEnemyTerritory.get(ownTerritory
379 .getKey());
380 }
381
382 for (QuadTree ownSea : ownTerritory.getValue().first) {
383
384 log.info("MyQTree");
385
386 ClosestPoints return_value = findClosestPointsBetweenTwoTrees(
387 enemyQuadTree,
388 ownSea);
389
390 if (return_value != null) {
391 boolean found = false;
392 for (ClosestPoints point : points) {
393 if (point.getTarget().equals(return_value.getTarget())) {
394 found = true;
395 point.addOrigins(return_value.getCompleteOrigins());
396 break;
397 }
398 }
399
400 if (!found) {
401 points.add(return_value);
402 }
403 }
404 }
405
406 return;
407 } else if (enemyQuadTreeIterator != null &&
408 enemyQuadTreeIterator.hasNext()) {
409
410 enemyQuadTree = enemyQuadTreeIterator.next();
411
412 log.info("EnemyQTree " + enemyQuadTree.getRoot().getCenter());
413
414 ownTerritoriesIterator = ownQuadTrees.entrySet().iterator();
415
416 tickGetClosestPointsWorker();
417 } else if (enemyTerritoryIterator.hasNext()) {
418
419 enemyTerritory = enemyTerritoryIterator.next();
420
421 enemyId = gameInfo.getTerritoryOwner(enemyTerritory.getKey());
422
423 log.info("EnemyTerritory " + enemyTerritory.getKey() + " of "
424 + enemyId);
425
426
427 enemyQuadTreeIterator = enemyTerritory.getValue().first
428 .iterator();
429
430
431 closestPointsToAnEnemyTerritory = new TreeMap<Integer, List<ClosestPoints>>();
432
433 closestPointsToEnemyTerritories.put(
434 enemyTerritory.getKey(),
435 closestPointsToAnEnemyTerritory);
436
437 tickGetClosestPointsWorker();
438
439 }
440
441 if (!enemyTerritoryIterator.hasNext()) {
442
443 if (enemyQuadTreeIterator == null
444 || !enemyQuadTreeIterator.hasNext()) {
445
446 if (ownTerritoriesIterator == null
447 || !ownTerritoriesIterator.hasNext()) {
448 isFinished = true;
449 }
450 }
451
452 }
453 }
454 }