在Java中的二維數組中檢查樓層一致性

Question

我正在研究迷宮生成算法。我的算法從預定義的圖塊中選擇並創建一個迷宮。這是我的代碼生成的一個例子。 '**'是牆，'__'是空的地面空間。

** ** ** ** ** ** ** ** ** ** ** 
** __ __ __ ** ** __ ** ** ** ** 
** ** __ __ __ __ __ ** ** ** ** 
** ** __ __ __ __ __ ** ** ** ** 
** __ __ __ ** __ ** ** ** ** ** 
** __ __ __ ** __ ** ** ** ** ** 
** __ __ ** ** __ ** ** ** ** ** 
** __ __ __ ** ** ** __ __ __ ** 
** __ ** __ ** ** ** __ __ ** ** 
** __ __ __ ** ** ** __ ** ** ** 
** ** ** ** ** ** ** ** ** ** ** 

我需要創建一個函數來測試是否所有樓層空間都已連接。即確保所有'__'空間都可以從其他'__'空間到達。這意味着上述迷宮是非法的，但下面是可以接受的。

** ** ** ** ** ** ** ** ** ** ** 
** ** __ ** __ __ __ __ __ __ ** 
** __ __ __ __ __ __ __ __ __ ** 
** ** __ ** __ __ ** ** __ ** ** 
** __ __ __ ** ** ** __ __ __ ** 
** __ __ ** ** ** ** __ __ __ ** 
** __ __ __ ** ** ** __ __ __ ** 
** ** ** __ ** ** ** ** ** ** ** 
** __ __ __ __ __ __ ** ** ** ** 
** __ __ __ ** ** ** ** ** ** ** 
** ** ** ** ** ** ** ** ** ** ** 

我不知道如何最好地解決這個問題。我想我應該使用BFS搜索，但我不是100％確定的。所有建議歡迎，提前致謝！

Answer 1

Flood-fill從一些起始樓層。你可以通過另外一個二維數組來做到這一點。您可以使用BFS（基於隊列）或DFS（基於堆棧）。重點只是做一個詳盡的搜索。

再次穿過迷宮。如果您發現上述步驟中沒有填充任何樓層，我們知道它與其他樓層沒有關聯。

Answer 2

一個簡單的A *搜索可以達到這個目的，儘管取決於你的迷宮的大小，它可能會慢一點。在僞代碼：

for(t=0; t<arrayOfAllTiles.length; t++) { 
    for(i=t; i<arrayOfAllTiles.length; i++) { 
     if(doAStarTest(i, t) == false) { 
      //oh no, not congruent 
     } 
    } 
} 

紅色斑點奧運會上，有一些壯觀的教程，包括一個在A *：http://www.redblobgames.com/pathfinding/a-star/introduction.html

Answer 3

我已經waaaaaaaaaay太多的業餘時間，代碼按預期工作，但一些方法可能可能會做得更好一點。

主要

package maze; 

public class Main 
{ 
    public static void main(String[] args) 
    { 
     //Create a new maze and populate it. 
     Maze maze = new Maze(11, 11); 
     maze.populate(); 

     //Get the total number of floor tiles in the entire maze. 
     int totalFloor = maze.getTotalFloorCount(); 

     //Get the total number of floor tiles in a section. 
     int sectionFloor = maze.getSectionFloorCount(maze.x, maze.y); 

     //If the section has an equal amount of floor tiles with the entire maze, then the maze is connected. 
     System.out.println("Section/Total: " + sectionFloor + "/" + totalFloor); 
     if (sectionFloor == totalFloor) 
     { 
      System.out.println("SUCCESS! Maze is valid!"); 
     } 
     else 
     { 
      System.out.println("FAIL! Maze is not valid!"); 
     } 
    } 
} 

瓷磚

package maze; 

public class Tile 
{ 
    public static final String FLOOR = "__"; 
    public static final String WALL = "**"; 

    private int x; 
    private int y; 

    public Tile(int x, int y) 
    { 
     this.setX(x); 
     this.setY(y); 
    } 

    /** ---------------------------------------- **/ 
    /** --- GETTERS & SETTERS    --- **/ 
    /** ---------------------------------------- **/ 

