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

Class StrategyFromPaper

java.lang.Object

com.treasure.hunt.strategy.searcher.impl.strategyFromPaper.StrategyFromPaper

All Implemented Interfaces:

Searcher<HalfPlaneHint>

Direct Known Subclasses:

MinimumRectangleSearcher

public class StrategyFromPaper
extends java.lang.Object
implements Searcher<HalfPlaneHint>

This strategy implements the strategy from the paper "Deterministic Treasure Hunt in the Plane with Angular Hints" from Bouchard et al..

Generally this strategy works in phases i=1, 2, ... in which it searchers the treasure in rectangles of the side length 2^i. The rectangles are centered in the start position of the searcher and are axis parallel. We will call the rectangle of the current phase the phase rectangle. The strategy uses a second rectangle, called the current rectangle, which equals the phase rectangle at the beginning of each phase. In some draws (most draws) the searcher can exclude a part of the current rectangle by using areas seen and the current hint gotten and lower its area. The previous rectangle is the current rectangle from the previous draw. When the current rectangle is small enough, the rectangle gets scanned which means the player walks a route in such a way that it sees all points of the current rectangle. When this happens the phase is incremented and the current rectangle is again set to the phase rectangle.

For more information please look in the paper.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	StrategyFromPaper.HintQuality

Field Summary

Fields

Modifier and Type	Field	Description
protected HalfPlaneHint	currentHint
protected LastHintBadSubroutine	lastHintBadSubroutine
protected int	phase	phase equals i in Algorithm2 (TreasureHunt1) in the paper.
protected boolean	phaseGotIncrementedThisMove
protected HalfPlaneHint	previousHint
protected StrategyFromPaper.HintQuality	previousHintQuality
protected org.locationtech.jts.geom.Point	searchAreaCornerA	searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.
protected org.locationtech.jts.geom.Point	searchAreaCornerB	searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.
protected org.locationtech.jts.geom.Point	searchAreaCornerC	searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.
protected org.locationtech.jts.geom.Point	searchAreaCornerD	searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.

Constructor Summary

Constructors

Constructor	Description
StrategyFromPaper()

Method Summary

