1 package cz.cuni.amis.pogamut.defcon.communication.worldview.polygons;
2
3 import java.io.FileNotFoundException;
4 import java.io.IOException;
5 import java.util.ArrayList;
6 import java.util.BitSet;
7 import java.util.Collections;
8 import java.util.Iterator;
9 import java.util.LinkedList;
10 import java.util.List;
11 import java.util.ListIterator;
12 import java.util.SortedMap;
13 import java.util.TreeMap;
14 import java.util.logging.Logger;
15
16 import javabot.PogamutJBotSupport;
17 import cz.cuni.amis.pogamut.base.agent.module.SensorModule;
18 import cz.cuni.amis.pogamut.base.component.controller.ComponentDependencies;
19 import cz.cuni.amis.pogamut.defcon.base3d.worldview.object.DefConLocation;
20 import cz.cuni.amis.pogamut.defcon.agent.DefConAgent;
21 import cz.cuni.amis.pogamut.defcon.communication.worldview.DefConWorldView;
22 import cz.cuni.amis.pogamut.defcon.communication.worldview.modules.grid.flags.BasicFlag;
23 import cz.cuni.amis.pogamut.defcon.communication.worldview.modules.grid.flags.IFlagChecker;
24 import cz.cuni.amis.pogamut.defcon.communication.worldview.polygons.loaders.borders.FilePrecomputedBordersLoader;
25 import cz.cuni.amis.pogamut.defcon.communication.worldview.polygons.loaders.borders.IPrecomputedBordersLoader;
26 import cz.cuni.amis.pogamut.defcon.communication.worldview.polygons.loaders.borders.IPrecomputedBordersSaver;
27 import cz.cuni.amis.pogamut.defcon.utils.Pair;
28 import cz.cuni.amis.utils.iterators.CircularListIterator;
29
30
31
32
33
34
35
36 public class GameMapInfoPolygons extends SensorModule<DefConAgent> {
37
38
39
40
41 protected final float STEP_SIZE = 1f;
42
43
44
45
46
47 protected final float SIMPLIFICATION_FACTOR = 0.1f;
48
49
50
51
52
53 protected ArrayList<Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>> territories =
54 new ArrayList<Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>();
55
56
57
58 protected TreeMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>> ownTerritories =
59 new TreeMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>();
60
61
62
63 protected TreeMap<Integer, SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>> enemyTerritories =
64 new TreeMap<Integer, SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>>();
65
66
67
68 protected List<List<DefConLocation>> land;
69
70
71
72 protected List<List<DefConLocation>> sea;
73
74
75
76
77 protected IFlagChecker flagChecker;
78
79
80
81
82 protected BasicFlag currentFlag;
83
84
85
86
87 protected int currentTerritoryId;
88
89
90
91 protected int currentEnemyId;
92
93 protected int lastAssignedTerritory;
94
95 protected double minX;
96 protected double minY;
97
98 public GameMapInfoPolygons(DefConAgent<?> agent,
99 IFlagChecker flagChecker) {
100 this(agent, flagChecker, null, null);
101 }
102
103 public GameMapInfoPolygons(DefConAgent<?> agent,
104 IFlagChecker flagChecker, String preprocessedPath) {
105 this(agent, flagChecker, preprocessedPath, null);
106 }
107
108 public GameMapInfoPolygons(DefConAgent<?> agent,
109 IFlagChecker flagChecker, String preprocessedPath, Logger log) {
110 this(agent, flagChecker, preprocessedPath, log, null);
111 }
112
113 public GameMapInfoPolygons(DefConAgent<?> agent,
114 IFlagChecker flagChecker, String preprocessedPath, Logger log,
115 ComponentDependencies dependencies) {
116 super(agent, log, dependencies);
117
118 this.flagChecker = flagChecker;
119
120 minX = agent.getWorldView().getMinX();
121 minY = agent.getWorldView().getMaxX();
122
123 for (int i = 0; i < agent.getWorldView().getGameInfo()
124 .getTerritoriesCount(); ++i) {
125 territories
126 .add(new Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>());
127 }
128
129 for (int teamId : agent.getWorldView().getGameInfo().getTeamIds()) {
130 for (int territoryId : agent.getWorldView().getGameInfo()
131 .getTeamTerritories(teamId)) {
132
133 Pair<List<List<DefConLocation>>, List<List<DefConLocation>>> territory =
134 territories.get(territoryId);
135
136 if (lastAssignedTerritory < territoryId)
137 lastAssignedTerritory = territoryId;
138
139 if (agent.getWorldView().getGameInfo().getOwnTeamId() == teamId) {
140 ownTerritories.put(territoryId, territory);
141 } else {
142 SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>> setOfEnemiesTerritories =
143 new TreeMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>();
144 enemyTerritories.put(teamId, setOfEnemiesTerritories);
145 setOfEnemiesTerritories.put(territoryId, territory);
146 }
147 }
148 }
149
150 if (preprocessedPath == null)
151 processMap();
152 else
153 loadBorders(preprocessedPath);
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176 }
177
178
179 public void saveBorders(IPrecomputedBordersSaver saver) {
180 log.info("Saving borders");
181
182 for (BasicFlag flag : new FlagColl()) {
183
184 log.info("Saving: " + flag + " "
185 + currentTerritoryId);
186 String type = null;
187 List<List<DefConLocation>> territory = null;
188
189 try {
190 switch (flag) {
191 case ENEMY_PLACEABLE_LAND:
192 case OWN_PLACEABLE_LAND:
193 type = "LAND";
194 territory = territories.get(currentTerritoryId).second;
195 case ENEMY_PLACEABLE_SEA:
196 case OWN_PLACEABLE_SEA:
197 if (type == null) {
198 type = "SEA";
199 territory = territories.get(currentTerritoryId).first;
200 }
201 saver.saveBorderOfTerritory("TERRITORY_" + type
202 + "_"
203 + currentTerritoryId
204 + "_border.def", territory);
205 break;
206 case SEA:
207 territory = sea;
208 case LAND:
209 if (territory == null)
210 territory = land;
211 saver.saveBorderOfTerritory(
212 flag + "_border.def",
213 territory);
214 break;
215 }
216 } catch (IOException e) {
217 e.printStackTrace();
218 }
219 }
220 }
221
222
223
224
225
226
227 private void loadBorders(String preprocessedPath) {
228 log.info("Loading borders");
229
230 IPrecomputedBordersLoader loader = new FilePrecomputedBordersLoader(preprocessedPath);
231 for (BasicFlag flag : new FlagColl()) {
232
233 log.info("Loading: " + flag + " "
234 + currentTerritoryId);
235
236 List<List<DefConLocation>> borders;
237
238 try {
239 String type = null;
240 switch (flag) {
241 case ENEMY_PLACEABLE_LAND:
242 case OWN_PLACEABLE_LAND:
243 type = "LAND";
244 case ENEMY_PLACEABLE_SEA:
245 case OWN_PLACEABLE_SEA:
246 if (type == null)
247 type = "SEA";
248
249 borders = loader
250 .loadBordersForTerritory("TERRITORY_" + type
251 + "_"
252 + currentTerritoryId
253 + "_border.def");
254 break;
255 default: {
256 borders = loader
257 .loadBordersForTerritory(flag + "_border.def");
258 break;
259 }
260 }
261
262 switch (flag) {
263 case ENEMY_PLACEABLE_SEA:
264 case OWN_PLACEABLE_SEA: {
265 territories.get(currentTerritoryId).first = borders;
266 break;
267 }
268 case OWN_PLACEABLE_LAND:
269 case ENEMY_PLACEABLE_LAND: {
270 territories.get(currentTerritoryId).second = borders;
271 break;
272 }
273 case SEA: {
274 sea = borders;
275 break;
276 }
277 case LAND: {
278 land = borders;
279 break;
280 }
281 }
282
283 } catch (NumberFormatException e) {
284
285 e.printStackTrace();
286 } catch (FileNotFoundException e) {
287
288 e.printStackTrace();
289 } catch (IOException e) {
290
291 e.printStackTrace();
292 }
293 }
294 }
295
296 public DefConWorldView getWorldView() {
297 return (DefConWorldView) worldView;
298 }
299
300
301
302
303
304
305
306
307 private final int convertCoordsToVisitedIndex(Coords coords) {
308 return coords.getX() * coords.getYSize() + coords.getY();
309 }
310
311 private class FlagColl implements Iterable<BasicFlag> {
312
313 @Override
314 public Iterator<BasicFlag> iterator() {
315 currentFlag = null;
316 currentTerritoryId = -1;
317 currentEnemyId = -1;
318 return new FlagIterator();
319 }
320
321 private class FlagIterator implements Iterator<BasicFlag> {
322
323 Iterator<Integer> territoryIterator;
324 ArrayList<BasicFlag> acceptedFlags = new ArrayList<BasicFlag>();
325 Iterator<BasicFlag> flagIterator;
326
327 public FlagIterator() {
328 territoryIterator = null;
329 currentFlag = null;
330 currentEnemyId = -1;
331 currentTerritoryId = -1;
332
333 if (enemyTerritories.keySet().size() == 0) {
334 for (BasicFlag flag : BasicFlag.values()) {
335 switch (flag) {
336 case ENEMY_PLACEABLE_LAND:
337 case ENEMY_PLACEABLE_SEA:
338 case ENEMY_TERRITORY:
339 case OWN_TERRITORY:
340 continue;
341 default:
342 acceptedFlags.add(flag);
343 }
344 }
345 } else {
346 for (BasicFlag flag : BasicFlag.values()) {
347 switch (flag) {
348 case ENEMY_TERRITORY:
349 case OWN_TERRITORY:
350 continue;
351 default:
352 acceptedFlags.add(flag);
353 }
354 }
355 }
356
357 flagIterator = acceptedFlags.iterator();
358 }
359
360 @Override
361 public boolean hasNext() {
362
363 if (!flagIterator.hasNext())
364 switch (currentFlag) {
365 case ENEMY_PLACEABLE_LAND:
366 case ENEMY_PLACEABLE_SEA:
367 case OWN_PLACEABLE_LAND:
368 case OWN_PLACEABLE_SEA:
369 return (territoryIterator != null && territoryIterator
370 .hasNext());
371 default:
372 return false;
373 }
374 else {
375 return true;
376 }
377 }
378
379 @Override
380 public BasicFlag next() {
381
382 if (currentFlag == null) {
383 return putFlagIntoEffect(flagIterator.next());
384 }
385
386 switch (currentFlag) {
387 case ENEMY_PLACEABLE_LAND:
388 case ENEMY_PLACEABLE_SEA:
389 case OWN_PLACEABLE_LAND:
390 case OWN_PLACEABLE_SEA:
391 if (territoryIterator != null &&
392 territoryIterator.hasNext()) {
393
394 currentTerritoryId = -1;
395
396 territoryIterator: while (territoryIterator
397 .hasNext()
398 && (currentTerritoryId < lastAssignedTerritory)) {
399
400 currentTerritoryId = territoryIterator.next();
401
402 currentEnemyId = agent.getWorldView()
403 .getGameInfo()
404 .getTerritoryOwner(currentTerritoryId);
405
406
407 switch (currentFlag) {
408 case ENEMY_PLACEABLE_LAND:
409 case ENEMY_PLACEABLE_SEA:
410 if (agent.getWorldView()
411 .getGameInfo()
412 .getOwnTeamId() != currentEnemyId) {
413 break territoryIterator;
414 }
415 break;
416 default:
417 break territoryIterator;
418 }
419
420 }
421
422 if (currentTerritoryId != -1) {
423 return currentFlag;
424 }
425 }
426 default:
427 territoryIterator = null;
428 if (flagIterator.hasNext()) {
429 return putFlagIntoEffect(flagIterator.next());
430 } else {
431 return null;
432 }
433 }
434 }
435
436 @Override
437 public void remove() {
438 throw new UnsupportedOperationException(
439 "Flag iterator does not support remove operation.");
440 }
441
442 private BasicFlag putFlagIntoEffect(BasicFlag flag) {
443 switch (flag) {
444 case OWN_PLACEABLE_LAND:
445 case OWN_PLACEABLE_SEA:
446 territoryIterator = ownTerritories
447 .keySet().iterator();
448 currentFlag = flag;
449 return next();
450 case ENEMY_PLACEABLE_LAND:
451 case ENEMY_PLACEABLE_SEA:
452 territoryIterator = agent
453 .getWorldView()
454 .getGameInfo()
455 .getAllEnemyTerritories()
456 .iterator();
457 currentFlag = flag;
458 return next();
459 default:
460 return currentFlag = flag;
461 }
462 }
463
464 }
465 }
466
467
468
469
470 protected void processMap() {
471
472 BitSet visited = new BitSet();
473 for (BasicFlag flag : new FlagColl()) {
474
475 visited.clear();
476
477 ArrayList<List<DefConLocation>> borders = new ArrayList<List<DefConLocation>>();
478
479 Coords coords = new Coords(0, 0);
480
481
482 for (coords.setX(0); coords.getX() < coords.getXSize(); coords
483 .setX(coords.getX() + 1)) {
484
485 for (coords.setY(0); coords.getY() < coords.getYSize(); coords
486 .setY(coords.getY() + 1)) {
487
488 int visited_index = convertCoordsToVisitedIndex(coords);
489 if (!visited.get(visited_index)
490 && isBorder(coords, flag)) {
491
492 LinkedList<DefConLocation> poly =
493 getFloodFillBorder(coords, flag, visited);
494
495 if (poly != null && poly.size() > 0) {
496 borders.add(Collections
497 .unmodifiableList(smoothPoly(poly)));
498 }
499 }
500 visited.set(visited_index);
501
502 }
503 }
504
505 log.info("Finished: " + flag);
506
507 switch (flag) {
508 case OWN_PLACEABLE_LAND:
509 case OWN_PLACEABLE_SEA:
510 case ENEMY_PLACEABLE_LAND:
511 case ENEMY_PLACEABLE_SEA: {
512
513 Pair<List<List<DefConLocation>>, List<List<DefConLocation>>> pair = territories
514 .get(currentTerritoryId);
515
516 switch (flag) {
517 case OWN_PLACEABLE_SEA:
518 case ENEMY_PLACEABLE_SEA:
519 pair.first = borders;
520 break;
521 case OWN_PLACEABLE_LAND:
522 case ENEMY_PLACEABLE_LAND:
523 pair.second = borders;
524 break;
525 }
526 }
527 break;
528 case LAND:
529 land = borders;
530 break;
531 case SEA:
532 sea = borders;
533 break;
534 }
535 }
536 PogamutJBotSupport.writeToConsole("mapInfo done");
537 System.gc();
538 }
539
540
541
542
543
544
545
546 private LinkedList<DefConLocation> smoothPoly(
547 LinkedList<DefConLocation> poly) {
548 if (poly.size() <= 3)
549 return poly;
550
551 ListIterator<DefConLocation> iter = poly.listIterator(1);
552 DefConLocation first = iter.next(), second = null;
553 DefConLocation third = poly.peekFirst();
554 boolean last = false;
555 DefConLocation last_dir = null;
556
557 while (iter.hasNext()) {
558 second = first;
559 first = iter.next();
560
561 if (first.equals(third))
562 continue;
563
564 if (areNeighbours(first, third) &&
565 (!last || last_dir.equals(third.sub(first).getNormalized(), 0.1f))) {
566 iter.previous();
567 iter.previous();
568 iter.remove();
569
570 if (!last)
571 last_dir = new DefConLocation(third.sub(first)
572 .getNormalized());
573
574 first = iter.next();
575 last = true;
576 } else {
577 third = second;
578 last = false;
579 }
580 }
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598 return poly;
599 }
600
601
602
603
604
605
606
607
608 private boolean areNeighbours(DefConLocation first, DefConLocation second) {
609
610 return ((Math.abs(first.getX() - second.getX()) <= 1) ||
611 (Math.abs(first.getX() - second.getX())
612 - getWorldView().getMinX() <= 1))
613 &&
614 (Math.abs(first.getY() - second.getY()) <= 1);
615 }
616
617 private boolean isPossibleBorderStartPoint(Coords coords, BasicFlag flag) {
618 if (coords == null)
619 return false;
620
621 if (!flagCheck(coords.getLocation()))
622 return false;
623
624 DefConLocation neighbour_location = Direction.LEFT
625 .getLocationInThisDirection(coords);
626
627 if (neighbour_location != null
628 && flagCheck(neighbour_location))
629 return false;
630
631 neighbour_location = Direction.LOWER.getLocationInThisDirection(coords);
632
633
634 if (neighbour_location != null
635 && flagCheck(neighbour_location))
636 return false;
637
638 return true;
639 }
640
641 private boolean isBorder(Coords coords, BasicFlag flag) {
642
643 if (coords == null)
644 return false;
645
646 if (!flagCheck(coords.getLocation()))
647 return false;
648
649 DefConLocation neighbour_location;
650
651
652
653 neighbour_location = Direction.RIGHT.getLocationInThisDirection(coords);
654
655 if (neighbour_location == null
656 || !flagCheck(neighbour_location))
657 return true;
658
659 neighbour_location = Direction.LEFT.getLocationInThisDirection(coords);
660
661 if (neighbour_location == null
662 || !flagCheck(neighbour_location))
663 return true;
664
665 neighbour_location = Direction.UPPER.getLocationInThisDirection(coords);
666
667 if (neighbour_location == null
668 || !flagCheck(neighbour_location))
669 return true;
670
671 neighbour_location = Direction.LOWER.getLocationInThisDirection(coords);
672
673 if (neighbour_location == null
674 || !flagCheck(neighbour_location))
675 return true;
676
677
678
679 neighbour_location = Direction.UPPER_RIGHT
680 .getLocationInThisDirection(coords);
681
682 if (neighbour_location == null
683 || !flagCheck(neighbour_location))
684 return true;
685
686 neighbour_location = Direction.UPPER_LEFT
687 .getLocationInThisDirection(coords);
688
689 if (neighbour_location == null
690 || !flagCheck(neighbour_location))
691 return true;
692
693 neighbour_location = Direction.LOWER_RIGHT
694 .getLocationInThisDirection(coords);
695
696 if (neighbour_location == null
697 || !flagCheck(neighbour_location))
698 return true;
699
700 neighbour_location = Direction.LOWER_LEFT
701 .getLocationInThisDirection(coords);
702
703 if (neighbour_location == null
704 || !flagCheck(neighbour_location))
705 return true;
706
707 return false;
708 }
709
710 private boolean isStandAloneCell(Coords coords, BasicFlag flag) {
711 if (coords == null)
712 return false;
713
714 if (!isPossibleBorderStartPoint(coords, flag))
715 return false;
716
717 DefConLocation neighbour_location = coords.getLocation();
718
719 neighbour_location = Direction.RIGHT.getLocationInThisDirection(coords);
720
721 if (neighbour_location != null
722 && flagCheck(neighbour_location))
723 return false;
724
725 neighbour_location = Direction.UPPER.getLocationInThisDirection(coords);
726
727 if (neighbour_location != null
728 && flagCheck(neighbour_location))
729 return false;
730
731 return true;
732 }
733
734 private class Coords {
735 private int x;
736 private int y;
737
738 public Coords(int x, int y) {
739 this.x = x;
740 this.y = y;
741 filterRestrictedCoords();
742 }
743
744 public Coords(Coords source) {
745 this.x = source.x;
746 this.y = source.y;
747 filterRestrictedCoords();
748 }
749
750 public int getX() {
751 return x;
752 }
753
754 public int getY() {
755 return y;
756 }
757
758 public int setX(int x) {
759 this.x = x;
760 filterRestrictedCoords();
761
762 return this.x;
763 }
764
765 public int setY(int y) {
766 this.y = y;
767 filterRestrictedCoords();
768
769 return this.y;
770 }
771
772 public DefConLocation getLocation() {
773 DefConLocation ret = new DefConLocation(x * STEP_SIZE
774 + getWorldView().getMinX(), -(y * STEP_SIZE
775 + getWorldView().getMinY()));
776
777 return ret;
778 }
779
780 public final int getXSize() {
781 return (int) Math.floor(getWorldView().getXSize() / STEP_SIZE);
782 }
783
784 public final int getYSize() {
785 return (int) Math.floor(getWorldView().getYSize() / STEP_SIZE);
786 }
787
788 private final void filterRestrictedCoords() {
789 if (this.y < 0 || this.y > getYSize())
790 throw new IllegalArgumentException(
791 "Coords cant have y out of bounds");
792
793 if (this.x < 0 || this.x > getXSize())
794 throw new IllegalArgumentException(
795 "Coords cant have x out of bounds");
796 }
797
798 private final void filterCoords() {
799 if (this.y < 0 || this.y > getYSize())
800 throw new IllegalArgumentException(
801 "Coords cant have y out of bounds");
802
803 this.x = (int) (this.x % getXSize());
804 }
805
806 public final GameMapInfoPolygons getOwner() {
807 return GameMapInfoPolygons.this;
808 }
809
810 @Override
811 public boolean equals(Object o) {
812 return (((Coords) o).x == x) && (((Coords) o).y == y);
813 }
814
815 public void setCoords(Coords coords) {
816 this.x = coords.x;
817 this.y = coords.y;
818
819 filterRestrictedCoords();
820 }
821
822 @Override
823 public String toString() {
824 return "Coords: [ " + x + " ; " + y + " ] ";
825 }
826 }
827
828 private LinkedList<DefConLocation> getFloodFillBorder(Coords coords,
829 BasicFlag flag, BitSet visited) {
830
831 int visited_index = convertCoordsToVisitedIndex(coords);
832 if (!isBorder(coords, flag) || visited.get(visited_index)) {
833 return null;
834 }
835
836 LinkedList<DefConLocation> polygon = new LinkedList<DefConLocation>();
837
838 Coords first_coords = new Coords(coords);
839 Coords old_coords = new Coords(coords);
840 coords = new Coords(coords);
841
842 Direction direction = Direction.RIGHT;
843 Direction old_direction = Direction.LEFT;
844
845 visited.set(visited_index);
846
847 if (!isStandAloneCell(first_coords, flag)) {
848
849 do {
850 direction = turnAsLeftAsPossible(direction, coords, flag);
851
852 coords = direction.getPointInThisDirection(old_coords);
853
854 visited_index = convertCoordsToVisitedIndex(coords);
855 visited.set(visited_index);
856
857 if (direction != old_direction) {
858 polygon.add(old_coords.getLocation());
859 }
860 old_coords.setCoords(coords);
861 old_direction = direction;
862
863
864
865
866 if (coords.equals(first_coords)) {
867 direction = turnAsLeftAsPossible(direction, coords, flag);
868
869 coords = direction.getPointInThisDirection(old_coords);
870
871 visited_index = convertCoordsToVisitedIndex(coords);
872
873 if (visited.get(visited_index)) {
874 break;
875 }
876
877 visited.set(visited_index);
878
879 if (direction != old_direction) {
880 polygon.add(old_coords.getLocation());
881 }
882 old_coords.setCoords(coords);
883 old_direction = direction;
884 }
885
886 } while (!coords.equals(first_coords));
887
888 } else {
889 polygon.add(first_coords.getLocation());
890 }
891
892 return polygon;
893 }
894
895 private Direction turnAsLeftAsPossible(Direction direction, Coords coords,
896 BasicFlag flag) {
897 direction = direction.turnLeft4Way();
898
899 while (!isBorder(direction.getPointInThisDirection(coords), flag)) {
900 direction = direction.turnRight4Way();
901 }
902
903 return direction;
904 }
905
906 private Coords getFilteredCoords(int x, int y) {
907 try {
908 return new Coords(x, y);
909 } catch (IllegalArgumentException e) {
910 return null;
911 }
912 }
913
914 private enum Direction {
915 RIGHT(1, 0), UPPER_RIGHT(1, -1), UPPER(0, -1), UPPER_LEFT(-1, -1), LEFT(
916 -1, 0), LOWER_LEFT(-1, 1), LOWER(0, 1), LOWER_RIGHT(1, 1);
917
918 public final int x;
919 public final int y;
920
921 private Direction(int x, int y) {
922 this.x = x;
923 this.y = y;
924 }
925
926 public Direction reverse() {
927 switch (this) {
928 case RIGHT:
929 return LEFT;
930 case UPPER_RIGHT:
931 return LOWER_LEFT;
932 case UPPER:
933 return LOWER;
934 case UPPER_LEFT:
935 return LOWER_RIGHT;
936 case LEFT:
937 return RIGHT;
938 case LOWER_LEFT:
939 return UPPER_RIGHT;
940 case LOWER:
941 return UPPER;
942 case LOWER_RIGHT:
943 return UPPER_LEFT;
944 }
945 return null;
946 }
947
948 public Direction turnLeft() {
949 switch (this) {
950 case RIGHT:
951 return UPPER_RIGHT;
952 case UPPER_RIGHT:
953 return UPPER;
954 case UPPER:
955 return UPPER_LEFT;
956 case UPPER_LEFT:
957 return LEFT;
958 case LEFT:
959 return LOWER_LEFT;
960 case LOWER_LEFT:
961 return LOWER;
962 case LOWER:
963 return LOWER_RIGHT;
964 case LOWER_RIGHT:
965 return RIGHT;
966 }
967 return null;
968 }
969
970 public Direction turnRight() {
971 switch (this) {
972 case RIGHT:
973 return LOWER_RIGHT;
974 case LOWER_RIGHT:
975 return LOWER;
976 case LOWER:
977 return LOWER_LEFT;
978 case LOWER_LEFT:
979 return LEFT;
980 case LEFT:
981 return UPPER_LEFT;
982 case UPPER_LEFT:
983 return UPPER;
984 case UPPER:
985 return UPPER_RIGHT;
986 case UPPER_RIGHT:
987 return RIGHT;
988 }
989 return null;
990 }
991
992 public Direction turnRight4Way() {
993 switch (this) {
994 case LOWER_RIGHT:
995 case UPPER_RIGHT:
996 case LOWER_LEFT:
997 case UPPER_LEFT:
998 return null;
999 }
1000 return turnRight().turnRight();
1001 }
1002
1003 public Direction turnLeft4Way() {
1004 switch (this) {
1005 case LOWER_RIGHT:
1006 case UPPER_RIGHT:
1007 case LOWER_LEFT:
1008 case UPPER_LEFT:
1009 return null;
1010 }
1011 return turnLeft().turnLeft();
1012 }
1013
1014 public DefConLocation getLocationInThisDirection(Coords coords) {
1015
1016 try {
1017 switch (this) {
1018 case RIGHT:
1019 return coords.getOwner().getFilteredCoords(
1020 coords.getX() + 1, coords.getY()).getLocation();
1021 case UPPER:
1022 return coords.getOwner().getFilteredCoords(coords.getX(),
1023 coords.getY() + 1).getLocation();
1024 case LEFT:
1025 return coords.getOwner().getFilteredCoords(
1026 coords.getX() - 1, coords.getY()).getLocation();
1027 case LOWER:
1028 return coords.getOwner().getFilteredCoords(coords.getX(),
1029 coords.getY() - 1).getLocation();
1030 case UPPER_RIGHT:
1031 return coords.getOwner().getFilteredCoords(
1032 coords.getX() + 1, coords.getY() + 1)
1033 .getLocation();
1034 case UPPER_LEFT:
1035 return coords.getOwner().getFilteredCoords(
1036 coords.getX() - 1, coords.getY() + 1)
1037 .getLocation();
1038 case LOWER_LEFT:
1039 return coords.getOwner().getFilteredCoords(
1040 coords.getX() - 1, coords.getY() - 1)
1041 .getLocation();
1042 case LOWER_RIGHT:
1043 return coords.getOwner().getFilteredCoords(
1044 coords.getX() + 1, coords.getY() - 1)
1045 .getLocation();
1046 }
1047 } catch (IllegalArgumentException e) {
1048 return null;
1049 } catch (NullPointerException e) {
1050 return null;
1051 }
1052 return null;
1053 }
1054
1055 public Coords getPointInThisDirection(Coords coords) {
1056 switch (this) {
1057 case RIGHT:
1058 return coords.getOwner().getFilteredCoords(coords.getX() + 1,
1059 coords.getY());
1060 case UPPER:
1061 return coords.getOwner().getFilteredCoords(coords.getX(),
1062 coords.getY() + 1);
1063 case LEFT:
1064 return coords.getOwner().getFilteredCoords(coords.getX() - 1,
1065 coords.getY());
1066 case LOWER:
1067 return coords.getOwner().getFilteredCoords(coords.getX(),
1068 coords.getY() - 1);
1069 case UPPER_RIGHT:
1070 return coords.getOwner().getFilteredCoords(coords.getX() + 1,
1071 coords.getY() + 1);
1072 case UPPER_LEFT:
1073 return coords.getOwner().getFilteredCoords(coords.getX() - 1,
1074 coords.getY() + 1);
1075 case LOWER_LEFT:
1076 return coords.getOwner().getFilteredCoords(coords.getX() - 1,
1077 coords.getY() - 1);
1078 case LOWER_RIGHT:
1079 return coords.getOwner().getFilteredCoords(coords.getX() + 1,
1080 coords.getY() - 1);
1081 }
1082 return null;
1083 }
1084
1085 };
1086
1087
1088
1089
1090
1091
1092
1093
1094 private LinkedList<DefConLocation> simplifyPoly(
1095 LinkedList<DefConLocation> poly) {
1096
1097 double area = approximatePolyArea(poly);
1098
1099 if (poly.size() <= 2)
1100 return poly;
1101
1102 while (poly.size() * poly.size() / area > SIMPLIFICATION_FACTOR) {
1103 Edge lightest_edge = getLightestEdge(poly);
1104
1105 area -= lightest_edge.weighEdge();
1106 lightest_edge.removeIntermediateVertices();
1107 }
1108
1109 return null;
1110 }
1111
1112 private final double approximatePolyArea(LinkedList<DefConLocation> poly) {
1113
1114 if (poly.size() <= 1)
1115 return 0d;
1116
1117 double area = 0d;
1118
1119 Iterator<DefConLocation> iter = poly.iterator();
1120 DefConLocation look_back = iter.next();
1121
1122 while (iter.hasNext()) {
1123 DefConLocation current = new DefConLocation(iter.next());
1124
1125 current.sub(new DefConLocation(minX, minY));
1126 area += look_back.getX() * current.getY();
1127 area -= look_back.getY() * current.getX();
1128 }
1129
1130 area += look_back.getX() * poly.getFirst().getY();
1131 area -= look_back.getY() * poly.getFirst().getX();
1132
1133 return 0.5f * area;
1134 }
1135
1136 private boolean flagCheck(DefConLocation location) {
1137
1138 switch (currentFlag) {
1139 case ENEMY_TERRITORY:
1140 return flagChecker.hasEnemyTerritoryFlag(
1141 location,
1142 currentEnemyId);
1143 case ENEMY_PLACEABLE_LAND:
1144 return flagChecker.hasEnemyTerritoryFlag(
1145 location,
1146 currentEnemyId, false);
1147 case ENEMY_PLACEABLE_SEA:
1148 return flagChecker.hasEnemyTerritoryFlag(
1149 location,
1150 currentEnemyId, true);
1151 default:
1152 return flagChecker.hasFlag(location, currentFlag);
1153 }
1154
1155 }
1156
1157 private Edge getLightestEdge(LinkedList<DefConLocation> poly) {
1158
1159 if (poly.size() <= 2)
1160 return null;
1161
1162 CircularListIterator<DefConLocation> tmp = new CircularListIterator<DefConLocation>(
1163 poly);
1164 tmp.next();
1165 Edge lightest_edge = new Edge(new CircularListIterator<DefConLocation>(
1166 poly), tmp, poly);
1167 double lightest_weight = Double.POSITIVE_INFINITY;
1168
1169 CircularListIterator<DefConLocation> first_iter = new CircularListIterator<DefConLocation>(
1170 poly);
1171
1172 while (!first_iter.hasPassedBeginning()) {
1173 DefConLocation first = first_iter.next();
1174
1175 CircularListIterator<DefConLocation> second_iter =
1176 new CircularListIterator<DefConLocation>(first_iter);
1177
1178 while (!second_iter.hasPassedEnd()) {
1179 DefConLocation second = second_iter.next();
1180 double weight;
1181
1182 if (second == first)
1183 continue;
1184
1185 if (lightest_weight > (weight = lightest_edge.weighEdge(
1186 first_iter.previousIter(),
1187 second_iter.previousIter(),
1188 poly))) {
1189
1190 lightest_edge = new Edge(first_iter, second_iter, poly);
1191 lightest_weight = weight;
1192 }
1193 first_iter.next(); second_iter.next();
1194 }
1195 }
1196
1197 return lightest_edge;
1198 }
1199
1200 private class Edge {
1201 public CircularListIterator<DefConLocation> first, second;
1202 public LinkedList<DefConLocation> poly;
1203
1204 public Edge(CircularListIterator<DefConLocation> first,
1205 CircularListIterator<DefConLocation> second,
1206 LinkedList<DefConLocation> poly) {
1207
1208 if (first == null || second == null || poly == null)
1209 throw new NullPointerException(
1210 "None of the parameters of Edge construction should be null.");
1211
1212 this.first = new CircularListIterator<DefConLocation>(first);
1213 this.second = new CircularListIterator<DefConLocation>(second);
1214 this.poly = poly;
1215 }
1216
1217 public void removeIntermediateVertices() {
1218 while (first.next() != second.next()) {
1219 first.remove();
1220 first.previous();
1221 second.previous();
1222 }
1223 }
1224
1225 public final double weighEdge() {
1226 return weighEdge(this);
1227 }
1228
1229 public final double weighEdge(
1230 CircularListIterator<DefConLocation> first,
1231 CircularListIterator<DefConLocation> second,
1232 LinkedList<DefConLocation> poly) {
1233 LinkedList<DefConLocation> subPoly = new LinkedList<DefConLocation>();
1234 CircularListIterator<DefConLocation> first_iter = new CircularListIterator<DefConLocation>(
1235 first);
1236 CircularListIterator<DefConLocation> second_iter = new CircularListIterator<DefConLocation>(
1237 second);
1238
1239 DefConLocation current = first_iter.next();
1240 DefConLocation last = second_iter.next();
1241
1242 while (current != last) {
1243 subPoly.add(current);
1244 current = first_iter.next();
1245 }
1246 return approximatePolyArea(subPoly);
1247 }
1248
1249 public final double weighEdge(Edge edge) {
1250 LinkedList<DefConLocation> subPoly = new LinkedList<DefConLocation>();
1251 CircularListIterator<DefConLocation> first_iter = edge.getFirst();
1252 CircularListIterator<DefConLocation> second_iter = edge.getSecond();
1253
1254 DefConLocation current = first_iter.next();
1255 DefConLocation last = second_iter.next();
1256
1257 while (current != last) {
1258 subPoly.add(current);
1259 current = first_iter.next();
1260 }
1261 return approximatePolyArea(subPoly);
1262 }
1263
1264 public CircularListIterator<DefConLocation> getFirst() {
1265 return new CircularListIterator<DefConLocation>(first);
1266 }
1267
1268 public CircularListIterator<DefConLocation> getSecond() {
1269 return new CircularListIterator<DefConLocation>(second);
1270 }
1271 }
1272
1273 private static final float mathModulus(float a, float b) {
1274 return (a % b + b) % b;
1275 }
1276
1277 private static final List<DefConLocation> checkAndJoinBordersOnSeam(
1278 List<DefConLocation> borderA, List<DefConLocation> borderB) {
1279
1280
1281
1282 return null;
1283 }
1284
1285 public SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>> getOwnTerritories() {
1286 return Collections.unmodifiableSortedMap(ownTerritories);
1287 }
1288
1289 public SortedMap<Integer, SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>>>
1290 getEnemiesTerritories() {
1291 return Collections.unmodifiableSortedMap(enemyTerritories);
1292 }
1293
1294
1295
1296
1297
1298
1299
1300 public Pair<List<List<DefConLocation>>, List<List<DefConLocation>>> getTerritory(
1301 int territoryId) {
1302 return territories.get(territoryId);
1303 }
1304
1305
1306
1307
1308
1309
1310
1311 public SortedMap<Integer, Pair<List<List<DefConLocation>>, List<List<DefConLocation>>>> getEnemyTerritories(
1312 int enemyId) {
1313 if (!enemyTerritories.containsKey(enemyId)) {
1314 throw new IllegalArgumentException(
1315 "getEnemyTerritories does not contain " + enemyId +
1316 " only contains "
1317 + enemyTerritories.keySet().toString());
1318 }
1319 return Collections.unmodifiableSortedMap(enemyTerritories
1320 .get(enemyId));
1321 }
1322
1323
1324
1325
1326
1327
1328 public List<List<DefConLocation>> getLand() {
1329 return Collections.unmodifiableList(land);
1330 }
1331
1332
1333
1334
1335
1336
1337 public List<List<DefConLocation>> getSea() {
1338 return Collections.unmodifiableList(sea);
1339 }
1340 }