Package mazealgo.model.algorithms.search

Class SearchableMaze

java.lang.Object

mazealgo.model.algorithms.search.SearchableMaze

All Implemented Interfaces:

ISearchable

public class SearchableMaze
extends Object
implements ISearchable

Object Adapter that exposes a Maze as an ISearchable. Straight moves (up/down/left/right) cost less than diagonal moves; a diagonal move is only legal if at least one of the two orthogonal cells next to the corner is also open, so the path cannot squeeze through a pinhole between two walls.

Constructor Summary

Constructors

Constructor	Description
SearchableMaze(Maze maze)

Method Summary

Modifier and Type	Method	Description
List<AState>	getAllPossibleStates(AState state)
AState	getGoalState()
AState	getStartState()
double	heuristic(AState from, AState to)	Octile distance scaled to the straight/diagonal cost weights.

Methods inherited from class java.lang.Object

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

Constructor Details

SearchableMaze

public SearchableMaze(Maze maze)

Method Details

getStartState

public AState getStartState()

Specified by:

getStartState in interface ISearchable

getGoalState

public AState getGoalState()

Specified by:

getGoalState in interface ISearchable

getAllPossibleStates

public List<AState> getAllPossibleStates(AState state)

Specified by:

getAllPossibleStates in interface ISearchable

heuristic

public double heuristic(AState from,
 AState to)

Octile distance scaled to the straight/diagonal cost weights. Equivalent to 15*min(|dr|,|dc|) + 10*(max-min), which is the exact optimal cost on an unobstructed grid - so it's admissible.

Specified by:

heuristic in interface ISearchable