スクリプトで最初に気付くのは、init()初期化visitedして for ループを使用して初期化し、その後すぐに再度初期化して値を true に設定しないことです。これにより、壁がなくなると思います。その後、生成中のスクリプトで、最初に訪問済みとしてマークされたものがないため、壁にいることが可能になります。次に、迷路の生成中に配列の「端」にあるため、エラーである配列外のセルを参照しようとする場合があります。したがって、2番目の初期化を削除しますvisited
もう 1 つ注意する必要があるのは、無限 while ループの可能性です。隣人が存在すると判断した後の while ループは、理論上、隣人を取得するために適切な r を継続的に選択しない可能性がありますが、非常に遅くなる可能性があります。代わりに、すべての隣人を見つけて、それらを「ArrayList」に入れてから、ランダムなものを選択します。以下のソースを参照してください。
メソッドに別のエラーが存在しますdraw。for ループは、条件を の代わりにx < this.dimensionandにして反復する必要があります。そうしないと、ArrayIndexOutOfBounds エラーが発生します。y < this.dimension<=
最後に、printlnその内容の情報を含まない配列のあまり価値のない表現を出力するメソッドです。代わりにこれを行います：
System.out.println(Arrays.deepToString(this.grid));
これが私の完成版のコードです。セルの状態を追跡するためのブリッジと元の変数の必要性を置き換えた内部クラスCellとフィールドCell[][] cellsがあります。MyMaze外側の 2 行と 2 列は、範囲外でArrayIndexOutOfBoundsExceptionキャッチされgetCellて戻るため、削除されnullます。大規模なボードでスタック オーバーフローが発生しないように、過剰な呼び出しを防ぐために、生成の概念が変更されました。ボードは長方形にすることができます。ソルバーは、A-star アルゴリズムに基づいて実装されています。意味のある表現を生成するために、出力が更新されました。「X」は壁で、「*」は解決済みのパスです。コメントされているので、何が起こっているのかを読むことができるはずです
これが私の最終的なソースです：
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<Cell> 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<Cell> 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<Cell> 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<Cell> 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<Cell>(){
@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();
System.out.print(maze);
}
}