001package squidpony.squidai.graph; 002 003import squidpony.squidgrid.Direction; 004import squidpony.squidmath.Coord; 005 006import java.io.Serializable; 007import java.util.ArrayList; 008import java.util.Arrays; 009 010/** 011 * A default setting for an {@link UndirectedGraph} of Coord vertices where all connections have cost 1. This should be 012 * initialized with a 2D (rectangular) char array using the map convention where {@code '#'} is a wall and anything else 013 * is passable. 014 * <br> 015 * Created by Tommy Ettinger on 7/9/2020. 016 */ 017public class DefaultGraph extends UndirectedGraph<Coord> implements Serializable { 018 private static final long serialVersionUID = 1L; 019 020 public int width; 021 public int height; 022 023 /** 024 * No-op no-arg constructor, present for {@link Serializable}; if you use this you must call {@link #init(char[][])} 025 * or {@link #init(char[][], boolean)} before using the DefaultGraph. 026 */ 027 public DefaultGraph() { 028 super(); 029 width = 0; 030 height = 0; 031 } 032 /** 033 * Builds a DefaultGraph from a 2D char array that uses {@code '#'} to represent any kind of inaccessible cell, with 034 * all other chars treated as walkable. This only builds connections along cardinal directions. 035 * @param map a 2D char array where {@code '#'} represents an inaccessible area (such as a wall) and anything else is walkable 036 */ 037 public DefaultGraph(char[][] map) { 038 this(map, false); 039 } 040 041 /** 042 * Builds a DefaultGraph from a 2D char array that uses {@code '#'} to represent any kind of inaccessible cell, with 043 * all other chars treated as walkable. If {@code eightWay} is true, this builds connections along diagonals as well 044 * as along cardinals, but if {@code eightWay} is false, it only builds connections along cardinal directions. 045 * @param map a 2D char array where {@code '#'} represents an inaccessible area (such as a wall) and anything else is walkable 046 * @param eightWay if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connections 047 */ 048 public DefaultGraph(char[][] map, boolean eightWay) { 049 super(); 050 init(map, eightWay); 051 } 052 053 /** 054 * Re-initializes a DefaultGraph from a 2D char array that uses {@code '#'} to represent any kind of inaccessible 055 * cell, with all other chars treated as walkable. This only builds connections along cardinal directions. 056 * @param map a 2D char array where {@code '#'} represents an inaccessible area (such as a wall) and anything else is walkable 057 */ 058 public void init(char[][] map) { 059 init(map, false); 060 } 061 062 /** 063 * Re-initializes this DefaultGraph from a 2D char array that uses {@code '#'} to represent any kind of inaccessible 064 * cell, with all other chars treated as walkable. If {@code eightWay} is true, this builds connections along 065 * diagonals as well as along cardinals, but if {@code eightWay} is false, it only builds connections along cardinal 066 * directions. 067 * @param map a 2D char array where {@code '#'} represents an inaccessible area (such as a wall) and anything else is walkable 068 * @param eightWay if true, this will build connections on diagonals as well as cardinal directions; if false, this will only use cardinal connections 069 */ 070 public void init(char[][] map, boolean eightWay) { 071 width = map.length; 072 height = map[0].length; 073 Coord.expandPoolTo(width, height); 074 ArrayList<Coord> vs = new ArrayList<>(width * height >>> 1); 075 vertexMap.clear(); 076 edgeMap.clear(); 077 for (int x = 0; x < width; x++) { 078 for (int y = 0; y < height; y++) { 079 if(map[x][y] != '#') 080 { 081 Coord pt = Coord.get(x, y); 082 vs.add(pt); 083 addVertex(pt); 084 } 085 } 086 } 087 final int sz = vs.size(); 088 Coord center, off; 089 final Direction[] outer = eightWay ? Direction.CLOCKWISE : Direction.CARDINALS_CLOCKWISE; 090 Direction dir; 091 for (int i = 0; i < sz; i++) { 092 center = vs.get(i); 093 for (int j = 0; j < outer.length; j++) { 094 dir = outer[j]; 095 off = center.translate(dir); 096 if(off.isWithin(width, height) && map[center.x + dir.deltaX][center.y + dir.deltaY] != '#') 097 { 098 if(!edgeExists(center, off)) 099 { 100 addEdge(center, off); 101 } 102 } 103 } 104 } 105 106 } 107 108 /** 109 * Find a minimum weight spanning tree using Kruskal's algorithm. 110 * @return a Graph object containing a minimum weight spanning tree (if this graph is connected - 111 * in general a minimum weight spanning forest) 112 */ 113 public Graph<Coord> findMinimumWeightSpanningTree() { 114 return algorithms.findMinimumWeightSpanningTree(); 115 } 116 117 /** 118 * Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue. 119 * @param start the starting vertex 120 * @param target the target vertex 121 * @return a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices 122 */ 123 public ArrayList<Coord> findShortestPath(Coord start, Coord target) { 124 return algorithms.findShortestPath(start, target); 125 } 126 127 /** 128 * 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. 129 * @param start the starting vertex 130 * @param target the target vertex 131 * @param heuristic typically predefined in {@link Heuristic}, this determines how the optimal path will be estimated 132 * @return a list of vertices from start to target containing the ordered vertices of a shortest path, including both the start and target vertices 133 */ 134 public ArrayList<Coord> findShortestPath(Coord start, Coord target, Heuristic<Coord> heuristic) { 135 return algorithms.findShortestPath(start, target, heuristic); 136 } 137 138 /** 139 * Find the shortest path between the start and target vertices, using the A* search algorithm with the provided 140 * heuristic, and implemented with a priority queue. Fills path with a list of vertices from start to target 141 * containing the ordered vertices of a shortest path, including both the start and target vertices. 142 * @param start the starting vertex 143 * @param target the target vertex 144 * @param path the list of vertices to which the path vertices should be added 145 * @return true if a path was found, or false if no path could be found 146 */ 147 public boolean findShortestPath(Coord start, Coord target, ArrayList<Coord> path, Heuristic<Coord> heuristic) { 148 return algorithms.findShortestPath(start, target, path, heuristic); 149 } 150 151 /** 152 * Find the shortest path between the start and target vertices, using Dijkstra's algorithm implemented with a priority queue. 153 * @param start the starting vertex 154 * @param target the target vertex 155 * @return the sum of the weights in a shortest path from the starting vertex to the target vertex 156 */ 157 public double findMinimumDistance(Coord start, Coord target) { 158 return algorithms.findMinimumDistance(start, target); 159 } 160 161 /** 162 * Perform a breadth first search starting from the specified vertex. 163 * @param coord the vertex at which to start the search 164 * @param maxVertices the maximum number of vertices to process before terminating the search 165 * @param maxDepth the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be 166 * considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the 167 * returned graph 168 * @return a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. 169 * The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be 170 * reflected in the iteration order of the collections returned by {@link Graph#getVertices()} and {@link Graph#getEdges()}. 171 */ 172 public Graph<Coord> breadthFirstSearch(Coord coord, int maxVertices, int maxDepth) { 173 return algorithms.breadthFirstSearch(coord, maxVertices, maxDepth); 174 } 175 176 /** 177 * Perform a breadth first search starting from the specified vertex. 178 * @param coord the vertex at which to start the search 179 * @return a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. 180 * The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be 181 * reflected in the iteration order of the collections returned by {@link Graph#getVertices()} and {@link Graph#getEdges()}. 182 */ 183 public Graph<Coord> breadthFirstSearch(Coord coord) { 184 return algorithms.breadthFirstSearch(coord); 185 } 186 187 /** 188 * Perform a depth first search starting from the specified vertex. 189 * @param coord the vertex at which to start the search 190 * @param maxVertices the maximum number of vertices to process before terminating the search 191 * @param maxDepth the maximum edge distance (the number of edges in a shortest path between vertices) a vertex should have to be 192 * considered for processing. If a vertex has a distance larger than the maxDepth, it will not be added to the 193 * returned graph 194 * @return a Graph object containing all the processed vertices, and the edges from which each vertex was encountered. 195 * The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be 196 * reflected in the iteration order of the collections returned by {@link Graph#getVertices()} and {@link Graph#getEdges()}. 197 */ 198 public Graph<Coord> depthFirstSearch(Coord coord, int maxVertices, int maxDepth) { 199 return algorithms.depthFirstSearch(coord, maxVertices, maxDepth); 200 } 201 202 /** 203 * Perform a depth first search starting from the specified vertex. 204 * @param coord the vertex at which to start the search 205 * @return a Graph object containing all the processed vertices (all the vertices in this graph), and the edges from which each vertex was encountered. 206 * The vertices and edges in the returned graph will be in the order they were encountered in the search, and this will be 207 * reflected in the iteration order of the collections returned by {@link Graph#getVertices()} and {@link Graph#getEdges()}. 208 */ 209 public Graph<Coord> depthFirstSearch(Coord coord) { 210 return algorithms.depthFirstSearch(coord); 211 } 212 213 /** 214 * Checks whether there are any cycles in the graph using depth first searches. 215 * @return true if the graph contains a cycle, false otherwise 216 */ 217 public boolean detectCycle() { 218 return algorithms.detectCycle(); 219 } 220 221 /** 222 * Creates a 1D char array (which can be passed to {@link String#valueOf(char[])}) filled with a grid made of the 223 * vertices in this Graph and their estimated costs, if this has done an estimate. Each estimate is rounded to the 224 * nearest int and only printed if it is 4 digits or less; otherwise this puts '####' in the grid cell. This is a 225 * building-block for toString() implementations that may have debugging uses as well. 226 * @return a 1D char array containing newline-separated rows of space-separated grid cells that contain estimated costs or '####' for unexplored 227 */ 228 public char[] show() { 229 final int w5 = width * 5; 230 final char[] cs = new char[w5 * height]; 231 Arrays.fill(cs, '#'); 232 for (int i = 4; i < cs.length; i += 5) { 233 cs[i] = (i + 1) % w5 == 0 ? '\n' : ' '; 234 } 235 final int vs = vertexMap.size(), rid = algorithms.lastRunID(); 236 Node<Coord> nc; 237 for (int i = 0; i < vs; i++) { 238 nc = vertexMap.getAt(i); 239 if(!nc.seen || nc.lastRunID != rid || nc.distance >= 9999.5) 240 continue; 241 int d = (int) (nc.distance + 0.5), x = nc.object.x * 5, y = nc.object.y; 242 cs[y * w5 + x ] = (d >= 1000) ? (char) ('0' + d / 1000) : ' '; 243 cs[y * w5 + x + 1] = (d >= 100) ? (char) ('0' + d / 100 % 10) : ' '; 244 cs[y * w5 + x + 2] = (d >= 10) ? (char) ('0' + d / 10 % 10) : ' '; 245 cs[y * w5 + x + 3] = (char) ('0' + d % 10); 246 } 247 return cs; 248 } 249}