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)

Logo

With the help of www.sourceforge.net and www.info.ucl.ac.be