Implement Panda A.I. and its Trail

2 files changed, 196 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 @@
 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 Animal {
+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);
-        // TODO
+        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());
     }
 
     /**
@@ -26,16 +131,20 @@ public class Panda extends Animal {
      * 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) {
-        // TODO
-        return Direction.NONE;
+        Direction[] smartChoices = this.selectBestDirections(choices);
+        Direction choice = super.move(smartChoices);
+
+        if (this.shouldMarkCurrentPosition(choices, choice))
+            this.markCurrentPosition(choices);
+
+        return choice;
     }
 
     @Override
     public Animal copy() {
-        // TODO
-        return null;
+        return new Panda(this.getPosition());
     }
+
 }
diff --git a/src/ch/epfl/maze/util/Trail.java b/src/ch/epfl/maze/util/Trail.java
new file mode 100644
index 0000000..351db8f
--- /dev/null
+++ b/src/ch/epfl/maze/util/Trail.java
@@ -0,0 +1,79 @@
+package ch.epfl.maze.util;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * A trail keeping track on positional markings.
+ *
+ * @author Pacien TRAN-GIRARD
+ */
+public class Trail {
+
+    public enum Marking {
+        NO_MARKING,
+        AVOID_MARKING,
+        NO_GO_MARKING;
+
+        public static Marking DEFAULT = NO_MARKING;
+        public static Marking[] ALL = new Marking[]{NO_MARKING, AVOID_MARKING, NO_GO_MARKING};
+
+        /**
+         * Returns the next Marking.
+         *
+         * @return The next Marking
+         */
+        public Marking getNext() {
+            switch (this) {
+                case NO_MARKING:
+                    return AVOID_MARKING;
+                case AVOID_MARKING:
+                    return NO_GO_MARKING;
+                case NO_GO_MARKING:
+                    return NO_GO_MARKING;
+                default:
+                    return AVOID_MARKING;
+            }
+        }
+    }
+
+    private final Map<Vector2D, Marking> trail;
+
+    /**
+     * Constructs a new blank Trail.
+     */
+    public Trail() {
+        this.trail = new HashMap<>();
+    }
+
+    /**
+     * Get the marking at the given position.
+     *
+     * @param position The positional Vector