blob: fecec84289ddaf999266f93ec6c5769a3698b48b (
plain)
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
|
package ch.epfl.maze.physical.zoo;
import ch.epfl.maze.physical.Animal;
import ch.epfl.maze.physical.ProbabilisticAnimal;
import ch.epfl.maze.util.Direction;
import ch.epfl.maze.util.Trail;
import ch.epfl.maze.util.Vector2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
/**
* Panda A.I. that implements Trémeaux's Algorithm.
*
* @author Pacien TRAN-GIRARD
*/
public class Panda extends ProbabilisticAnimal {
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();
}
/**
* Checks if the current position is an intersection given the possible choices.
*
* @param choices An array of possible Directions
* @return T(the current position is an intersection)
*/
private boolean isIntersection(Direction[] choices) {
return choices.length > 2;
}
/**
* 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);
}
/**
* Checks if all Direction choices are leading to the given Marking.
*
* @param choices An array of possible Directions
* @param marking The Marking
* @return T(all choices are leading to positions with the given Marking)
*/
private boolean allChoicesLeadingTo(Direction[] choices, Trail.Marking marking) {
return (new ArrayList<>(Arrays.asList(choices)))
.stream()
.allMatch(dir -> this.getMarkingAtDirection(dir) == marking);
}
/**
* Selects the Direction choices leading to the given Marking.
*
* @param choices An array of possible Directions
* @param marking The Marking
* @return An array of choices leading to the given Marking
*/
private Direction[] selectDirectionsWithMarking(Direction[] choices, Trail.Marking marking) {
return (new ArrayList<>(Arrays.asList(choices)))
.stream()
.filter(dir -> this.getMarkingAtDirection(dir) == marking)
.collect(Collectors.toList())
.toArray(new Direction[0]);
}
/**
* Selects the best choices according to the neighbours Markings.
*
* @param choices An array of possible Directions
* @return An array of smart choices
*/
private Direction[] selectBestDirections(Direction[] choices) {
// special case
if (this.isIntersection(choices) && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING))
return new Direction[]{this.currentDirection.reverse()};
// general case
for (Trail.Marking mark : Trail.Marking.ALL) {
Direction[] smartChoices = this.selectDirectionsWithMarking(choices, mark);
if (smartChoices.length > 0) return smartChoices;
}
// panda is trapped :(
return new Direction[]{};
}
/**
* 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 An array of possible Directions
* @param choice The selected Direction
* @return T(the current position should be marked)
*/
private boolean shouldMarkCurrentPosition(Direction[] choices, Direction choice) {
return !(this.isIntersection(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 An array of possible Direction to take
*/
private void markCurrentPosition(Direction[] choices) {
if (choices.length == 1 && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING)) // dead end
this.trail.markPosition(this.getPosition(), Trail.Marking.NO_GO_MARKING);
else
this.trail.markPosition(this.getPosition());
}
/**
* 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(Direction[] choices) {
Direction[] smartChoices = this.selectBestDirections(choices);
Direction choice = super.move(smartChoices);
if (this.shouldMarkCurrentPosition(choices, choice))
this.markCurrentPosition(choices);
return choice;
}
@Override
public Animal copy() {
return new Panda(this.getPosition());
}
}
|