Class CostlyGraph

java.lang.Object
com.github.yellowstonegames.path.Graph<com.github.yellowstonegames.grid.Coord>
com.github.yellowstonegames.path.DirectedGraph<com.github.yellowstonegames.grid.Coord>
com.github.yellowstonegames.path.CostlyGraph
All Implemented Interfaces:
com.github.yellowstonegames.core.ISerializersNeeded, Externalizable, Serializable
public class CostlyGraph extends DirectedGraph<com.github.yellowstonegames.grid.Coord> implements com.github.yellowstonegames.core.ISerializersNeeded
A default setting for a DirectedGraph of Coord vertices where each passable cell has a cost to enter it from any passable neighbor.
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    int
    height
     
    int
    width
     

    Fields inherited from class DirectedGraph

    algorithms

    Fields inherited from class Graph

    edgeSet, vertexMap

  • Constructor Summary

    Constructors
    Constructor
    Description
    CostlyGraph()
    No-op no-arg constructor, present for serialization; if you use this you must call init(float[][]) or init(float[][], 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(float[][] map)
    Builds a DefaultGraph from a 2D float 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 float.
    CostlyGraph(float[][] map, boolean eightWay)
    Builds a DefaultGraph from a 2D float 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 float.

  • Method Summary

    Modifier and Type
    Method
    Description
    Graph<com.github.yellowstonegames.grid.Coord>
    breadthFirstSearch(com.github.yellowstonegames.grid.Coord coord)
    Perform a breadth first search starting from the specified vertex.
    Graph<com.github.yellowstonegames.grid.Coord>
    breadthFirstSearch(com.github.yellowstonegames.grid.Coord coord, int maxVertices, int maxDepth)
    Perform a breadth first search starting from the specified vertex.
    boolean
    containsCycle()
    Checks whether there are any cycles in the graph using depth first searches.
    Graph<com.github.yellowstonegames.grid.Coord>
    depthFirstSearch(com.github.yellowstonegames.grid.Coord coord)
    Perform a depth first search starting from the specified vertex.
    Graph<com.github.yellowstonegames.grid.Coord>
    depthFirstSearch(com.github.yellowstonegames.grid.Coord coord, int maxVertices, int maxDepth)
    Perform a depth first search starting from the specified vertex.
    boolean
    equals(Object o)
     
    float
    findMinimumDistance(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target)
    Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findShortestPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target)
    Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue.
    boolean
    findShortestPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target, com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path, Heuristic<com.github.yellowstonegames.grid.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.
    com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord>
    findShortestPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target, Heuristic<com.github.yellowstonegames.grid.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.
    static float[][]
    generateAStarCostMap(char[][] map)
    Given a char[][] for the map, produces a float[][] that can be used as a cost map by this class.
    static float[][]
    generateAStarCostMap(char[][] map, com.github.tommyettinger.ds.IntFloatMap costs, float defaultValue)
    Given a char[][] for the map, a jdkgdxds IntFloatMap that maps chars in the map to their costs, and a float value for unhandled characters, produces a float[][] that can be used as a map by AStarSearch.
    List<Class<?>>
    getSerializersNeeded()
    Gets a List of Class instances that must each be registered with a serialization library before this object can be successfully serialized or deserialized.
    int
    hashCode()
     
    void
    init(float[][] map)
    Re-initializes this DefaultGraph from a 2D float 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 float.
    void
    init(float[][] map, boolean eightWay)
    Re-initializes this DefaultGraph from a 2D float 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 float.
    void
    readExternal(ObjectInput in)
    Meant for deserialization using Fory.
    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(com.github.tommyettinger.ds.ObjectList<com.github.yellowstonegames.grid.Coord> sortedVertices)
    Perform a topological sort on the graph, and puts the sorted vertices in the supplied list.
    String
    toString()
     
    void
    writeExternal(ObjectOutput out)
    Meant for serialization using Fory.

    Methods inherited from class DirectedGraph

    algorithms, createNew, obtainEdge

    Methods inherited from class Graph

    addConnection, addConnection, addEdge, addEdge, addVertex, addVertices, addVertices, connectionExists, contains, disconnect, disconnect, edgeExists, getEdge, getEdge, getEdgeCount, getEdges, getEdges, getNode, getNodes, getVertices, isDirected, removeAllEdges, removeAllVertices, removeConnection, removeEdge, removeEdge, removeEdgeIf, removeEdges, removeNode, removeVertex, removeVertexIf, removeVertices, size, sortEdges, sortVertices

    Methods inherited from class Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

    • width

      public int width

    • height

      public int height

  • Constructor Details

    • CostlyGraph

      public CostlyGraph()
      No-op no-arg constructor, present for serialization; if you use this you must call init(float[][]) or init(float[][], boolean) before using the CostlyGraph.

    • CostlyGraph

      public CostlyGraph(float[][] map)
      Builds a DefaultGraph from a 2D float 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 float. This only builds connections along cardinal directions.
      Parameters:
      map - a 2D float array where negative numbers are impassable and non-negative ones represent costs to enter
      See Also:

    • CostlyGraph

      public CostlyGraph(float[][] map, boolean eightWay)
      Builds a DefaultGraph from a 2D float 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 float. 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 float 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:

    • 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(float[][], boolean) with the result of generateAStarCostMap(char[][]) for the 2D float array. You can get more control by calling generateAStarCostMap(char[][], IntFloatMap, float) and passing that to init() or a constructor that takes a 2D float 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(float[][], boolean) with the result of generateAStarCostMap(char[][]) for the 2D float array. You can get more control by calling generateAStarCostMap(char[][], IntFloatMap, float) and passing that to init() or a constructor that takes a 2D float 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

    • generateAStarCostMap

      public static float[][] generateAStarCostMap(char[][] map)
      Given a char[][] for the map, produces a float[][] that can be used as a cost map by this class. It expects any doors to be represented by '+' if closed or '/' if open and any walls to be '#' or box drawing characters. Any wall or closed door will be assigned a negative number, meaning it is impassable for the graph search, and all other chars will be assigned 1.0, giving them a normal cost.
      Parameters:
      map - a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() .
      Returns:
      a cost map suitable for use with AStarSearch

    • generateAStarCostMap

      public static float[][] generateAStarCostMap(char[][] map, com.github.tommyettinger.ds.IntFloatMap costs, float defaultValue)
      Given a char[][] for the map, a jdkgdxds IntFloatMap that maps chars in the map to their costs, and a float value for unhandled characters, produces a float[][] that can be used as a map by AStarSearch. It expects any doors to be represented by '+' if closed or '/' if open, and any walls to be '#' or box drawing characters. In the parameter costs, there does not need to be an entry for '#' or any box drawing characters, but if one is present for '#' it will apply that cost to both '#' and all box drawing characters, and if one is not present it will default to a negative number, meaning it is impassable for a graph search. For any other entry in costs, a char in the 2D char array that matches the key (which is an int, but can and should be in the valid char range) will correspond (at the same x,y position in the returned 2D float array) to that key's value in costs. If a char is used in the map but does not have a corresponding key in costs, it will be given the value of the parameter defaultValue, which is typically 1 unless a creature is limited to only moving in some terrain.

      The values in costs are different from those expected for DijkstraMap; negative numbers are impassable, 1 is the cost for a normal walkable tile, and higher numbers are harder to enter.

      An example use for this would be to make a creature unable to enter any non-water cell (like a fish), unable to enter doorways (like some mythological versions of vampires), or to make a wheeled vehicle take more time to move across rubble or rough terrain.

      A potentially common case that needs to be addressed is NPC movement onto staircases in games that have them; some games may find it desirable for NPCs to block staircases and others may not, but in either case you should give both '>' and '<', the standard characters for staircases, the same value in costs.

      Parameters:
      map - a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() .
      costs - a Map of Character keys representing possible elements in map, and Double values for their cost.
      defaultValue - a float that will be used as the cost for any characters that don't have a key in costs.
      Returns:
      a cost map suitable for use with AStarSearch

    • init

      public void init(float[][] map)
      Re-initializes this DefaultGraph from a 2D float 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 float. This only builds connections along cardinal directions.
      Parameters:
      map - a 2D float array where negative numbers are impassable and non-negative ones represent costs to enter
      See Also:

    • init

      public void init(float[][] map, boolean eightWay)
      Re-initializes this DefaultGraph from a 2D float 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 float. 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 float 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:

    • 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(com.github.tommyettinger.ds.ObjectList<com.github.yellowstonegames.grid.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 ObjectList 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 com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findShortestPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.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 com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> findShortestPath(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target, Heuristic<com.github.yellowstonegames.grid.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(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.Coord target, com.github.tommyettinger.ds.ObjectDeque<com.github.yellowstonegames.grid.Coord> path, Heuristic<com.github.yellowstonegames.grid.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 float findMinimumDistance(com.github.yellowstonegames.grid.Coord start, com.github.yellowstonegames.grid.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<com.github.yellowstonegames.grid.Coord> breadthFirstSearch(com.github.yellowstonegames.grid.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<com.github.yellowstonegames.grid.Coord> breadthFirstSearch(com.github.yellowstonegames.grid.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<com.github.yellowstonegames.grid.Coord> depthFirstSearch(com.github.yellowstonegames.grid.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<com.github.yellowstonegames.grid.Coord> depthFirstSearch(com.github.yellowstonegames.grid.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().

    • containsCycle

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

    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Meant for serialization using Fory. If a class overrides this with different behavior, readExternal(ObjectInput) must also be overridden to match that behavior.
      Specified by:
      writeExternal in interface Externalizable
      Overrides:
      writeExternal in class Graph<com.github.yellowstonegames.grid.Coord>
      Parameters:
      out - the stream to write the object to
      Throws:
      IOException - Includes any I/O exceptions that may occur

    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Meant for deserialization using Fory. If a class overrides this with different behavior, writeExternal(ObjectOutput) must also be overridden to match that behavior.
      Specified by:
      readExternal in interface Externalizable
      Overrides:
      readExternal in class Graph<com.github.yellowstonegames.grid.Coord>
      Parameters:
      in - the stream to read data from in order to restore the object
      Throws:
      IOException - if I/O errors occur
      ClassNotFoundException - If the class for an object being restored cannot be found.

    • 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 fewer; 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

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Graph<com.github.yellowstonegames.grid.Coord>

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Graph<com.github.yellowstonegames.grid.Coord>

    • toString

      public String toString()
      Overrides:
      toString in class DirectedGraph<com.github.yellowstonegames.grid.Coord>

    • getSerializersNeeded

      public List<Class<?>> getSerializersNeeded()
      Gets a List of Class instances that must each be registered with a serialization library before this object can be successfully serialized or deserialized. This is GwtIncompatible; none of the serialization libraries this is meant for have any support for GWT.
      Specified by:
      getSerializersNeeded in interface com.github.yellowstonegames.core.ISerializersNeeded
      Returns:
      a List of Class instances that must each be registered with a serialization library