Path Finder (2D/3D) 1.0.1
Create and use simple navigation graphs for 2D/3D path finding with choice of 4 search algorithms.
|
Public Member Functions | |
GraphSearch_Dijkstra (Graph graph) | |
LinkedList< GraphNode > | search (int startID, int targetID) |
LinkedList< GraphNode > | search (int startID, int targetID, boolean remember) |
GraphEdge[] | getExaminedEdges () |
GraphNode[] | getRoute () |
LinkedList< GraphNode > | search (int startID, int targetID) |
LinkedList< GraphNode > | search (int startID, int targetID, boolean remember) |
GraphEdge[] | getExaminedEdges () |
public< T > T[] | getExaminedEdges (T[] array) |
GraphNode[] | getRoute () |
public< T > T[] | getRoute (T[] array) |
Protected Member Functions | |
double | getCost (GraphNode node) |
Protected Attributes | |
Graph | graph |
HashSet< GraphNode > | settledNodes |
PriorityQueue< GraphNodeCost > | unsettledNodes |
HashMap< GraphNode, GraphNode > | parent |
HashMap< GraphNode, Double > | graphCostToNode |
HashSet< GraphEdge > | examinedEdges |
LinkedList< GraphNode > | route |
Dijkstra
Objects of this class are used to search a graph and find a path between two nodes using this algorithm.
pathfinder.GraphSearch_Dijkstra.GraphSearch_Dijkstra | ( | Graph | graph | ) |
Create a search object that uses Dijkstra's algorithm for the given graph.
graph | the graph to use |
|
protected |
Used by the search method
node |
GraphEdge[] pathfinder.GraphSearch_Dijkstra.getExaminedEdges | ( | ) |
Get all the edges examined during the search.
Implements pathfinder.IGraphSearch.
GraphNode[] pathfinder.GraphSearch_Dijkstra.getRoute | ( | ) |
Get the path found as an array of GraphNode(s) in start->end order
Implements pathfinder.IGraphSearch.
LinkedList< GraphNode > pathfinder.GraphSearch_Dijkstra.search | ( | int | startID, |
int | targetID | ||
) |
Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.
startID | id of the start node |
targetID | id of the target node |
Implements pathfinder.IGraphSearch.
LinkedList< GraphNode > pathfinder.GraphSearch_Dijkstra.search | ( | int | startID, |
int | targetID, | ||
boolean | remember | ||
) |
Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.
startID | id of the start node |
targetID | id of the target node |
remember | whether to remember the examined edges. |
Implements pathfinder.IGraphSearch.
|
protected |
Used to remember examined edges
|
protected |
Stores the smallest path cost found so far for a given node
Indicates the predecessor node for a given node. This is used to store the shortest path. <node of interest, node where the edge originated>
|
protected |
List for routes nodes in order of travel
|
protected |
The settled nodes - the nodes whose shortest distances from the source have been found.
|
protected |
The unsettled nodes