Package com.treasure.hunt.strategy.searcher.impl.minimumRectangleStrategy

Class MinimumRectangleSearcher

  • All Implemented Interfaces:
    Searcher<HalfPlaneHint>
    public class MinimumRectangleSearcher
extends StrategyFromPaper
implements Searcher<HalfPlaneHint>
    The strategy MinimumRectangleStrategy works similar to the strategy from the paper "Deterministic Treasure Hunt in the Plane with Angular Hints" from Bouchard et al.. We will call the strategy from the paper S in the following text. S gets improved by this strategy. Like S, this strategy has phases i=1,2,... in which it searches the treasure in rectangles of the side length 2^i. These rectangles are also centered in the start position of the searcher. But in contrast to S, in this strategy the phase rectangles aren't oriented in order to be axis parallel, but the rectangle is rotated in order to have one side that is parallel to the first gotten hint. By that, already half of the phase rectangle can be ignored. Every step the intersection I of all halfplanes of all hints and the current phase rectangle is created. The difference D of I and all already seen areas is created. The strategy applies S on each step but decreases the current rectangle of the strategy (if the previous hint was not bad) to the minimum rectangle where D is inside and which has sides parallel to the phase rectangle.

    Also when applying RectangleScan, this strategy does reduce the rectangle to be scanned, by ignoring some areas it has already seen and areas which can be ignored due to hints and uses a more efficient RectangleScan Routine.

    An annotation to the implementation: The implementation works on two different coordinate systems: 1. the "external" coordinate system: There all coordinates are represented as in the world around this strategy, i.e. the when move() returns, this gets interpreted by the game engine so all coordinates used in the return value are by definition in external coordinates. Also the strategy gets hints which are represented in external coordinates 2. the "internal" coordinate system: Since the strategy from the paper can only work on axis-parallel phase rectangles, the real phase rectangle gets rotated around the center of it in order to be easily processed by the strategy from the paper. For simplification the rectangle also gets shifted so that the center matches (0,0). By rotating and shifting the external coordinates in that manner, the internal coordinate system is created. The two coordinate systems can be translated in one another by using the TransformForAxisParallelism instance transformer.

    • Constructor Detail

      • MinimumRectangleSearcher

        public MinimumRectangleSearcher()

    • Method Detail

      • returnHandlingMinimumRectangleStrategy

        protected SearchPath returnHandlingMinimumRectangleStrategy​(SearchPath move)
        This method has to be called directly before move(HalfPlaneHint) returns In this method, several things are accomplished: - the internal fields are updated (visitedPolygon, lastLocation) - the move is transformed in the external coordinates - the state of the current rectangle is added to the move - the status messages which have to be removed, get removed - status messages of quality of hints get added
        Parameters:
        move - the move which is done this draw in internal coordinates
        Returns:
        the transformed move with added state and removed status messages

      • specificRectangleScan

        protected SearchPath specificRectangleScan​(org.locationtech.jts.geom.Coordinate rectangleCorner1,
                                           org.locationtech.jts.geom.Coordinate rectangleCorner2,
                                           org.locationtech.jts.geom.Coordinate rectangleCorner3,
                                           org.locationtech.jts.geom.Coordinate rectangleCorner4,
                                           SearchPath move)
        Description copied from class: StrategyFromPaper
        A specific rectangle scanner for this strategy, in case of StrategyFromPaper, the standard rectangleScanSpecificForStrategy from RoutinesFromPaper is used (this method is required for the MinimumRectangleStrategy which inherits from this class.)
        Overrides:
        specificRectangleScan in class StrategyFromPaper

      • getObtainedHints

        public java.util.List<HalfPlaneHint> getObtainedHints()

      • getCurrentMultiPolygon

        public org.locationtech.jts.geom.Geometry getCurrentMultiPolygon()
        This points represent the polygon where the treasure must lie in if it is in the current search rectangle, according to all obtained hints. If this List is empty, the treasure is not in the current search rectangle.

      • getHintPolygon

        public org.locationtech.jts.geom.Polygon getHintPolygon()

      • getVisitedPolygon

        public org.locationtech.jts.geom.Polygon getVisitedPolygon()
        The polygon the player already has seen because he was there.