Package squidpony.squidai.graph

Class CostlyGraph

java.lang.Object
squidpony.squidai.graph.Graph<V>
squidpony.squidai.graph.DirectedGraph<Coord>
squidpony.squidai.graph.CostlyGraph
All Implemented Interfaces:
Serializable
public class CostlyGraph
extends DirectedGraph<Coord>
implements Serializable
A default setting for a DirectedGraph of Coord vertices where each passable cell has a cost to enter it from any passable neighbor. This should be compatible with the AStar cost maps produced by DungeonUtility.generateAStarCostMap(char[][], Map, double).
Created by Tommy Ettinger on 7/9/2020.
See Also:
Serialized Form

  • Field Details

  • Constructor Details

    • CostlyGraph

      public 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

      public 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. This only builds connections along cardinal directions.
      Parameters:
      map - a 2D double array where negative numbers are impassable and non-negative ones represent costs to enter
      See Also:
      DungeonUtility has methods to generate this type of map

    • CostlyGraph

      public 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. 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.
      Parameters:
      map - a 2D double array where negative numbers are impassable and non-negative ones represent costs to enter
      eightWay - if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connections
      See Also:
      DungeonUtility has methods to generate this type of map

    • CostlyGraph

      public 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. This only builds connections along cardinal directions.
      This simply delegates to 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.
      Parameters:
      map - a 2D char array where '#', '+', and all box drawing characters are considered impassable

    • CostlyGraph

      public 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. 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.
      This simply delegates to 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.
      Parameters:
      map - a 2D char array where '#', '+', and all box drawing characters are considered impassable
      eightWay - if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connections

  • Method Details

    • init

      public 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. This only builds connections along cardinal directions.
      Parameters:
      map - a 2D double array where negative numbers are impassable and non-negative ones represent costs to enter
      See Also:
      DungeonUtility has methods to generate this type of map

    • init

      public 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. 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.
      Parameters:
      map - a 2D double array where negative numbers are impassable and non-negative ones represent costs to enter
      eightWay - if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connections
      See Also:
      DungeonUtility has methods to generate this type of map

    • topologicalSort

      public boolean topologicalSort()
      Sort the vertices of this graph in topological order. That is, for every edge from vertex u to vertex v, u comes before v in the ordering. This is reflected in the iteration order of the collection returned by 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.
      Returns:
      true if the sort was successful, false if the graph contains a cycle

    • topologicalSort

      public boolean topologicalSort​(ArrayList<Coord> sortedVertices)
      Perform a topological sort on the graph, and puts the sorted vertices in the supplied list. That is, for every edge from vertex u to vertex v, u will come before v in the supplied list. Note that the graph cannot contain any cycles for a topological order to exist. If a cycle exists, the sorting procedure will terminate and the supplied list will only contain the vertices up until the point of termination.
      Parameters:
      sortedVertices - an ArrayList of V vertices that will be cleared and modified in-place
      Returns:
      true if the sort was successful, false if the graph contains a cycle

    • findShortestPath

      public 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.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices

    • findShortestPath

      public 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.
      Parameters:
      start - the starting vertex
      target - the target vertex
      heuristic - typically predefined in Heuristic, this determines how the optimal path will be estimated
      Returns:
      a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices

    • findShortestPath

      public boolean findShortestPath​(Coord start, Coord target, 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. Fills path with a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices.
      Parameters:
      start - the starting vertex
      target - the target vertex
      path - the list of vertices to which the path vertices should be added
      Returns:
      true if a path was found, or false if no path could be found

    • findMinimumDistance

      public 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.
      Parameters:
      start - the starting vertex
      target - the target vertex
      Returns:
      the sum of the weights in a shortest path from the starting vertex to the target vertex

    • breadthFirstSearch

      public Graph<Coord> breadthFirstSearch​(Coord coord, int maxVertices, int maxDepth)
      Perform a breadth first search starting from the specified vertex.
      Parameters:
      coord - the vertex at which to start the search
      maxVertices - the maximum number of vertices to process before terminating the search
      maxDepth - 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 graph
      Returns:
      a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • breadthFirstSearch

      public Graph<Coord> breadthFirstSearch​(Coord coord)
      Perform a breadth first search starting from the specified vertex.
      Parameters:
      coord - the vertex at which to start the search
      Returns:
      a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • depthFirstSearch

      public Graph<Coord> depthFirstSearch​(Coord coord, int maxVertices, int maxDepth)
      Perform a depth first search starting from the specified vertex.
      Parameters:
      coord - the vertex at which to start the search
      maxVertices - the maximum number of vertices to process before terminating the search
      maxDepth - 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 graph
      Returns:
      a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • depthFirstSearch

      public Graph<Coord> depthFirstSearch​(Coord coord)
      Perform a depth first search starting from the specified vertex.
      Parameters:
      coord - the vertex at which to start the search
      Returns:
      a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be reflected in the iteration order of the collections returned by Graph.getVertices() and Graph.getEdges().

    • detectCycle

      public boolean detectCycle()
      Checks whether there are any cycles in the graph using depth first searches.
      Returns:
      true if the graph contains a cycle, false otherwise

    • show

      public 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. 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.
      Returns:
      a 1D char array containing newline-separated rows of space-separated grid cells that contain estimated costs or '####' for unexplored