简单的Java 2darrays迷宫样本
我正在工作或了解如何创建一个简单的java 2d迷宫 ，它应该如下所示：
int [][] maze = { {1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,1,0,1,0,0,0,0,0,1}, {1,0,1,0,0,0,1,0,1,1,1,0,1}, {1,0,0,0,1,1,1,0,0,0,0,0,1}, {1,0,1,0,0,0,0,0,1,1,1,0,1}, {1,0,1,0,1,1,1,0,1,0,0,0,1}, {1,0,1,0,1,0,0,0,1,1,1,0,1}, {1,0,1,0,1,1,1,0,1,0,1,0,1}, {1,0,0,0,0,0,0,0,0,0,1,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1} }; 这个已创建的想法是设置一个起点和目标点并通过使用递归深度首先找到路径。 但必须说我很难创造迷宫。
你有什么建议怎么做吗？
或者也许是教程的链接？
我现在主要关注的是创造迷宫。
迷宫实施有很多变化。
一切都取决于您想要使用哪些方面？
这是一些起点迷宫生成算法 。
我过去试图解决这个问题。 我猜测代码片段，而不是很多单词，我试图这样做。
迷宫发生器代码 ：
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Random; public class MyMaze { private int dimensionX, dimensionY; // dimension of maze private int gridDimensionX, gridDimensionY; // dimension of output grid private char[][] grid; // output grid private Cell[][] cells; // 2d array of Cells private Random random = new Random(); // The random object // initialize with x and y the same public MyMaze(int aDimension) { // Initialize this(aDimension, aDimension); } // constructor public MyMaze(int xDimension, int yDimension) { dimensionX = xDimension; dimensionY = yDimension; gridDimensionX = xDimension * 4 + 1; gridDimensionY = yDimension * 2 + 1; grid = new char[gridDimensionX][gridDimensionY]; init(); generateMaze(); } private void init() { // create cells cells = new Cell[dimensionX][dimensionY]; for (int x = 0; x < dimensionX; x++) { for (int y = 0; y < dimensionY; y++) { cells[x][y] = new Cell(x, y, false); // create cell (see Cell constructor) } } } // inner class to represent a cell private class Cell { int x, y; // coordinates // cells this cell is connected to ArrayList| neighbors = new ArrayList<>(); // solver: if already used boolean visited = false; // solver: the Cell before this one in the path Cell parent = null; // solver: if used in last attempt to solve path boolean inPath = false; // solver: distance travelled this far double travelled; // solver: projected distance to end double projectedDist; // impassable cell boolean wall = true; // if true, has yet to be used in generation boolean open = true; // construct Cell at x, y Cell(int x, int y) { this(x, y, true); } // construct Cell at x, y and with whether it isWall Cell(int x, int y, boolean isWall) { this.x = x; this.y = y; this.wall = isWall; } // add a neighbor to this cell, and this cell as a neighbor to the other void addNeighbor(Cell other) { if (!this.neighbors.contains(other)) { // avoid duplicates this.neighbors.add(other); } if (!other.neighbors.contains(this)) { // avoid duplicates other.neighbors.add(this); } } // used in updateGrid() boolean isCellBelowNeighbor() { return this.neighbors.contains(new Cell(this.x, this.y + 1)); } // used in updateGrid() boolean isCellRightNeighbor() { return this.neighbors.contains(new Cell(this.x + 1, this.y)); } // useful Cell representation @Override public String toString() { return String.format("Cell(%s, %s)", x, y); } // useful Cell equivalence @Override public boolean equals(Object other) { if (!(other instanceof Cell)) return false; Cell otherCell = (Cell) other; return (this.x == otherCell.x && this.y == otherCell.y); } // should be overridden with equals @Override public int hashCode() { // random hash code method designed to be usually unique return this.x + this.y * 256; } } // generate from upper left (In computing the y increases down often) private void generateMaze() { generateMaze(0, 0); } // generate the maze from coordinates x, y private void generateMaze(int x, int y) { generateMaze(getCell(x, y)); // generate from Cell } private void generateMaze(Cell startAt) { // don't generate from cell not there if (startAt == null) return; startAt.open = false; // indicate cell closed for generation ArrayList | cells = new ArrayList<>(); cells.add(startAt); while (!cells.isEmpty()) { Cell cell; // this is to reduce but not completely eliminate the number // of long twisting halls with short easy to detect branches // which results in easy mazes if (random.nextInt(10)==0) cell = cells.remove(random.nextInt(cells.size())); else cell = cells.remove(cells.size() - 1); // for collection ArrayList | neighbors = new ArrayList<>(); // cells that could potentially be neighbors Cell[] potentialNeighbors = new Cell[]{ getCell(cell.x + 1, cell.y), getCell(cell.x, cell.y + 1), getCell(cell.x - 1, cell.y), getCell(cell.x, cell.y - 1) }; for (Cell other : potentialNeighbors) { // skip if outside, is a wall or is not opened if (other==null || other.wall || !other.open) continue; neighbors.add(other); } if (neighbors.isEmpty()) continue; // get random cell Cell selected = neighbors.get(random.nextInt(neighbors.size())); // add as neighbor selected.open = false; // indicate cell closed for generation cell.addNeighbor(selected); cells.add(cell); cells.add(selected); } } // used to get a Cell at x, y; returns null out of bounds public Cell getCell(int x, int y) { try { return cells[x][y]; } catch (ArrayIndexOutOfBoundsException e) { // catch out of bounds return null; } } public void solve() { // default solve top left to bottom right this.solve(0, 0, dimensionX - 1, dimensionY -1); } // solve the maze starting from the start state (A-star algorithm) public void solve(int startX, int startY, int endX, int endY) { // re initialize cells for path finding for (Cell[] cellrow : this.cells) { for (Cell cell : cellrow) { cell.parent = null; cell.visited = false; cell.inPath = false; cell.travelled = 0; cell.projectedDist = -1; } } // cells still being considered ArrayList | openCells = new ArrayList<>(); // cell being considered Cell endCell = getCell(endX, endY); if (endCell == null) return; // quit if end out of bounds { // anonymous block to delete start, because not used later Cell start = getCell(startX, startY); if (start == null) return; // quit if start out of bounds start.projectedDist = getProjectedDistance(start, 0, endCell); start.visited = true; openCells.add(start); } boolean solving = true; while (solving) { if (openCells.isEmpty()) return; // quit, no path // sort openCells according to least projected distance Collections.sort(openCells, new Comparator | (){ @Override public int compare(Cell cell1, Cell cell2) { double diff = cell1.projectedDist - cell2.projectedDist; if (diff > 0) return 1; else if (diff < 0) return -1; else return 0; } }); Cell current = openCells.remove(0); // pop cell least projectedDist if (current == endCell) break; // at end for (Cell neighbor : current.neighbors) { double projDist = getProjectedDistance(neighbor, current.travelled + 1, endCell); if (!neighbor.visited || // not visited yet projDist < neighbor.projectedDist) { // better path neighbor.parent = current; neighbor.visited = true; neighbor.projectedDist = projDist; neighbor.travelled = current.travelled + 1; if (!openCells.contains(neighbor)) openCells.add(neighbor); } } } // create path from end to beginning Cell backtracking = endCell; backtracking.inPath = true; while (backtracking.parent != null) { backtracking = backtracking.parent; backtracking.inPath = true; } } // get the projected distance // (A star algorithm consistent) public double getProjectedDistance(Cell current, double travelled, Cell end) { return travelled + Math.abs(current.x - end.x) + Math.abs(current.y - current.x); } // draw the maze public void updateGrid() { char backChar = ' ', wallChar = 'X', cellChar = ' ', pathChar = '*'; // fill background for (int x = 0; x < gridDimensionX; x ++) { for (int y = 0; y < gridDimensionY; y ++) { grid[x][y] = backChar; } } // build walls for (int x = 0; x < gridDimensionX; x ++) { for (int y = 0; y < gridDimensionY; y ++) { if (x % 4 == 0 || y % 2 == 0) grid[x][y] = wallChar; } } // make meaningful representation for (int x = 0; x < dimensionX; x++) { for (int y = 0; y < dimensionY; y++) { Cell current = getCell(x, y); int gridX = x * 4 + 2, gridY = y * 2 + 1; if (current.inPath) { grid[gridX][gridY] = pathChar; if (current.isCellBelowNeighbor()) if (getCell(x, y + 1).inPath) { grid[gridX][gridY + 1] = pathChar; grid[gridX + 1][gridY + 1] = backChar; grid[gridX - 1][gridY + 1] = backChar; } else { grid[gridX][gridY + 1] = cellChar; grid[gridX + 1][gridY + 1] = backChar; grid[gridX - 1][gridY + 1] = backChar; } if (current.isCellRightNeighbor()) if (getCell(x + 1, y).inPath) { grid[gridX + 2][gridY] = pathChar; grid[gridX + 1][gridY] = pathChar; grid[gridX + 3][gridY] = pathChar; } else { grid[gridX + 2][gridY] = cellChar; grid[gridX + 1][gridY] = cellChar; grid[gridX + 3][gridY] = cellChar; } } else { grid[gridX][gridY] = cellChar; if (current.isCellBelowNeighbor()) { grid[gridX][gridY + 1] = cellChar; grid[gridX + 1][gridY + 1] = backChar; grid[gridX - 1][gridY + 1] = backChar; } if (current.isCellRightNeighbor()) { grid[gridX + 2][gridY] = cellChar; grid[gridX + 1][gridY] = cellChar; grid[gridX + 3][gridY] = cellChar; } } } } } // simply prints the map public void draw() { System.out.print(this); } // forms a meaningful representation @Override public String toString() { updateGrid(); String output = ""; for (int y = 0; y < gridDimensionY; y++) { for (int x = 0; x < gridDimensionX; x++) { output += grid[x][y]; } output += "\n"; } return output; } // run it public static void main(String[] args) { MyMaze maze = new MyMaze(20); maze.solve(); maze.draw(); } } |
这不是最好的解决方案，我此时的任务是自己实现这个算法。 它有明确的评论。
输出：
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X * X ********* X ***** XXX X * X * XXXXX * X * X * XXXX X ***** X ***** X * X * XXXX XXXXXXXXX * XXXXX * X * XXXX XX ***** X * X * XXX XX XXXXX * X * X * XXXXXXXXX X XXX ***** X * X X XXXXXXXXXXXXXXXXX * XXXXXXXXXXXXX X ***************** X ***** XX X * XXXXXXXXXXXXX * XXXXX * XXX X ***** XX ********* XXX XXXXX * X XXXXXXXXXXXXXXXXXXXXX X X ***** X ***** X ***** X X * XXXXXXXXXXXXX * X * XXXXX * X * X X ************* X * X * X ***** X * X XXXXXXXXXXXXX * X * X * X * XXXXX * X X ***** X ***** X * X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
我希望它可以作为一些解决方案的例证。
如果我理解你的问题，我会做的是：1。创建一个特定大小的棋盘（将所有坐标改为你想要的数字 – 在你的例子’1’中）。 我不会使用递归函数，因为你可能最终会绘制整个板（考虑什么会使递归停止）。
您可以创建一个接收起始协调，结束协调和数组（板）的函数。 函数的伪代码：为下一个绘画方向设置一个变量（将其设置为起始协调）。 绘制下一个协调0.而下一个协调！=到结束协调：绘制下一个协调0.使用Random将协调设置为4个方向之一。
你应该添加限制（如果下一个协调是彩绘的/迷宫的边界等…选择不同的协调）。 祝好运！