Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The first thing I notice in your script is in <code>init()</code> you initialize <code>visited</code> and use for loops to initialize it, and then immediately after you initialize again and don't set any values in it to true. This I think causes the walls to become eliminated. Then later on in the script during generation it becomes possible to be at a wall because none are marked visited initially. Then during maze generation since it's at the 'edge' of the array it may try to reference a cell outside the array which is your error. So remove the second initialization of <code>visited</code></p> <p>Another thing you should be wary of is the potential of an infinite while loop. The while loop after determining that there was a neighbor has the potential to continually not pick the right r to get the neighbor in theory, but it does have the potential to slow down tremendously. Instead, I would find all neighbors, put them into an `ArrayList and then pick a random one. See source below.</p> <p>Another error exists in the <code>draw</code> method. The for loop should iterate with the conditions being <code>x &lt; this.dimension</code> and <code>y &lt; this.dimension</code> instead of <code>&lt;=</code>. Otherwise you'll get ArrayIndexOutOfBounds error.</p> <p>Finally the <code>println</code> method we'll print a less than valuable representation of the array that contains no information of its contents. Do this instead:</p> <pre><code>System.out.println(Arrays.deepToString(this.grid)); </code></pre> <hr> <p>Here's my finalized version of the code. There is an inner class <code>Cell</code> and a field <code>Cell[][] cells</code> in <code>MyMaze</code> which replaced the need for bridges and the original variables for tracking the state of cells. The outer 2 rows and columns are removed because the <code>ArrayIndexOutOfBoundsException</code> is caught by <code>getCell</code> and returns <code>null</code> when out of bounds. The idea of generation has been altered to prevent excessive calling to avoid getting a stack overflow on large boards. Boards can be rectangular now. The solver is implemented based on A-star algorithm. The output has been updated to produce meaningful representation. The "X" are walls and the "*" is the solved path. It is commented so should be able to read through what's going on</p> <p>Here is my finalized source :</p> <pre><code>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 &lt; dimensionX; x++) { for (int y = 0; y &lt; 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&lt;Cell&gt; neighbors = new ArrayList&lt;&gt;(); // 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 &amp;&amp; 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&lt;Cell&gt; cells = new ArrayList&lt;&gt;(); 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&lt;Cell&gt; neighbors = new ArrayList&lt;&gt;(); // 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&lt;Cell&gt; openCells = new ArrayList&lt;&gt;(); // 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&lt;Cell&gt;(){ @Override public int compare(Cell cell1, Cell cell2) { double diff = cell1.projectedDist - cell2.projectedDist; if (diff &gt; 0) return 1; else if (diff &lt; 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 &lt; 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 &lt; gridDimensionX; x ++) { for (int y = 0; y &lt; gridDimensionY; y ++) { grid[x][y] = backChar; } } // build walls for (int x = 0; x &lt; gridDimensionX; x ++) { for (int y = 0; y &lt; gridDimensionY; y ++) { if (x % 4 == 0 || y % 2 == 0) grid[x][y] = wallChar; } } // make meaningful representation for (int x = 0; x &lt; dimensionX; x++) { for (int y = 0; y &lt; 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 &lt; gridDimensionY; y++) { for (int x = 0; x &lt; 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); } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POMaze generation - ArrayIndexOutOfBoundsException
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDoubleMx2
    1. USDoubleMx2
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POMaze generation - ArrayIndexOutOfBoundsException
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAs I understood this `..I replaced everything except the first line of ` should be into `init()`?
      singulars
      1. PO
      1. USnazar_art
    2. CO@nazar_art No, in the `init()` method the only thing I did was remove the second `visited = new boolean[dimension+2][dimension+2];`. Additionally, the codeblock in my answer is currently the entire body of my `generateMaze(int, int)`. I can post my modified source if you want, it works for me.
      singulars
      1. PO
      1. USDoubleMx2
    3. COIt will be really helpful.
      singulars
      1. PO
      1. USnazar_art
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload