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