Modifier and Type	Method	Description
protected SearchPath	addState(SearchPath move, org.locationtech.jts.geom.Coordinate[] currentRectanglePoints, org.locationtech.jts.geom.Coordinate[] phaseRectanglePoints)	This method is used to visualize the current phases rectangle and the current search rectangle.
protected org.locationtech.jts.geom.Coordinate[]	currentPhaseRectangle()	Returnes the rectangle of the current phase, by using the current phase index (equates to j in the paper or the phase-field in this implementation)
void	init(org.locationtech.jts.geom.Point startPosition)
SearchPath	move()	Use this to perform a initial move, without a hint given.
SearchPath	move(HalfPlaneHint hint)
protected org.locationtech.jts.geom.Coordinate[]	phaseRectangle(int phase)	Returnes the rectangle of the current phase, by using a specified phase index
protected boolean	rectangleNotLargeEnough()
protected SearchPath	returnHandling(SearchPath move)
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)	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.)
protected SearchPath	specificRectangleScan(org.locationtech.jts.geom.Point rectangleCorner1, org.locationtech.jts.geom.Point rectangleCorner2, org.locationtech.jts.geom.Point rectangleCorner3, org.locationtech.jts.geom.Point rectangleCorner4, SearchPath move)	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.)
protected org.locationtech.jts.geom.Point[]	splitRectangleHorizontally(org.locationtech.jts.geom.Point A, org.locationtech.jts.geom.Point B, org.locationtech.jts.geom.Point C, org.locationtech.jts.geom.Point D, HalfPlaneHint hint, org.locationtech.jts.geom.LineSegment hintLine)	If the checkIfHintGood is true and the hint is bad (i.e.
protected org.locationtech.jts.geom.Point[]	splitRectangleVertically(org.locationtech.jts.geom.Point A, org.locationtech.jts.geom.Point B, org.locationtech.jts.geom.Point C, org.locationtech.jts.geom.Point D, HalfPlaneHint hint, org.locationtech.jts.geom.LineSegment hintLine)	If the checkIfHintGood is true and the hint is bad (i.e.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

phase

protected int phase

phase equals i in Algorithm2 (TreasureHunt1) in the paper. In phase k, the algorithm checks, if the treasure is located in a rectangle with a side length of 2^k, centered at the initial position of the searcher.

searchAreaCornerA

protected org.locationtech.jts.geom.Point searchAreaCornerA

searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.

searchAreaCornerB

protected org.locationtech.jts.geom.Point searchAreaCornerB

searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.

searchAreaCornerC

protected org.locationtech.jts.geom.Point searchAreaCornerC

searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.

searchAreaCornerD

protected org.locationtech.jts.geom.Point searchAreaCornerD

searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.

previousHint

protected HalfPlaneHint previousHint

currentHint

protected HalfPlaneHint currentHint

previousHintQuality

protected StrategyFromPaper.HintQuality previousHintQuality

lastHintBadSubroutine

protected LastHintBadSubroutine lastHintBadSubroutine

phaseGotIncrementedThisMove

protected boolean phaseGotIncrementedThisMove

Constructor Detail

StrategyFromPaper

public StrategyFromPaper()

Method Detail

init

public void init(org.locationtech.jts.geom.Point startPosition)

Specified by:

init in interface Searcher<HalfPlaneHint>

Parameters:

startPosition - the Searcher starting position, he will initialized on.

move

public SearchPath move()

Use this to perform a initial move, without a hint given. This is for the case, the searcher starts. (as he does normally)

Specified by:

move in interface Searcher<HalfPlaneHint>

Returns:

SearchPath the SearchPath the searcher did

move

public SearchPath move(HalfPlaneHint hint)

Specified by:

move in interface Searcher<HalfPlaneHint>

Parameters:

hint - the hint, the Hider gave last.

Returns:

SearchPath the SearchPath, this searcher chose.

rectangleNotLargeEnough

protected boolean rectangleNotLargeEnough()

addState

protected SearchPath addState(SearchPath move,
                              org.locationtech.jts.geom.Coordinate[] currentRectanglePoints,
                              org.locationtech.jts.geom.Coordinate[] phaseRectanglePoints)

This method is used to visualize the current phases rectangle and the current search rectangle. Adds their values to move

Returns:

the input with the visualisations of the current phase and the search rectangle added

returnHandling

protected SearchPath returnHandling(SearchPath move)

splitRectangleHorizontally

protected org.locationtech.jts.geom.Point[] splitRectangleHorizontally(org.locationtech.jts.geom.Point A,
                                                                       org.locationtech.jts.geom.Point B,
                                                                       org.locationtech.jts.geom.Point C,
                                                                       org.locationtech.jts.geom.Point D,
                                                                       HalfPlaneHint hint,
                                                                       org.locationtech.jts.geom.LineSegment hintLine)

If the checkIfHintGood is true and the hint is bad (i.e. does not divide one side of the rectangle ABCD in two parts such that both are bigger or equal to 1), null is returned. If the hint-line goes through AD and BC, the biggest axis parallel-rectangle which lies in ABCD and where the treasure could be located due to the information gained by the hint, is returned. Otherwise the return value is null.

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)

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.)

specificRectangleScan

protected SearchPath specificRectangleScan(org.locationtech.jts.geom.Point rectangleCorner1,
                                           org.locationtech.jts.geom.Point rectangleCorner2,
                                           org.locationtech.jts.geom.Point rectangleCorner3,
                                           org.locationtech.jts.geom.Point rectangleCorner4,
                                           SearchPath move)

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.)

splitRectangleVertically

protected org.locationtech.jts.geom.Point[] splitRectangleVertically(org.locationtech.jts.geom.Point A,
                                                                     org.locationtech.jts.geom.Point B,
                                                                     org.locationtech.jts.geom.Point C,
                                                                     org.locationtech.jts.geom.Point D,
                                                                     HalfPlaneHint hint,
                                                                     org.locationtech.jts.geom.LineSegment hintLine)

If the checkIfHintGood is true and the hint is bad (i.e. does not divide one side of the rectangle ABCD in two parts such that both are bigger or equal to 1), null is returned. If the hint-line goes through AB and CD, the biggest axis-parallel rectangle which lies in ABCD and where the treasure could be located due to the information gained by the hint, is returned. Otherwise the return value is null.

currentPhaseRectangle

protected org.locationtech.jts.geom.Coordinate[] currentPhaseRectangle()

Returnes the rectangle of the current phase, by using the current phase index (equates to j in the paper or the phase-field in this implementation)

phaseRectangle

protected org.locationtech.jts.geom.Coordinate[] phaseRectangle(int phase)

Returnes the rectangle of the current phase, by using a specified phase index

Parameters:

phase - the phase to which the phase's rectangle should be returned

Returns:

the points of the phase's rectangle