Prim用于生成迷宫的算法：获取相邻小区

我正在基于Prim算法的迷宫生成器程序：

该算法是Prim算法的随机版本。

1. 从充满墙壁的网格开始。
2. 选择一个单元格，将其标记为迷宫的一部分。 将单元格的墙添加到墙列表中。
3. 虽然列表中有墙：
   1. 从列表中选择一个随机墙。 如果对面的细胞尚未进入迷宫：
      1. 使墙成为通道，并将对面的细胞标记为迷宫的一部分。
      2. 将单元格的相邻墙添加到墙列表中。
   2. 如果对面的单元格已经在迷宫中，请从列表中移除墙壁。

（来自维基百科 ）

我已经理解了算法，我只是坚持这一部分：“知道相邻小区是否构成了迷宫的一部分”（这意味着，首先获取相邻小区）因为小区实际上是树的节点（迷宫，一个二维细胞arrays），墙壁是这些节点之间的边缘，我认为有必要用一对点（x，y）识别每个墙壁。 我怎么知道两个单元是否通过墙连接？ （记住每个单元有4面墙）

我想过使用equals（）函数。 我只是要求伪代码或你的最佳解释，这将使事情变得更容易。

My Wall类有三个属性：bool isWall（确定它是墙还是单元格之间的通道）; int x; int y（标识符）。

如果您认为我需要更多属性，我将很高兴知道。 我知道有一个简单的方法，我只是卡住了;）谢谢你的时间！

Answer 1

让我们看看我们可以定义：

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]); } 

Answer 2

我不能评论添加到讨论如此生病只回答一个答案。 基本上Lee Meandor有正确的想法。

这是细胞与细胞关系的基本结构。

因此，一个小区有一个北西南和东墙。

墙壁位于连接它们的两个相邻单元之间。

 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; } 

要记住的重要一点是细胞指向正确的墙壁。

这是一些重要的逻辑工作:)。

如果您需要帮助，请发表评论。

Answer 3

好吧，我花了整个下午编写迷宫发生器，基于你的帮助。 现在我得到了这种迷宫（对于大屏幕截图我很抱歉，我没有这里的图片编辑器。

我认为问题是我如何返回邻居小区。 也许不吧。 这就是我返回相邻单元格的方式，我做了@progenhard方式，Wall有2个单元格，cell1和cell2，如果cell1被占用，则返回cell2，反之亦然：

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

再次感谢！