For game AI development, I am currently using a slight modification on the DFS "count the islands" problem (specification below) as a solution to the One Hive Rule for the game of Hive. This may not be the ideal solution so I am open to any other ideas if you note DFS is not the best approach. Thank you.
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
My version utilises a 2D map (matrix) which represents a hexagonal board for the game.
The differences are:
- My implementation uses hexagons so each cell has 6 neighbours, not 8
Blanks represent 0s and anything else are 1s- My implementation purposely stops if/when it finds more than one island/hive
My question is can the code be improved with regards to time complexity?
from insects import Blank
class HiveGraph:
def __init__(self, board):
self.row = board.height
self.col = board.width
self.visited = [[False for _ in range(self.col)] for _ in range(self.row)]
self.graph = board.board
# A function to check if a given hexagon can be included in DFS
def is_safe(self, row, col):
# row number is in range,
# column number is in range,
# and hexagon is Blank and not yet visited
return (0 <= row < self.row and
0 <= col < self.col and
not self.visited[row][col] and
type(self.graph[row][col]) is not Blank)
# DFS for a 2D matrix. It only considers
# the 6 neighbours as adjacent pieces
def dfs(self, row, col):
print(row, col)
# These arrays are used to get row and
# column numbers of 6 neighbours
# of a given hexagon
if col % 2 == 1:
row_nbr = [-1, 0, 0, 1, 1, 1]
col_nbr = [ 0, -1, 1, -1, 0, 1]
else:
row_nbr = [-1, -1, -1, 0, 0, 1]
col_nbr = [-1, 0, 1, -1, 1, 0]
# Mark this hexagon as visited
self.visited[row][col] = True
# Recur for all connected neighbours
for k in range(6):
if self.is_safe(row + row_nbr[k], col + col_nbr[k]):
self.dfs(row + row_nbr[k], col + col_nbr[k])
def one_hive(self):
# Initialize count as 0 and traverse
# through the all hexagons of given matrix
count = 0
for row in range(self.row):
for col in range(self.col):
# If a hexagon not Blank and is not visited yet,
# then new hive found
if not self.visited[row][col] and type(self.graph[row][col]) is not Blank:
# Visit all hexagons in this hive
# and increment hive count
count += 1
if count > 1:
return False
self.dfs(row, col)
return True
Refer to this image for row, col matrix values for the layout of hexagons: Hexagon encoding for matrix
1 Answer 1
Given there are only 22-28 tiles in a Hive game, the time complexity of the check probably doesn't matter much. Nevertheless, a modified scanline fill algorithm might be faster than a DFS. This answer explains the algorithm fairly well. In this use case it might be easier to scan down the columns instead of across the rows.
From the rules of the Hive game, it seems the "one hive rule" would need to be checked when a tile is put down on the playing field and when it is picked up from the playing field (e.g., to move it). When a tile is put down, it is sufficient to make sure it touches another tile (beside or on top).
When a tile is picked up, it is necessary to make sure it's former neighbor tiles are still connected via another path. This may be trivial such as when the neighbors are adjacent, or may require searching for a path using a DFS, BFS, spanning tree, or fill/paint algorithm.
In any case, the AI should know which tile is being moved, so it shouldn't be necessary to scan the hex grid. Just start from one of the tiles neighbors.