java - laberintos - Algoritmo de Prim para generar un laberinto: obtener la celda vecina

code laberintos

Question

Estoy basando un programa generador de laberinto en el algoritmo de Prim:

Este algoritmo es una versión aleatorizada del algoritmo de Prim.

1. Comience con una grilla llena de paredes.
2. Elige una celda, márcala como parte del laberinto. Agrega las paredes de la celda a la lista de la pared.
3. Si bien hay paredes en la lista:
   1. Elige un muro al azar de la lista. Si la celda del lado opuesto aún no está en el laberinto:
      1. Haz que la pared sea un pasaje y marca la celda del lado opuesto como parte del laberinto.
      2. Agregue las paredes vecinas de la celda a la lista de la pared.
   2. Si la celda del lado opuesto ya estaba en el laberinto, quite la pared de la lista.

(de Wikipedia )

Ya entiendo el algoritmo, me quedé atrapado en esta parte: "Saber si la célula vecina forma parte del laberinto o no" (esto significa, obtener primero la celda vecina) ya que las células son realmente nodos de un árbol (el laberinto, una matriz bidimensional de Células) y las paredes son los bordes entre esos nodos, pensé que sería necesario identificar cada pared con un par de puntos (x, y). ¿Cómo puedo saber si dos celdas están conectadas por una pared? (recuerde que cada celda tiene 4 paredes)

Pensé en usar la función equals (). Solo pido un pseudocódigo o tu mejor explicación para facilitar las cosas.

La clase My Wall tiene tres atributos: bool isWall (determina si se trata de un muro o un pasaje entre celdas); int x; int y (identificadores).

Si crees que necesitaría más atributos, estaré encantado de saberlo. Sé que hay una manera fácil, estoy atascado;) ¡Gracias por su tiempo!

Answer 1

Bueno, pasé toda la tarde codificando el generador de laberintos, basándome en tu ayuda. Ahora estoy recibiendo este tipo de laberintos (lo siento por la gran pantalla, no tengo un editor de imágenes aquí.

Creo que el problema es cómo estoy devolviendo la celda vecina. Tal vez no. Así es como devuelvo la celda contigua, lo hice de la manera @progenhard, el Muro tiene 2 celdas, cell1 y cell2, si cell1 está ocupado, devuelve cell2 y viceversa:

public Cell getNeighbourCell(Wall wall, Cell cell) {
if (wall.getCell1().equals(cell)) {
return wall.getCell2();
} else {
return wall.getCell1();
}
}

¡Gracias de nuevo!

Answer 2

No puedo hacer ningún comentario para agregar a la discusión, así que solo responderé con una respuesta. Básicamente Lee Meandor tiene la idea correcta.

Esta es la estructura básica de la relación célula a pared.

Entonces una celda tiene una pared norte sur oeste y este.

Una pared se encuentra entre dos celdas adyacentes que los conectan.

Class Cell{
Wall North;
Wall South;
Wall East;
Wall West;
}
Class Wall{
// You can store the cells that are connected to the wall but it''s not necessary.
Cell 1;
Cell 2;
bool isUP;
}

Lo importante a tener en cuenta es que las Células apunten a las paredes correctas.

Ese es un trabajo de lógica importante :).

Si necesita ayuda, solo deje caer un comentario.

Answer 3

Veamos lo que podemos definir:

 Cell[][] maze; // prepopulate with cells in a rectangular fashion.
// Populate adjacent cells with walls.
{
maze = new Cell[m][n];
for (i = 0 .. m) {
for (j = 0 .. n) {
cell = maze[i][j] = new Cell(m, n);
// fix top wall
if (i == 0) { // first row
cell.wall[0] = new Wall();
cell.wall[0].setIsEdge();
} else {
cell.wall[0] = maze[i-1][j].wall[2]; // my up is last row''s down
}
// fix bottom wall
cell.wall[2] = new Wall();
if (i == m-1) { // last row
cell.wall[2].setIsEdge();
}
// fix left wall
if (j == 0) { // leftmost column
cell.wall[3] = new Wall();
cell.wall[3].setIsEdge();
} else {
cell.wall[3] = maze[i][j-1].wall[1]; // my left is last col''s right
}
// fix right wall
cell.wall[1] = new Wall();
if (j == n-1) { // rightmost column
cell.wall[1].setIsEdge();
}
}
}
}
List walls = new List();
class Cell {
Wall[] walls = new Wall[4]; // 0 is up, 1 is right, 2 is down, 3 is left (count clockwise)
boolean isInMaze = false;
int x;
int y;
Cell(col, row) {
x = col;
y = row;
}
}
class Wall {
boolean isOpen = false; // open walls are passages
boolean isEdge = false; // edges have nothing on the other side.
Cell[] cells = new Cell[2];
}
Cell aCell = maze[randomx][randomy]; // make sure x,y in bounds
initializeCellInMaze(aCell, null);
while (!walls.isEmpty()) {
aWall = walls.get(randomWall); // in range
if (!(aWall.cell[0].isInMaze && aWall.cell[1].isInMaze)) {
// opposite cell NOT in maze
wall.setIsOpen();
Cell otherCell;
if (wall.cell[0].isInMaze) {
otherCell = wall.cell[1];
} else {
otherCell = wall.cell[0];
}
initializeCellInMaze(otherCell, aWall);
}
walls.remove(aWall); // or use index
}
initializeCellInMaze(cell, wallToSkip) {
cell.setIsInMaze();
for (i = 0 .. 3) if (cell.wall[i] != wallToSkip) walls.add(cell.wall[i]);
}