public class CostlyGraph extends DirectedGraph<Coord> implements java.io.Serializable
DungeonUtility.generateAStarCostMap(char[][], Map, double)
.
Constructor and Description |
---|
CostlyGraph()
No-op no-arg constructor, present for
Serializable ; if you use this you must call
init(double[][]) or init(double[][], boolean) before using the CostlyGraph. |
CostlyGraph(char[][] map)
Builds a DefaultGraph from a 2D char array that treats
'#' , '+' , and all box drawing characters
as impassable, but considers all other cells passable for a cost of 1.0. |
CostlyGraph(char[][] map,
boolean eightWay)
Builds a DefaultGraph from a 2D char array that treats
'#' , '+' , and all box drawing characters
as impassable, but considers all other cells passable for a cost of 1.0. |
CostlyGraph(double[][] map)
Builds a DefaultGraph from a 2D double array that uses negative numbers to represent any kind of inaccessible
cell, with all other numbers treated as possible to enter for a cost equal to that double.
|
CostlyGraph(double[][] map,
boolean eightWay)
Builds a DefaultGraph from a 2D double array that uses negative numbers to represent any kind of inaccessible
cell, with all other numbers treated as possible to enter for a cost equal to that double.
|
Modifier and Type | Method and Description |
---|---|
Graph<Coord> |
breadthFirstSearch(Coord coord)
Perform a breadth first search starting from the specified vertex.
|
Graph<Coord> |
breadthFirstSearch(Coord coord,
int maxVertices,
int maxDepth)
Perform a breadth first search starting from the specified vertex.
|
Graph<Coord> |
depthFirstSearch(Coord coord)
Perform a depth first search starting from the specified vertex.
|
Graph<Coord> |
depthFirstSearch(Coord coord,
int maxVertices,
int maxDepth)
Perform a depth first search starting from the specified vertex.
|
boolean |
detectCycle()
Checks whether there are any cycles in the graph using depth first searches.
|
double |
findMinimumDistance(Coord start,
Coord target)
Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
java.util.ArrayList<Coord> |
findShortestPath(Coord start,
Coord target)
Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
|
boolean |
findShortestPath(Coord start,
Coord target,
java.util.ArrayList<Coord> path,
Heuristic<Coord> heuristic)
Find the shortest path between the start and target vertices, using the A* search algorithm with the provided
heuristic, and implemented with a priority queue.
|
java.util.ArrayList<Coord> |
findShortestPath(Coord start,
Coord target,
Heuristic<Coord> heuristic)
Find the shortest path between the start and target vertices, using the A* search algorithm with the provided heuristic, and implemented with a priority queue.
|
void |
init(double[][] map)
Re-initializes this DefaultGraph from a 2D double array that uses negative numbers to represent any kind of
inaccessible cell, with all other numbers treated as possible to enter for a cost equal to that double.
|
void |
init(double[][] map,
boolean eightWay)
Re-initializes this DefaultGraph from a 2D double array that uses negative numbers to represent any kind of
inaccessible cell, with all other numbers treated as possible to enter for a cost equal to that double.
|
char[] |
show()
Creates a 1D char array (which can be passed to
String.valueOf(char[]) ) filled with a grid made of the
vertices in this Graph and their estimated costs, if this has done an estimate. |
boolean |
topologicalSort()
Sort the vertices of this graph in topological order.
|
boolean |
topologicalSort(java.util.ArrayList<Coord> sortedVertices)
Perform a topological sort on the graph, and puts the sorted vertices in the supplied list.
|
algorithms, createNew, obtainEdge
addConnection, addConnection, addEdge, addEdge, addVertex, addVertices, connectionExists, contains, edgeExists, getEdge, getEdge, getEdgeCount, getEdges, getEdges, getNode, getNodes, getVertices, isDirected, removeAllEdges, removeAllVertices, removeConnection, removeEdge, removeEdge, removeNode, removeVertex, removeVertices, size, sortEdges, sortVertices
public CostlyGraph()
Serializable
; if you use this you must call
init(double[][])
or init(double[][], boolean)
before using the CostlyGraph.public CostlyGraph(double[][] map)
map
- a 2D double array where negative numbers are impassable and non-negative ones represent costs to enterDungeonUtility has methods to generate this type of map
public CostlyGraph(double[][] map, boolean eightWay)
eightWay
is
true, this builds connections along diagonals as well as along cardinals, but if eightWay
is false, it
only builds connections along cardinal directions.map
- a 2D double array where negative numbers are impassable and non-negative ones represent costs to entereightWay
- if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connectionsDungeonUtility has methods to generate this type of map
public CostlyGraph(char[][] map)
'#'
, '+'
, and all box drawing characters
as impassable, but considers all other cells passable for a cost of 1.0. This only builds connections along
cardinal directions.
init(double[][], boolean)
with the result of
DungeonUtility.generateAStarCostMap(char[][])
for the 2D double array. You can get more control by
calling DungeonUtility.generateAStarCostMap(char[][], Map, double)
and passing that to init() or a
constructor that takes a 2D double array.map
- a 2D char array where '#'
, '+'
, and all box drawing characters are considered impassablepublic CostlyGraph(char[][] map, boolean eightWay)
'#'
, '+'
, and all box drawing characters
as impassable, but considers all other cells passable for a cost of 1.0. If eightWay
is true, this builds
connections along diagonals as well as along cardinals, but if eightWay
is false, it only builds
connections along cardinal directions.
init(double[][], boolean)
with the result of
DungeonUtility.generateAStarCostMap(char[][])
for the 2D double array. You can get more control by
calling DungeonUtility.generateAStarCostMap(char[][], Map, double)
and passing that to init() or a
constructor that takes a 2D double array.map
- a 2D char array where '#'
, '+'
, and all box drawing characters are considered impassableeightWay
- if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connectionspublic void init(double[][] map)
map
- a 2D double array where negative numbers are impassable and non-negative ones represent costs to enterDungeonUtility has methods to generate this type of map
public void init(double[][] map, boolean eightWay)
eightWay
is true, this builds connections along diagonals as well as along cardinals, but if
eightWay
is false, it only builds connections along cardinal directions.map
- a 2D double array where negative numbers are impassable and non-negative ones represent costs to entereightWay
- if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connectionsDungeonUtility has methods to generate this type of map
public boolean topologicalSort()
Graph.getVertices()
. Note that the graph cannot contain any cycles for a topological order to exist. If a
cycle exists, this method will do nothing.public boolean topologicalSort(java.util.ArrayList<Coord> sortedVertices)
sortedVertices
- an ArrayList of V vertices that will be cleared and modified in-placepublic java.util.ArrayList<Coord> findShortestPath(Coord start, Coord target)
start
- the starting vertextarget
- the target vertexpublic java.util.ArrayList<Coord> findShortestPath(Coord start, Coord target, Heuristic<Coord> heuristic)
start
- the starting vertextarget
- the target vertexheuristic
- typically predefined in Heuristic
, this determines how the optimal path will be estimatedpublic boolean findShortestPath(Coord start, Coord target, java.util.ArrayList<Coord> path, Heuristic<Coord> heuristic)
start
- the starting vertextarget
- the target vertexpath
- the list of vertices to which the path vertices should be addedpublic double findMinimumDistance(Coord start, Coord target)
start
- the starting vertextarget
- the target vertexpublic Graph<Coord> breadthFirstSearch(Coord coord, int maxVertices, int maxDepth)
coord
- the vertex at which to start the searchmaxVertices
- the maximum number of vertices to process before terminating the searchmaxDepth
- the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be
considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the
returned graphGraph.getVertices()
and Graph.getEdges()
.public Graph<Coord> breadthFirstSearch(Coord coord)
coord
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public Graph<Coord> depthFirstSearch(Coord coord, int maxVertices, int maxDepth)
coord
- the vertex at which to start the searchmaxVertices
- the maximum number of vertices to process before terminating the searchmaxDepth
- the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be
considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the
returned graphGraph.getVertices()
and Graph.getEdges()
.public Graph<Coord> depthFirstSearch(Coord coord)
coord
- the vertex at which to start the searchGraph.getVertices()
and Graph.getEdges()
.public boolean detectCycle()
public char[] show()
String.valueOf(char[])
) filled with a grid made of the
vertices in this Graph and their estimated costs, if this has done an estimate. Each estimate is rounded to the
nearest int and only printed if it is 4 digits or less; otherwise this puts '####' in the grid cell. This is a
building-block for toString() implementations that may have debugging uses as well.Copyright © Eben Howard 2012–2022. All rights reserved.