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; // ?????

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

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

Top