Javaの2D配列のフロア合同を確認してください

Question

私は迷路生成アルゴリズムに取り組んでいます。私のアルゴリズムは、あらかじめ定義されたタイルから選択し、迷路を作成します。ここに私のコードによって生成された例があります。 '**'は壁で、 '__'は空きスペースです。

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

すべてのフロアスペースが接続されているかどうかをテストする関数を作成する必要があります。すなわち、すべての '__'スペースが他のすべての '__'スペースから到達可能であることを確認する。それは上記の迷路が違法であることを意味しますが、以下は許容されます。

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

この問題に最も近づける方法がわかりません。私はBFS検索を使うべきだと思いますが、私は100％確信していません。すべての提案は歓迎です、事前に感謝！

Answer 1

Flood-fill開始階の階。これを行うには、別の2D配列を持つか、これを行うだけです。 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 
     } 
    } 
} 

レッドブロブゲーム*上のものを含め、いくつかの壮大なチュートリアルがあります。意図したものではなくて、私はwaaaaaaaaaayすぎ暇な時、コードが動作しているhttp://www.redblobgames.com/pathfinding/a-star/introduction.html

Answer 3

方法のいくつかの可能性おそらくもう少しうまくいくでしょう。

メイン

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