dk.deepthought.sidious.planner.graph
Class AStarVertex

java.lang.Object
  dk.deepthought.sidious.planner.graph.AStarVertex

All Implemented Interfaces:

Vertex, java.lang.Comparable<AStarVertex>

@ThreadSafe
public final class AStarVertex
extends java.lang.Object
implements Vertex, java.lang.Comparable<AStarVertex>

This class implements a vertex with respect to the A*-algorithm.

Author:

Deepthought

Field Summary

private double	costCandidate The cost-candidate of getting to this vertex from the source vertex.
private Edge	edgeToPredecessor The edge to the predecessor of this.
private boolean	goal Flag to indicate this being a goal vertex.
private double	heuristic The calculated heuristic for this.
private static org.apache.commons.logging.Log	logger Logger of this class.
private boolean	source Flag to indicate this being a source vertex.
private State	state The state this represents.

Constructor Summary

	AStarVertex(State state, double heuristic) Creates a AStarVertex with the specified State and heuristic value.
private	AStarVertex(State state, double heuristic, Edge edgeToPredecessor, boolean source, boolean goal, double costCandidate) Private utility constructor.

Method Summary

int	compareTo(AStarVertex v) This method implements the compareTo method of the Comparable interface.
boolean	equals(java.lang.Object obj)
double	g() At any given time, this method returns the cost of the shortest path to this vertex, with respect to the set of vertices the algorithm has evaluated at that time.
Vertex	getPredecessorVertex() Gets the predecessor Vertex from the edge.
State	getState() Gets the State represented by this Vertex.
Step	getStepToThis() Gets the Step leading to this Vertex.
double	h() This method returns an estimated cost of getting to the goal from this vertex.
int	hashCode()
boolean	isGoal() Returns true if this Vertex is the goal vertex.
boolean	isSource() Returns true if this Vertex is the source vertex.
boolean	partiallyEquals(Vertex otherVertex) Checks whether this vertex is contains all the state descriptors of the input vertex.
Vertex	toGoalVertex() Creates a goal vertex.
Vertex	toSourceVertex(Step initialStep) Creates a source vertex from the specified initial setpoints.
java.lang.String	toString()
void	update(Edge edgeToPredecessor, double cost) This is the implementation of the update method.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

logger

private static final org.apache.commons.logging.Log logger

Logger of this class.

state

private final State state

The state this represents.

heuristic

private final double heuristic

The calculated heuristic for this.

edgeToPredecessor

private Edge edgeToPredecessor

The edge to the predecessor of this.

source

private final boolean source

Flag to indicate this being a source vertex.

goal

private final boolean goal

Flag to indicate this being a goal vertex.

costCandidate

private double costCandidate

The cost-candidate of getting to this vertex from the source vertex. Is initialized to an "arbitrary" maximum value.

Constructor Detail

AStarVertex

public AStarVertex(State state,
                   double heuristic)

Creates a AStarVertex with the specified State and heuristic value.

According to the A*-algorithm an estimated cost from any vertex to the goal vertex cannot be negative.

Parameters:

state - the State this vertex represent

heuristic - the heuristic

AStarVertex

private AStarVertex(State state,
                    double heuristic,
                    Edge edgeToPredecessor,
                    boolean source,
                    boolean goal,
                    double costCandidate)

Private utility constructor.

Parameters:

state - the state

heuristic - the heuristic

edgeToPredecessor - the edge

source - is source vertex flag

goal - is goal vertex flag

costCandidate - the cost candidate

Method Detail

h

public double h()

This method returns an estimated cost of getting to the goal from this vertex. This estimate is calculated as the Euclidian distance to the goal.

Returns:

an estimated cost of getting to the goal

g

public double g()

Description copied from interface: Vertex

At any given time, this method returns the cost of the shortest path to this vertex, with respect to the set of vertices the algorithm has evaluated at that time.

Specified by:

g in interface Vertex

Returns:

the shortest path cost candidate

update

public void update(Edge edgeToPredecessor,
                   double cost)

This is the implementation of the update method.

In accordance with the A*-algorithm the following will throw AssertionError:

Negative costs, which imply negative edge weights.

An edgeToPredecessor which is null, because it will break the shortest path tree.

Specified by:

update in interface Vertex

Parameters:

edgeToPredecessor - the edge to the previous vertex

cost - the cost of getting to this vertex

See Also:

Vertex.update(dk.deepthought.sidious.planner.graph.Edge, double)

toGoalVertex

public Vertex toGoalVertex()

Description copied from interface: Vertex

Creates a goal vertex.

Specified by:

toGoalVertex in interface Vertex

Returns:

the goal Vertex

toSourceVertex

public Vertex toSourceVertex(Step initialStep)

Description copied from interface: Vertex

Creates a source vertex from the specified initial setpoints.

Specified by:

toSourceVertex in interface Vertex

Parameters:

initialStep - the initial step

Returns:

the source Vertex

isGoal

public boolean isGoal()

Description copied from interface: Vertex

Returns true if this Vertex is the goal vertex. The goal vertex is defined as the end of a path.

Specified by:

isGoal in interface Vertex

Returns:

true if this is the goal vertex.

isSource

public boolean isSource()

Description copied from interface: Vertex

Returns true if this Vertex is the source vertex. The source vertex is defined as the start of a path.

Specified by:

isSource in interface Vertex

Returns:

true if this is the source vertex.

getPredecessorVertex

public Vertex getPredecessorVertex()

Description copied from interface: Vertex

Gets the predecessor Vertex from the edge.

Specified by:

getPredecessorVertex in interface Vertex

Returns:

the predecessor vertex

getStepToThis

public Step getStepToThis()

Description copied from interface: Vertex

Gets the Step leading to this Vertex.

Specified by:

getStepToThis in interface Vertex

Returns:

the Step

getState

public State getState()

Description copied from interface: Vertex

Gets the State represented by this Vertex.

Specified by:

getState in interface Vertex

Returns:

the state

partiallyEquals

public boolean partiallyEquals(Vertex otherVertex)

Description copied from interface: Vertex

Checks whether this vertex is contains all the state descriptors of the input vertex. The input vertex does not have to contain all the state descriptors of this vertex.

Specified by:

partiallyEquals in interface Vertex

Parameters:

otherVertex - the input vertex

Returns:

true if all state descriptors are contained in this vertex

compareTo

public int compareTo(AStarVertex v)

This method implements the compareTo method of the Comparable interface.

The method is needed to specify the ordering of the AStarVertex objects. This ordering is imperative for the functionality of the pathfinding algorithm.

Specified by:

compareTo in interface java.lang.Comparable<AStarVertex>

See Also:

Comparable.compareTo(java.lang.Object), dk.deepthought.sidious.planner.Pathfinder#search()

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object