summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPacien TRAN-GIRARD2015-11-24 18:32:47 +0100
committerPacien TRAN-GIRARD2015-11-24 18:34:15 +0100
commit7a71ddfd0a103abeab1280aa33583d28f7e8e756 (patch)
tree413c507273782b12a7a9fa304a680d09dc2e5515 /src
parent9bec90d20c20b01e94a8b5d8364bbe60f9687f05 (diff)
downloadmaze-solver-7a71ddfd0a103abeab1280aa33583d28f7e8e756.tar.gz
Refactor Panda A.I.
Diffstat (limited to 'src')
-rw-r--r--src/ch/epfl/maze/physical/zoo/Panda.java130
-rw-r--r--src/ch/epfl/maze/util/Trail.java2
2 files changed, 78 insertions, 54 deletions
diff --git a/src/ch/epfl/maze/physical/zoo/Panda.java b/src/ch/epfl/maze/physical/zoo/Panda.java
index f4c2035..2f46b6d 100644
--- a/src/ch/epfl/maze/physical/zoo/Panda.java
+++ b/src/ch/epfl/maze/physical/zoo/Panda.java
@@ -1,7 +1,8 @@
1package ch.epfl.maze.physical.zoo; 1package ch.epfl.maze.physical.zoo;
2 2
3import ch.epfl.maze.physical.Animal; 3import ch.epfl.maze.physical.Animal;
4import ch.epfl.maze.physical.ProbabilisticAnimal; 4import ch.epfl.maze.physical.stragegies.picker.RandomPicker;
5import ch.epfl.maze.physical.stragegies.reducer.BackwardReducer;
5import ch.epfl.maze.util.Direction; 6import ch.epfl.maze.util.Direction;
6import ch.epfl.maze.util.Trail; 7import ch.epfl.maze.util.Trail;
7import ch.epfl.maze.util.Vector2D; 8import ch.epfl.maze.util.Vector2D;
@@ -16,7 +17,7 @@ import java.util.stream.Collectors;
16 * @author EPFL 17 * @author EPFL
17 * @author Pacien TRAN-GIRARD 18 * @author Pacien TRAN-GIRARD
18 */ 19 */
19public class Panda extends ProbabilisticAnimal { 20public class Panda extends Animal implements BackwardReducer, RandomPicker {
20 21
21 private final Trail trail; 22 private final Trail trail;
22 23
@@ -27,20 +28,65 @@ public class Panda extends ProbabilisticAnimal {
27 */ 28 */
28 public Panda(Vector2D position) { 29 public Panda(Vector2D position) {
29 super(position); 30 super(position);
31
30 this.trail = new Trail(); 32 this.trail = new Trail();
31 } 33 }
32 34
33 /** 35 /**
36 * Reduces the set of Direction choice using <i>Trémeaux's Algorithm</i> and,
37 * if possible, avoiding going backward.
38 *
39 * @param choices A set of possible choices
40 * @return A subset of choices
41 */
42 @Override
43 public Set<Direction> reduce(Set<Direction> choices) {
44 Set<Direction> bestChoices = this.selectBestDirections(choices);
45 return bestChoices.size() > 1 ? BackwardReducer.super.reduce(bestChoices) : bestChoices;
46 }
47
48 /**
49 * Moves according to <i>Trémeaux's Algorithm</i>: when the panda
50 * moves, it will mark the ground at most two times (with two different
51 * colors). It will prefer taking the least marked paths. Special cases
52 * have to be handled, especially when the panda is at an intersection.
53 */
54 @Override
55 public Direction move(Set<Direction> choices) {
56 Direction choice = this.pick(this.reduce(choices));
57
58 if (this.shouldMarkCurrentPosition(choices, choice))
59 this.markCurrentPosition(choices);
60
61 return choice;
62 }
63
64 @Override
65 public Animal copy() {
66 return new Panda(this.getPosition());
67 }
68
69 /**
34 * Checks if the current position is an intersection given the possible choices. 70 * Checks if the current position is an intersection given the possible choices.
35 * 71 *
36 * @param choices A set of possible Directions 72 * @param choices A set of possible Directions
37 * @return T(the current position is an intersection) 73 * @return T(The set of choices corresponds to an intersection)
38 */ 74 */
39 private boolean isIntersection(Set<Direction> choices) { 75 private boolean onIntersection(Set<Direction> choices) {
40 return choices.size() > 2; 76 return choices.size() > 2;
41 } 77 }
42 78
43 /** 79 /**
80 * Checks if the current position is a dead end.
81 *
82 * @param choices A set of possible Directions
83 * @return T(The set of choices and their Marking corresponds to a dead end)
84 */
85 private boolean inDeadEnd(Set<Direction> choices) {
86 return choices.size() == 1 && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING);
87 }
88
89 /**
44 * Get the Marking at the adjacent position given the Direction. 90 * Get the Marking at the adjacent position given the Direction.
45 * 91 *
46 * @param dir The Direction from the current position 92 * @param dir The Direction from the current position
@@ -52,6 +98,32 @@ public class Panda extends ProbabilisticAnimal {
52 } 98 }
53 99
54 /** 100 /**
101 * Determines if the current position should be marked according to the rules of the <i>Trémeaux's Algorithm</i>,
102 * avoiding intersections over-marking.
103 *
104 * @param choices A set of possible Directions
105 * @param choice The selected Direction
106 * @return T(the current position should be marked)
107 */
108 private boolean shouldMarkCurrentPosition(Set<Direction> choices, Direction choice) {
109 return !(this.onIntersection(choices)
110 && this.trail.getMarking(this.getPosition()) == Trail.Marking.AVOID_MARKING
111 && this.getMarkingAtDirection(choice) == Trail.Marking.NO_MARKING);
112 }
113
114 /**
115 * Marks the current position according to the rules of the <i>Trémeaux's Algorithm</i>.
116 *
117 * @param choices A set of possible Direction to take
118 */
119 private void markCurrentPosition(Set<Direction> choices) {
120 if (this.inDeadEnd(choices))
121 this.trail.markPosition(this.getPosition(), Trail.Marking.NO_GO_MARKING);
122 else
123 this.trail.markPosition(this.getPosition());
124 }
125
126 /**
55 * Checks if all Direction choices are leading to the given Marking. 127 * Checks if all Direction choices are leading to the given Marking.
56 * 128 *
57 * @param choices A set of possible Directions 129 * @param choices A set of possible Directions
@@ -86,7 +158,7 @@ public class Panda extends ProbabilisticAnimal {
86 */ 158 */
87 private Set<Direction> selectBestDirections(Set<Direction> choices) { 159 private Set<Direction> selectBestDirections(Set<Direction> choices) {
88 // special case 160 // special case
89 if (this.isIntersection(choices) && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING)) 161 if (this.onIntersection(choices) && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING))
90 return EnumSet.of(this.getDirection().reverse()); 162 return EnumSet.of(this.getDirection().reverse());
91 163
92 // general case 164 // general case
@@ -99,52 +171,4 @@ public class Panda extends ProbabilisticAnimal {
99 return EnumSet.noneOf(Direction.class); 171 return EnumSet.noneOf(Direction.class);
100 } 172 }
101 173
102 /**
103 * Determines if the current position should be marked according to the rules of the <i>Trémeaux's Algorithm</i>,
104 * avoiding intersections over-marking.
105 *
106 * @param choices A set of possible Directions
107 * @param choice The selected Direction
108 * @return T(the current position should be marked)
109 */
110 private boolean shouldMarkCurrentPosition(Set<Direction> choices, Direction choice) {
111 return !(this.isIntersection(choices)
112 && this.trail.getMarking(this.getPosition()) == Trail.Marking.AVOID_MARKING
113 && this.getMarkingAtDirection(choice) == Trail.Marking.NO_MARKING);
114 }
115
116 /**
117 * Marks the current position according to the rules of the <i>Trémeaux's Algorithm</i>.
118 *
119 * @param choices A set of possible Direction to take
120 */
121 private void markCurrentPosition(Set<Direction> choices) {
122 if (choices.size() == 1 && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING)) // dead end
123 this.trail.markPosition(this.getPosition(), Trail.Marking.NO_GO_MARKING);
124 else
125 this.trail.markPosition(this.getPosition());
126 }
127
128 /**
129 * Moves according to <i>Trémeaux's Algorithm</i>: when the panda
130 * moves, it will mark the ground at most two times (with two different
131 * colors). It will prefer taking the least marked paths. Special cases
132 * have to be handled, especially when the panda is at an intersection.
133 */
134 @Override
135 public Direction move(Set<Direction> choices) {
136 Set<Direction> smartChoices = this.selectBestDirections(choices);
137 Direction choice = super.move(smartChoices);
138
139 if (this.shouldMarkCurrentPosition(choices, choice))
140 this.markCurrentPosition(choices);
141
142 return choice;
143 }
144
145 @Override
146 public Animal copy() {
147 return new Panda(this.getPosition());
148 }
149
150} 174}
diff --git a/src/ch/epfl/maze/util/Trail.java b/src/ch/epfl/maze/util/Trail.java
index ed806c5..33e0975 100644
--- a/src/ch/epfl/maze/util/Trail.java
+++ b/src/ch/epfl/maze/util/Trail.java
@@ -54,7 +54,7 @@ public class Trail {
54 */ 54 */
55 public Marking getMarking(Vector2D position) { 55 public Marking getMarking(Vector2D position) {
56 Marking marking = this.trail.get(position); 56 Marking marking = this.trail.get(position);
57 return marking != null ? marking : Marking.DEFAULT; 57 return marking != null ? marking : Marking.NO_MARKING;
58 } 58 }
59 59
60 /** 60 /**