From 15c612d56c98849daafeebea79d3f8f9b3a887b2 Mon Sep 17 00:00:00 2001
From: Pacien TRAN-GIRARD
Date: Sun, 22 Nov 2015 16:03:51 +0100
Subject: Implement Panda A.I. and its Trail
---
src/ch/epfl/maze/physical/zoo/Panda.java | 125 +++++++++++++++++++++++++++++--
src/ch/epfl/maze/util/Trail.java | 79 +++++++++++++++++++
2 files changed, 196 insertions(+), 8 deletions(-)
create mode 100644 src/ch/epfl/maze/util/Trail.java
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 Trémeaux's Algorithm,
+ * 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 Trémeaux's Algorithm.
+ *
+ * @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 trail;
+
+ /**
+ * Constructs a new blank Trail.
+ */
+ public Trail() {
+ this.trail = new HashMap<>();
+ }
+
+ /**
+ * Get the marking at the given position.
+ *
+ * @param position The positional Vector
+ * @return The Marking
+ */
+ public Marking getMarking(Vector2D position) {
+ Marking marking = this.trail.get(position);
+ return marking != null ? marking : Marking.DEFAULT;
+ }
+
+ /**
+ * Marks the given position with the given Marking.
+ *
+ * @param position The positional vector
+ * @param marking The Marking
+ */
+ public void markPosition(Vector2D position, Marking marking) {
+ this.trail.put(position, marking);
+ }
+
+ /**
+ * Marks the given position with the following Marking.
+ *
+ * @param position The positional vector
+ */
+ public void markPosition(Vector2D position) {
+ this.markPosition(position, this.getMarking(position).getNext());
+ }
+
+}
--
cgit v1.2.3