cad.simcad.pathfinding.astar
Class AStarAlgo

java.lang.Object
  |
  +--java.lang.Thread
        |
        +--cad.simcad.pathfinding.astar.AStarAlgo

All Implemented Interfaces:

PathFinder, java.lang.Runnable

Direct Known Subclasses:

AStarBasic, AStarForProduction, AStarSequential

public abstract class AStarAlgo

extends java.lang.Thread

implements PathFinder

Abstract class to use as a framework to implement A* algorithms NOT APPLICABLE the Runnable interface is used because we are only overriding the run() method and no other Thread methods. This is important because classes should not be subclassed unless the programmer intends on modifying or enhancing the fundamental behavior of the class. Once the class has been instantiated, you have to give it to a thread object and start it.

Version:

1.0

Author:

Charles-Philip Bentley

Field Summary

protected java.lang.String	_algoType
protected int	_assoId
protected java.util.TreeSet	_closed
protected Path	_cp
protected PathPlace	_finish
protected java.lang.Thread	_loop
protected java.util.Hashtable	_mapTable Hasthtable mapping a PathPlace with a cost
protected PathFindable	_myMap
protected java.util.TreeSet	_open
protected PathUser	_pu
protected double	_rebuildingFudgeFactor
protected PathPlace	_start
protected int	_state
int	FOUND
int	NO_PATH
int	NOT_FOUND

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

AStarAlgo(PathFindable map)

AStarAlgo(PathFindable map, Path cp)
Creates new AStarAlgo

Method Summary

protected void	buildReferences(Path cp) This method should only be invoked if the algorithm needs to to trace the best path from the destination back to the origin
protected void	buildReferencesFudged(Path cp) This method should only be invoked if the algorithm needs to to trace the best path from the destination back to the origin
protected void	firePathComputation(PathPlaceSet pp)
protected void	firePathPlaceChange(PathPlace pp)
protected PathPlace	getFudgedLowestAdjacent(PathPlace mp) Returns the best PathPlace adjacent to the given PathPlace.
protected PathPlace	getLowestAdjacent(PathPlace mp) Returns the best PathPlace adjacent to the given PathPlace.
PathPlaceSet	getShortestPath() Returns the Path of the Algorithm
PathPlaceSet	getShortestPath(PathPlace origin, PathPlace dest, PathUser pu) Find the shortest path between two places.
boolean	isApplicable(Path cp)
boolean	isSequential() Returns true if the PathFinder does not run in its own thread
abstract void	run()

Methods inherited from class java.lang.Thread

activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, getContextClassLoader, getName, getPriority, getThreadGroup, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setName, setPriority, sleep, sleep, start, stop, stop, suspend, toString, yield

Methods inherited from class java.lang.Object

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

Field Detail

NO_PATH

public final int NO_PATH

See Also:

Constant Field Values

NOT_FOUND

public final int NOT_FOUND

See Also:

Constant Field Values

FOUND

public final int FOUND

See Also:

Constant Field Values

_myMap

protected PathFindable _myMap

_cp

protected Path _cp

_open

protected java.util.TreeSet _open

_closed

protected java.util.TreeSet _closed

_state

protected int _state

_mapTable

protected java.util.Hashtable _mapTable

Hasthtable mapping a PathPlace with a cost

_loop

protected java.lang.Thread _loop

_assoId

protected int _assoId

_finish

protected PathPlace _finish

_start

protected PathPlace _start

_algoType

protected java.lang.String _algoType

_pu

protected PathUser _pu

_rebuildingFudgeFactor

protected double _rebuildingFudgeFactor

Constructor Detail

AStarAlgo

public AStarAlgo(PathFindable map,
                 Path cp)

Creates new AStarAlgo

AStarAlgo

public AStarAlgo(PathFindable map)

Method Detail

isApplicable

public boolean isApplicable(Path cp)

run

public abstract void run()

Specified by:

run in interface java.lang.Runnable

Overrides:

run in class java.lang.Thread

getLowestAdjacent

protected PathPlace getLowestAdjacent(PathPlace mp)

Returns the best PathPlace adjacent to the given PathPlace.

Pre:

-

Post:

the PathPlace with the lowest cost computed in _mapTable Hashtable object Ties are not broken. first come, first served

getFudgedLowestAdjacent

protected PathPlace getFudgedLowestAdjacent(PathPlace mp)

Returns the best PathPlace adjacent to the given PathPlace.

Pre:

-

Post:

the PathPlace with the lowest cost computed in _mapTable Hashtable object Ties are broken using a cross product

buildReferences

protected void buildReferences(Path cp)

This method should only be invoked if the algorithm needs to to trace the best path from the destination back to the origin

Parameters:

cp - the Path to update

Pre:

_state == FOUND

Post:

The Path given in argument has been updated. It is consistent if there is a path between origin and destination.

buildReferencesFudged

protected void buildReferencesFudged(Path cp)

This method should only be invoked if the algorithm needs to to trace the best path from the destination back to the origin

Parameters:

cp - the Path to update

Pre:

_state == FOUND

Post:

The Path given in argument has been updated. It is consistent if there is a path between origin and destination.

getShortestPath

public PathPlaceSet getShortestPath()

Returns the Path of the Algorithm

Specified by:

getShortestPath in interface PathFinder

Returns:

a PathPlaceSet object

isSequential

public boolean isSequential()

Description copied from interface: PathFinder

Returns true if the PathFinder does not run in its own thread

Specified by:

isSequential in interface PathFinder

Returns:

a boolean true = sequential PathFinder false = threaded PathFinder

getShortestPath

public PathPlaceSet getShortestPath(PathPlace origin,
                                    PathPlace dest,
                                    PathUser pu)

Find the shortest path between two places. Runs in owner's thread

Specified by:

getShortestPath in interface PathFinder

Parameters:

origin - The origin of the Path

dest - The destination of the Path

Pre:

Two PathPlace objects. First is the origin, second is the destination

Returns:

the shortest PathPlaceSet between those the two PathPlaces given in argument

Post:

Ask the PathFinder to compute a new Path. This method runs in the owner's thread. No side effects on other parts of the PathFinder

firePathPlaceChange

protected void firePathPlaceChange(PathPlace pp)

firePathComputation

protected void firePathComputation(PathPlaceSet pp)