到目前為止，我得到了一個 DFS 迷宮演算法，它可以讓我完美地完成一條路徑的迷宮。我想知道如何在幾乎沒有改變的情況下獲得不止一條通往終點的道路。我應該隨機拆除墻壁嗎？但問題是我不想要完全沒有墻壁的空曠廣場......
到目前為止，這是我的演算法：
private void computeMaze(){
Random random = new Random();
Stack<Block> stack = new Stack<Block>(); //Stack
Block current = blocks[0][0]; //First cell is the current cell
current.setVisited(true); //Mark as accessed
//Create a count; first cell has been accessed, if no unvisited cells left == 0
int unVisitedCount=ROWS*COLS-1;
//Create a list of neighbors
List<Block> neighbors;
Block next;
while(unVisitedCount > 0) {
//Find neighbor collection (unreachable)
neighbors = current.findNeighbors();
//If the current cell has unvisited neighbors then:
if(neighbors.size() > 0) {
//Randomly select a neighbor from this list
int index = random.nextInt(neighbors.size());
next = neighbors.get(index);
//Stack the current cell
stack.push(current);
//Remove the walls between the current maze cell and the randomly selected neighbor cell
this.removeWall(current,next);
//Mark the neighbor cell as visited and use it as the current cell
next.setVisited(true);
current = next;
//If an access is marked, the counter is decreased by 1
unVisitedCount--;
}
else if(stack.isEmpty() == false) {//If the current maze cell does not have an unreachable adjacent maze cell, and the stack is not empty
/*
1.The maze unit at the top of the stack comes out of the stack
2.Make it the current maze unit
*/
Block cell = stack.pop();
current = cell;
}
}
}
//Find neighbors as well as the getneighbors methods:
//Find out whether the current cell has an unreachable neighbor cell
public List<Block> findNeighbors() {
//The neighbors are divided into upper, lower, left and right
List<Block> res = new ArrayList<Block>();
Block top = this.getNeighbor(0,false);
Block right = this.getNeighbor(1,false);
Block bottom = this.getNeighbor(2,false);
Block left = this.getNeighbor(3,false);
if(top != null){
res.add(top);
}
if(right != null){
res.add(right);
}
if(bottom != null){
res.add(bottom);
}
if(left != null){
res.add(left);
}
return res;//Return neighbor array
}
//Get neighbors according to direction
public Block getNeighbor(int type,boolean lose_visited) {
Block neighbor;
int neighbor_i = 0, neighbor_j = 0;
switch(type) {
case 0:
neighbor_i = this.i-1;
neighbor_j = this.j;
break;
case 1:
neighbor_i = this.i;
neighbor_j = this.j 1;
break;
case 2:
neighbor_i = this.i 1;
neighbor_j = this.j;
break;
case 3:
neighbor_i = this.i;
neighbor_j = this.j-1;
break;
}
Block[][] blocks = panel.blocks;
//It's beyond the boundary, therefore no neighbor
if(neighbor_i < 0 || neighbor_j < 0 || neighbor_i >= panel.ROWS || neighbor_j >= panel.COLS) {
neighbor = null;
}
//The dimensions are permitted, neighbor is found
else {
//Find the neighbor, either top/bottom/left/right
neighbor = blocks[neighbor_i][neighbor_j];
//Judge whether it is accessed. If it is accessed, null is returned
if(neighbor.visited && !lose_visited) {//lose_visited equals true to ignore access
neighbor = null;
}
}
return neighbor;
}
uj5u.com熱心網友回復：
要制作具有多個解決方案的迷宮，您需要移除將解決方案路徑連接到非解決方案路徑的墻壁。然后，這會將非解決方案路徑添加到替代解決方案中。
您可能還想移除多個非解決方案路徑之間的一些墻，以使其變得有趣。
留下空白區域的問題更有趣。您可以從一個單元格中移除所有 4 個墻壁，如果它是一個 4 路連接點，那么您需要檢查相鄰單元格是否有墻壁連接到角落。
然后問題是洗掉微不足道 - 連接是否接近兩條路徑已經連接的點？
- 識別具有該連接屬性的所有墻部分，
- 不要導致瑣碎的解決方案
- 檢查洗掉該墻部分是否不會破壞角落規則。
- 隨機選擇一個
- 重復直到你有足夠的替代解決方案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482723.html
下一篇：查找樹高時超出時間限制