Checking gender congruence in a 2D array in Java

I am working on a maze generation algorithm. My algorithm selects from predefined fragments and creates a maze. Here is an example of my code. "**" is a wall and "__" is an empty space.

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

      

I need to create a function that will test to see if all space is connected. those. make sure all "__" spaces can be reached from any other "__" space. This means the above labyrinth is illegal, but below is acceptable.

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

      

I'm not sure how best to approach this issue. I think I should be using BFS search, but I'm not 100% sure. Any suggestions are welcome, thanks in advance!

+3


source to share


3 answers


Flooding fills the floors from some initial floor. You can do it either with another 2D array. You can use BFS (queue based) or DFS (stack based). It's just a matter of doing an exhaustive search.



Start the maze again. If you find any floor that has not been filled with the above stage, we know that it is not related to the rest.

+1


source


I have waaaaaaaaaay too much free time, the code works as intended, but some of the methods could probably be done a little better.

home

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

      

Tile



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

      

Maze

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

      

+1


source


A simple A * search will work well for this purpose, although depending on the size of your maze it can be slow. In pseudocode:

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

      

Red Blob Games has some exciting tutorials, including one on A *: http://www.redblobgames.com/pathfinding/a-star/introduction.html

0


source







All Articles