当前位置: 动力学知识库 > 问答 > 编程问答 >

java - Checking if chosen tiles on a 2d matrix are all connected

问题描述:

I'm creating a game with a map which is a [100 tile x 100 tile] matrix. Players will be able create "Duchies" by combining 4 tiles. The game will let the player choose 4 tiles and check if those tiles are all connected to each other and let the player create the Duchy only if they are so.

So my isConnected() method will take in an ArrayList<Tiles> and the tiles have getX() and getY() methods, which returns their X and Y coordinates on the grid. If the tiles are connected to each other, it will return true, or false, if they are not. Note that the tiles can not be connected diagonally.

It is worth mentioning that the method will need to work for ArrayList's of tiles with more than 4 tiles since it will need to check bigger lists of tiles and that the Duchy scenario was an example of how the method will be used.


Just to visualize the whole thing;

Example Input 1 (X's are the selected tiles):

[X][X][X][ ][ ]

[ ][X][X][ ][ ]

[ ][ ][X][ ][ ]

[ ][ ][X][ ][ ]

[ ][ ][ ][ ][ ]

Example Output 1:

true


Example Input 2 (X's are the selected tiles):

[X][X][X][ ][ ]

[ ][X][X][ ][ ]

[ ][ ][ ][X][X]

[ ][ ][ ][ ][ ]

[ ][ ][ ][ ][ ]

Example Output 2:

false


I thought of comparing all tiles to all the others one by one and assume that the tiles were all connected if all tiles were connected to at least one other tile, but realized that it wouldn't work because it would return true for something like this:

[X][X][ ][ ][ ]

[ ][ ][ ][ ][ ]

[ ][ ][ ][ ][ ]

[ ][ ][X][X][ ]

[ ][ ][ ][ ][ ]


I couldn't figure out a way to do this and I couldn't find a solution for such a problem online. I would appreciate any help, thanks. :)

网友答案:

Sort of a flood fill algorithm; takes one of the tiles and recursively consumes adjacent tiles in the selection. If all tiles in the selection were consumed in this way, all selected tiles are connected.

boolean isConnected(List<Tile> selection) {

    if (selection.isEmpty())
        return true; // ?????

    Queue<Tile> toConsume = new LinkedList<>(selection);
    Queue<Tile> queue = new LinkedList<>();
    queue.add(toConsume.remove());

    while (!queue.isEmpty() && !toConsume.isEmpty()) {
        Tile tile = queue.remove();
        findNeighbours(tile, toConsume)
        .forEach(n -> {
            toConsume.remove(n);
            queue.add(n);
        });
    }
    return toConsume.isEmpty();
}

List<Tile> findNeighbours(Tile tile, Collection<Tile> tiles) {
    return tiles.stream()
        .filter(t -> distance(t, tile) == 1)
        .collect(Collectors.toList());
}

int distance(Tile a, Tile b) {
    int dx = a.getX() - b.getX();
    int dy = a.getY() - b.getY();
    return Math.abs(dx) + Math.abs(dy);
}
分享给朋友:
您可能感兴趣的文章:
随机阅读: