1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
package ch.epfl.maze.physical.zoo;
import ch.epfl.maze.physical.Animal;
import ch.epfl.maze.physical.stragegies.picker.RandomPicker;
import ch.epfl.maze.physical.stragegies.reducer.BackwardReducer;
import ch.epfl.maze.util.Direction;
import ch.epfl.maze.util.Trail;
import ch.epfl.maze.util.Vector2D;
import java.util.EnumSet;
import java.util.Set;
import java.util.stream.Collectors;
/**
* Panda A.I. that implements Trémeaux's Algorithm.
*
* @author EPFL
* @author Pacien TRAN-GIRARD
*/
public class Panda extends Animal implements BackwardReducer, RandomPicker {
private final Trail trail;
/**
* Constructs a panda with a starting position.
*
* @param position Starting position of the panda in the labyrinth
*/
public Panda(Vector2D position) {
super(position);
this.trail = new Trail();
}
/**
* Reduces the set of Direction choice using <i>Trémeaux's Algorithm</i> and,
* if possible, avoiding going backward.
*
* @param choices A set of possible choices
* @return A subset of choices
*/
@Override
public Set<Direction> reduce(Set<Direction> choices) {
Set<Direction> bestChoices = this.selectBestDirections(choices);
return bestChoices.size() > 1 ? BackwardReducer.super.reduce(bestChoices) : bestChoices;
}
/**
* Moves according to <i>Trémeaux's Algorithm</i>: when the panda
* moves, it will mark the ground at most two times (with two different
* colors). It will prefer taking the least marked paths. Special cases
* have to be handled, especially when the panda is at an intersection.
*/
@Override
public Direction move(Set<Direction> choices) {
Direction choice = this.pick(this.reduce(choices));
if (this.shouldMarkCurrentPosition(choices, choice))
this.markCurrentPosition(choices);
return choice;
}
@Override
public Animal copy() {
return new Panda(this.getPosition());
}
/**
* Checks if the current position is an intersection given the possible choices.
*
* @param choices A set of possible Directions
* @return T(The set of choices corresponds to an intersection)
*/
private boolean onIntersection(Set<Direction> choices) {
return choices.size() > 2;
}
/**
* Checks if the current position is a dead end.
*
* @param choices A set of possible Directions
* @return T(The set of choices and their Marking corresponds to a dead end)
*/
private boolean inDeadEnd(Set<Direction> choices) {
return choices.size() == 1 && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING);
}
/**
* Get the Marking at the adjacent position given the Direction.
*
* @param dir The Direction from the current position
* @return The Marking
*/
private Trail.Marking getMarkingAtDirection(Direction dir) {
Vector2D pos = this.getPosition().addDirectionTo(dir);
return this.trail.getMarking(pos);
}
/**
* Determines if the current position should be marked according to the rules of the <i>Trémeaux's Algorithm</i>,
* avoiding intersections over-marking.
*
* @param choices A set of possible Directions
* @param choice The selected Direction
* @return T(the current position should be marked)
*/
private boolean shouldMarkCurrentPosition(Set<Direction> choices, Direction choice) {
return !(this.onIntersection(choices)
&& this.trail.getMarking(this.getPosition()) == Trail.Marking.AVOID_MARKING
&& this.getMarkingAtDirection(choice) == Trail.Marking.NO_MARKING);
}
/**
* Marks the current position according to the rules of the <i>Trémeaux's Algorithm</i>.
*
* @param choices A set of possible Direction to take
*/
private void markCurrentPosition(Set<Direction> choices) {
if (this.inDeadEnd(choices))
this.trail.markPosition(this.getPosition(), Trail.Marking.NO_GO_MARKING);
else
this.trail.markPosition(this.getPosition());
}
/**
* Checks if all Direction choices are leading to the given Marking.
*
* @param choices A set of possible Directions
* @param marking The Marking
* @return T(all choices are leading to positions with the given Marking)
*/
private boolean allChoicesLeadingTo(Set<Direction> choices, Trail.Marking marking) {
return choices
.stream()
.allMatch(dir -> this.getMarkingAtDirection(dir) == marking);
}
/**
* Selects the Direction choices leading to the given Marking.
*
* @param choices A set of possible Directions
* @param marking The Marking
* @return A set of choices leading to the given Marking
*/
private Set<Direction> selectDirectionsWithMarking(Set<Direction> choices, Trail.Marking marking) {
return choices
.stream()
.filter(dir -> this.getMarkingAtDirection(dir) == marking)
.collect(Collectors.toSet());
}
/**
* Selects the best choices according to the neighbours Markings.
*
* @param choices A set of possible Directions
* @return A set of smart choices
*/
private Set<Direction> selectBestDirections(Set<Direction> choices) {
// special case
if (this.onIntersection(choices) && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING))
return EnumSet.of(this.getDirection().reverse());
// general case
for (Trail.Marking mark : Trail.Marking.ALL) {
Set<Direction> smartChoices = this.selectDirectionsWithMarking(choices, mark);
if (!smartChoices.isEmpty()) return smartChoices;
}
// panda is trapped :(
return EnumSet.noneOf(Direction.class);
}
}
|