    public int getX() { 
     return x; 
    } 

    public void setX(int x) { 
     this.x = x; 
    } 

    public int getY() { 
     return y; 
    } 

    public void setY(int y) { 
     this.y = y; 
    } 
} 

迷宮

package maze; 

import java.util.ArrayList; 
import java.util.List; 

public class Maze 
{ 
    //Maze dimensions. 
    private int mazeDimX = 11; 
    private int mazeDimY = 11; 
    private String[][] array; 

    //Last found floor tile coordinates. 
    public int x = -1; 
    public int y = -1; 

    public Maze(int mazeDimX, int mazeDimY) 
    { 
     this.mazeDimX = mazeDimX; 
     this.mazeDimY = mazeDimY; 
     array = new String[mazeDimX][mazeDimY]; 
    } 

    /** ---------------------------------------- **/ 
    /** --- METHODS       --- **/ 
    /** ---------------------------------------- **/ 

    public void populate() 
    { 
     //Insert code to populate maze here. 
    } 

    public int getTotalFloorCount() 
    { 
     int count = 0; 
     for (int i=0; i<mazeDimX; i++) 
     { 
      for (int j=0; j<mazeDimY; j++) 
      { 
       if (array[i][j].equals(Tile.FLOOR)) 
       { 
        //Increase the total count of floor tiles. 
        count++; 

        //Stores the last found floor tile. 
        x = i; 
        y = j; 
       } 
      } 
     } 
     return count; 
    } 

    public int getSectionFloorCount(int x, int y) 
    { 
     int tileCount = 0; 

     List<Tile> tiles = new ArrayList<Tile>(); 
     List<Tile> removedTiles = new ArrayList<Tile>(); 
     if (x != -1 && y != -1) 
     { 
      tiles.add(new Tile(x, y)); 
     } 

     while (!tiles.isEmpty()) 
     { 
      //Increase current tile count. 
      tileCount++; 

      //Get next tile. 
      Tile tile = tiles.get(0); 

      //Get x and y of tile. 
      int tileX = tile.getX(); 
      int tileY = tile.getY(); 

      //Get up, down, left and right tiles. 
      Tile up =  getAdjacentTile(tileX, tileY - 1); 
      Tile down =  getAdjacentTile(tileX, tileY + 1); 
      Tile left =  getAdjacentTile(tileX - 1, tileY); 
      Tile right = getAdjacentTile(tileX + 1, tileY); 

      //Add tile if required. 
      addTile(tiles, removedTiles, up); 
      addTile(tiles, removedTiles, down); 
      addTile(tiles, removedTiles, left); 
      addTile(tiles, removedTiles, right); 

      //Move the tile from the checked list to the removed list. 
      tiles.remove(tile); 
      removedTiles.add(tile); 
     } 
     return tileCount; 
    } 

    private Tile getAdjacentTile(int x, int y) 
    { 
     //Check if the tile is in bounds. 
     if (x >= 0 && x < mazeDimX && y >= 0 && y < mazeDimY) 
     { 
      //Check if the tile is a floor. 
      if (array[x][y].equals(Tile.FLOOR)) 
      { 
       return new Tile(x, y); 
      } 
     } 
     return null; 
    } 

    private void addTile(List<Tile> tiles, List<Tile> removedTiles, Tile tile) 
    { 
     boolean isRemoved = false; 
     if (tile != null) 
     { 
      //Check if the tile has already been removed. 
      for (int i=0; i<removedTiles.size(); i++) 
      { 
       Tile removed = removedTiles.get(i); 
       if (tile.getX() == removed.getX() && tile.getY() == removed.getY()) 
       { 
        isRemoved = true; 
        break; 
       } 
      } 
      if (!isRemoved) 
      { 
       boolean isInList = false; 
       //Check if the tile already is in the list to be checked. 
       for (int i=0; i<tiles.size(); i++) 
       { 
        Tile item = tiles.get(i); 
        if (tile.getX() == item.getX() && tile.getY() == item.getY()) 
        { 
         isInList = true; 
        } 
       } 
       //Add the tile if it hasn't been checked or removed already. 
       if (!isInList) 
       { 
        tiles.add(tile); 
       } 
      } 
     } 
    } 
}