summaryrefslogtreecommitdiff
path: root/src/ch/epfl/maze/physical/zoo
diff options
context:
space:
mode:
authorPacien TRAN-GIRARD2015-11-22 16:03:51 +0100
committerPacien TRAN-GIRARD2015-11-22 16:03:51 +0100
commit15c612d56c98849daafeebea79d3f8f9b3a887b2 (patch)
treef5678ace0ce0ed7fee5556883a8b6708ccaf0374 /src/ch/epfl/maze/physical/zoo
parent76eba89ebb2da6d19ac37dba5741a717edd8dd8e (diff)
downloadmaze-solver-15c612d56c98849daafeebea79d3f8f9b3a887b2.tar.gz
Implement Panda A.I. and its Trail
Diffstat (limited to 'src/ch/epfl/maze/physical/zoo')
-rw-r--r--src/ch/epfl/maze/physical/zoo/Panda.java125
1 files changed, 117 insertions, 8 deletions
diff --git a/src/ch/epfl/maze/physical/zoo/Panda.java b/src/ch/epfl/maze/physical/zoo/Panda.java
index c168d97..fecec84 100644
--- a/src/ch/epfl/maze/physical/zoo/Panda.java
+++ b/src/ch/epfl/maze/physical/zoo/Panda.java
@@ -1,23 +1,128 @@
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.util.Direction; 5import ch.epfl.maze.util.Direction;
6import ch.epfl.maze.util.Trail;
5import ch.epfl.maze.util.Vector2D; 7import ch.epfl.maze.util.Vector2D;
6 8
9import java.util.ArrayList;
10import java.util.Arrays;
11import java.util.stream.Collectors;
12
7/** 13/**
8 * Panda A.I. that implements Trémeaux's Algorithm. 14 * Panda A.I. that implements Trémeaux's Algorithm.
15 *
16 * @author Pacien TRAN-GIRARD
9 */ 17 */
10public class Panda extends Animal { 18public class Panda extends ProbabilisticAnimal {
19
20 private final Trail trail;
11 21
12 /** 22 /**
13 * Constructs a panda with a starting position. 23 * Constructs a panda with a starting position.
14 * 24 *
15 * @param position Starting position of the panda in the labyrinth 25 * @param position Starting position of the panda in the labyrinth
16 */ 26 */
17
18 public Panda(Vector2D position) { 27 public Panda(Vector2D position) {
19 super(position); 28 super(position);
20 // TODO 29 this.trail = new Trail();
30 }
31
32 /**
33 * Checks if the current position is an intersection given the possible choices.
34 *
35 * @param choices An array of possible Directions
36 * @return T(the current position is an intersection)
37 */
38 private boolean isIntersection(Direction[] choices) {
39 return choices.length > 2;
40 }
41
42 /**
43 * Get the Marking at the adjacent position given the Direction.
44 *
45 * @param dir The Direction from the current position
46 * @return The Marking
47 */
48 private Trail.Marking getMarkingAtDirection(Direction dir) {
49 Vector2D pos = this.getPosition().addDirectionTo(dir);
50 return this.trail.getMarking(pos);
51 }
52
53 /**
54 * Checks if all Direction choices are leading to the given Marking.
55 *
56 * @param choices An array of possible Directions
57 * @param marking The Marking
58 * @return T(all choices are leading to positions with the given Marking)
59 */
60 private boolean allChoicesLeadingTo(Direction[] choices, Trail.Marking marking) {
61 return (new ArrayList<>(Arrays.asList(choices)))
62 .stream()
63 .allMatch(dir -> this.getMarkingAtDirection(dir) == marking);
64 }
65
66 /**
67 * Selects the Direction choices leading to the given Marking.
68 *
69 * @param choices An array of possible Directions
70 * @param marking The Marking
71 * @return An array of choices leading to the given Marking
72 */
73 private Direction[] selectDirectionsWithMarking(Direction[] choices, Trail.Marking marking) {
74 return (new ArrayList<>(Arrays.asList(choices)))
75 .stream()
76 .filter(dir -> this.getMarkingAtDirection(dir) == marking)
77 .collect(Collectors.toList())
78 .toArray(new Direction[0]);
79 }
80
81 /**
82 * Selects the best choices according to the neighbours Markings.
83 *
84 * @param choices An array of possible Directions
85 * @return An array of smart choices
86 */
87 private Direction[] selectBestDirections(Direction[] choices) {
88 // special case
89 if (this.isIntersection(choices) && this.allChoicesLeadingTo(choices, Trail.Marking.AVOID_MARKING))
90 return new Direction[]{this.currentDirection.reverse()};
91
92 // general case
93 for (Trail.Marking mark : Trail.Marking.ALL) {
94 Direction[] smartChoices = this.selectDirectionsWithMarking(choices, mark);
95 if (smartChoices.length > 0) return smartChoices;
96 }
97
98 // panda is trapped :(
99 return new Direction[]{};
100 }
101
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 An array of possible Directions
107 * @param choice The selected Direction
108 * @return T(the current position should be marked)
109 */
110 private boolean shouldMarkCurrentPosition(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 An array of possible Direction to take
120 */
121 private void markCurrentPosition(Direction[] choices) {
122 if (choices.length == 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());
21 } 126 }
22 127
23 /** 128 /**
@@ -26,16 +131,20 @@ public class Panda extends Animal {
26 * colors). It will prefer taking the least marked paths. Special cases 131 * colors). It will prefer taking the least marked paths. Special cases
27 * have to be handled, especially when the panda is at an intersection. 132 * have to be handled, especially when the panda is at an intersection.
28 */ 133 */
29
30 @Override 134 @Override
31 public Direction move(Direction[] choices) { 135 public Direction move(Direction[] choices) {
32 // TODO 136 Direction[] smartChoices = this.selectBestDirections(choices);
33 return Direction.NONE; 137 Direction choice = super.move(smartChoices);
138
139 if (this.shouldMarkCurrentPosition(choices, choice))
140 this.markCurrentPosition(choices);
141
142 return choice;
34 } 143 }
35 144
36 @Override 145 @Override
37 public Animal copy() { 146 public Animal copy() {
38 // TODO 147 return new Panda(this.getPosition());
39 return null;
40 } 148 }
149
41} 150}