◆ GraphSearch_Astar() [1/2]
| game2dai.graph.GraphSearch_Astar.GraphSearch_Astar |
( |
Graph |
graph | ) |
|
Create a search object that uses the A* algorithm for the given graph.
By default it uses the crow-flies heuristic.
- Parameters
-
◆ GraphSearch_Astar() [2/2]
Create a search object that uses the A* algorithm for the given graph using the given heuristic.
- Parameters
-
| graph | the graph to use |
| ash | the heuristic to use |
◆ clear()
| void game2dai.graph.GraphSearch_Astar.clear |
( |
| ) |
|
|
private |
Clears all data related to a search so this object can be reused for another search
◆ getExaminedEdges() [1/2]
| GraphEdge[] game2dai.graph.GraphSearch_Astar.getExaminedEdges |
( |
| ) |
|
Get all the edges examined during the search.
- Returns
- edges examined or array size 0 if none found
Implements game2dai.graph.IGraphSearch.
◆ getExaminedEdges() [2/2]
| public< T > T[] game2dai.graph.GraphSearch_Astar.getExaminedEdges |
( |
T[] |
array | ) |
|
|
package |
Get all the edges examined during the search.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphEdge or any class that extends GraphEdge.
- Parameters
-
| array | the array to populate |
- Returns
- edges examined or array size 0 if none found
Implements game2dai.graph.IGraphSearch.
◆ getFullCost()
| double game2dai.graph.GraphSearch_Astar.getFullCost |
( |
GraphNode |
node | ) |
|
|
protected |
Used during search.
- Parameters
-
| node | node used during search |
- Returns
- full cost of reaching this this edge
◆ getGraphCost()
| double game2dai.graph.GraphSearch_Astar.getGraphCost |
( |
GraphNode |
node | ) |
|
|
protected |
Used during search.
- Parameters
-
| node | node used during search |
- Returns
- cost of travelling to this node
◆ getRoute() [1/2]
| GraphNode[] game2dai.graph.GraphSearch_Astar.getRoute |
( |
| ) |
|
Get the path found as an array of GraphNode(s) in start->end order
- Returns
- path found or array size 0 if none found
Implements game2dai.graph.IGraphSearch.
◆ getRoute() [2/2]
| public< T > T[] game2dai.graph.GraphSearch_Astar.getRoute |
( |
T[] |
array | ) |
|
|
package |
Get the path found as an array of T(s) in start->end order.
The type of each element in the array will be of type Object if the parameter is null otherwise it is T (where T is GraphNode or any class that extends GraphNode.
- Parameters
-
| array | the array to populate |
- Returns
- path found or array size 0 if none found
Implements game2dai.graph.IGraphSearch.
◆ makeDataStores()
| void game2dai.graph.GraphSearch_Astar.makeDataStores |
( |
int |
nbrNodes | ) |
|
|
private |
Create the data stores needed by A*
- Parameters
-
| nbrNodes | number of nodes in the graph |
◆ search() [1/2]
| LinkedList< GraphNode > game2dai.graph.GraphSearch_Astar.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.
- Parameters
-
| startID | id of the start node |
| targetID | id of the target node |
- Returns
- the route as a list of nodes
Implements game2dai.graph.IGraphSearch.
◆ search() [2/2]
| LinkedList< GraphNode > game2dai.graph.GraphSearch_Astar.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.
- Parameters
-
| startID | id of the start node |
| targetID | id of the target node |
| remember | whether to remember the examined edges. |
- Returns
- the route as a list of nodes
Implements game2dai.graph.IGraphSearch.
◆ ash
The heuristic used to estimate cost to target.
◆ examinedEdges
| HashSet<GraphEdge> game2dai.graph.GraphSearch_Astar.examinedEdges |
|
protected |
Used to remember examined edges
◆ fullCostAtNode
| HashMap<GraphNode, Double> game2dai.graph.GraphSearch_Astar.fullCostAtNode |
|
protected |
Stores the smallest full cost (path cost + heuristic cost) found so far for a given node.
◆ graphCostToNode
| HashMap<GraphNode, Double> game2dai.graph.GraphSearch_Astar.graphCostToNode |
|
protected |
Stores the smallest path cost found so far for a given node
◆ parent
Indicates the predecessor node for a given node. This is used to store the shortest path. <node of interest, node where the edge originated>
◆ route
| LinkedList<GraphNode> game2dai.graph.GraphSearch_Astar.route |
|
protected |
List for routes nodes in order of travel
◆ settledNodes
| HashSet<GraphNode> game2dai.graph.GraphSearch_Astar.settledNodes |
|
protected |
The settled nodes - the nodes whose shortest distances from the source have been found.
◆ unsettledNodes
| PriorityQueue<GraphNodeCost> game2dai.graph.GraphSearch_Astar.unsettledNodes |
|
protected |
The documentation for this class was generated from the following file:
- /Users/peter/git/ai4games-repos/AI_4_2D_Games/src/game2dai/graph/GraphSearch_Astar.java
