package escape.validation; import escape.Board; import escape.interfaces.Coordinate; import escape.interfaces.EscapePiece; import escape.util.GamePiece; import escape.util.Location; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import static escape.enumerations.LocationType.*; import static escape.interfaces.EscapePiece.MovementPattern.*; import static escape.interfaces.EscapePiece.PieceAttributeID.*; import static escape.interfaces.EscapePiece.MovementPattern; public class PathFinder { //Bounds of our BFS array private int ROW = 0; private int COL = 0; // Denote possible moves from any given point private int rowNum[]; private int colNum[]; public boolean getPath(Board board, Location from, Location to){ Coordinate.CoordinateType type = board.getBoardType(); GamePiece piece = board.pieceAt(from); int range = 1; boolean hasUnBlock = false; boolean hasFly = false; MovementPattern pattern = OMNI; // Get attributes of piece if (piece != null) { for (int i = 0; i < piece.getAttributes().length; i++) { switch (piece.getAttributes()[i].getId()){ case DISTANCE: range = piece.getAttributes()[i].getValue(); break; case FLY: range = piece.getAttributes()[i].getValue(); hasFly = true; break; case UNBLOCK: hasUnBlock = true; break; } } pattern = piece.getMovementPattern(); } // Get graph of relevant board area Location[][] graph = board.getGraph(from,range); int[][] matrix = convertGraph(graph, from, to, hasUnBlock, hasFly); ROW = graph.length; COL = graph[0].length; //Define possible movement options if (type == Coordinate.CoordinateType.HEX) { rowNum = new int[]{-1, 0, 0, 1, -1, 1}; colNum = new int[]{0, -1, 1, 0, 1, -1}; } else { rowNum = new int[]{-1, 0, 0, 1, -1, -1, 1, 1}; colNum = new int[]{0, -1, 1, 0, -1, 1, -1, 1}; } Point start = getLoc(graph, from); Point end = getLoc(graph, to); int result = -1; if(start != null && end != null){ //debugPrintBoard(matrix, start, end); switch (pattern){ case LINEAR: result = linearDistance(matrix, start, end, type); break; case DIAGONAL: if(type == Coordinate.CoordinateType.SQUARE){ rowNum = new int[]{-1, -1, 1, 1}; colNum = new int[]{-1, 1, -1, 1}; } result = BFS(matrix, start, end); break; case ORTHOGONAL: if(type == Coordinate.CoordinateType.SQUARE){ rowNum = new int[]{-1, 0, 0, 1}; colNum = new int[]{0, -1, 1, 0}; } result = BFS(matrix, start, end); break; default: result = BFS(matrix, start, end); } } return result > -1 && range >= result; } /** * Convert given Location coordinates into a Point * @param graph * @param loc * @return Point form of given location */ private Point getLoc(Location[][] graph, Location loc){ Point point = null; for(int i = 0; i < graph.length; i ++){ for(int j = 0; j < graph[0].length; j ++){ if(graph[i][j].getX() == loc.getX() && graph[i][j].getY() == loc.getY()){ point = new Point(i,j); //System.out.println(i + " " + j); } } } return point; } /** * Converts the location 2D array into a 2D int array denoting valid and invalid spaces * Assumes that the destination is always valid. * @param graph * @param from * @param to * @return 2D int array of reachable spaces */ private int[][] convertGraph(Location[][] graph, Location from, Location to, boolean hasUnBlock, boolean hasFly){ int[][] matrix = new int[graph.length][graph[0].length]; for(int i = 0; i < graph.length; i ++){ for(int j = 0; j < graph[0].length; j ++){ if(hasFly){ matrix[i][j] = 1; } else if(graph[i][j].getX() == from.getX() && graph[i][j].getY() == from.getY()){ matrix[i][j] = 1; } else if(graph[i][j].getX() == to.getX() && graph[i][j].getY() == to.getY()){ matrix[i][j] = 1; } else if(graph[i][j].getPiece() != null || (graph[i][j].getLocationType() == BLOCK && !hasUnBlock)){ matrix[i][j] = 0; } else{ matrix[i][j] = 1; } } } return matrix; } // check whether given cell (row, col) // is a valid cell or not. boolean isValid(int row, int col) { // return true if row number and // column number is in range return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL); } /** * Performs BFS on the given matrix, starting at a given point and ending at the destination point * @param mat * @param src * @param dest * @return Distance between the start and end points, -1 if no path is found */ int BFS(int mat[][], Point src, Point dest) { if (mat[src.x][src.y] != 1 || mat[dest.x][dest.y] != 1) return -1; boolean [][]visited = new boolean[ROW][COL]; visited[src.x][src.y] = true; // Create a queue for BFS Queue<queueNode> q = new LinkedList<>(); queueNode s = new queueNode(src, 0); q.add(s); while (!q.isEmpty()) { queueNode curr = q.peek(); Point pt = curr.pt; // If we have reached the destination cell, // we are done if (pt.x == dest.x && pt.y == dest.y) return curr.dist; // Otherwise dequeue the front cell // in the queue and enqueue // its adjacent cells q.remove(); for (int i = 0; i < rowNum.length; i++) { int row = pt.x + rowNum[i]; int col = pt.y + colNum[i]; // if adjacent cell is valid, has path // and not visited yet, enqueue it. if (isValid(row, col) && mat[row][col] == 1 && !visited[row][col]) { // mark cell as visited and enqueue it visited[row][col] = true; queueNode Adjcell = new queueNode (new Point(row, col), curr.dist + 1 ); q.add(Adjcell); } } } return -1; } private int linearDistance(int[][] matrix, Point start, Point end, Coordinate.CoordinateType type){ int result; if(type == Coordinate.CoordinateType.HEX){ result = linearHexPath(matrix, start, end); } else{ result = linearSquarePath(matrix, start, end); } return result; } /** * Runs BFS using only orthogonal or diagonal moves. * @param matrix * @param start * @param end * @return distance from source or -1 if no path is available */ private int linearSquarePath(int[][] matrix, Point start, Point end){ int result = -1; if(isOrthogonal(start, end)){ if(end.x == start.x){ rowNum = new int[]{0, 0}; colNum = new int[]{1, -1}; result = BFS(matrix, start, end); } else{ rowNum = new int[]{1, -1}; colNum = new int[]{0, 0}; result = BFS(matrix, start, end); } } if(isDiagonal(start, end)){ if(end.y == (-1 * end.x) + (start.x + start.y)){ rowNum = new int[]{-1, 1}; colNum = new int[]{1, -1}; result = BFS(matrix, start, end); } else{ rowNum = new int[]{-1, 1}; colNum = new int[]{-1, 1}; result = BFS(matrix, start, end); } } return result; } private int linearHexPath(int[][] matrix, Point start, Point end){ int result = -1; if(isOrthogonal(start, end)){ if(end.x == start.x){ rowNum = new int[]{0, 0}; colNum = new int[]{1, -1}; result = BFS(matrix, start, end); } else{ rowNum = new int[]{1, -1}; colNum = new int[]{0, 0}; result = BFS(matrix, start, end); } } else{ rowNum = new int[]{1, -1}; colNum = new int[]{-1, 1}; result = BFS(matrix, start, end); } return result; } private boolean isOrthogonal(Point start, Point end){ return start.x == end.x || start.y == end.y; } private boolean isDiagonal(Point start, Point end){ return end.y == (-1 * end.x) + (start.x + start.y) || end.y == end.x + (start.y - start.x); } /* private void debugPrintBoard(int[][] matrix, Point start, Point end) { for (int i = 0; i < matrix.length; i++) { System.out.println(""); for (int j = 0; j < matrix[0].length; j++) { if (i == start.x && j == start.y) { System.out.print("S"); } else if (i == end.x && j == end.y) { System.out.print("E"); } else { System.out.print(matrix[i][j]); } //System.out.print(graph[i][j].getX() + "," + graph[i][j].getY() + "|"); } } } */ }