We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. The Bomberman Game
  2. Discussions

The Bomberman Game

  • VictorAtPL
     + 0 comments

    Python. Runs the clock and does explosions until a cycle is found. For explosion steps, grid for each t % 2 == 1 is kept in the memory. Once the cycle is found, number of steps to make through the graph is calculated, as well as the cycle length and with that final_t can be calculated.

    def removeBomb(row, idx):
    return row[:idx] + '.' + row[idx + 1:]


def gridHash(grid):
    return "".join(grid)

def createAllBombsGrid(r, c):
    return ["O" * c for _ in range(r)]

def gridAfterExplode(grid, r, c):
    new_grid = createAllBombsGrid(r, c)
    
    for i in range(r):
        for j in range(c):
            if grid[i][j] == '.':
                continue
                
            # it's a bomb!
            for x in range(-1, 2):
                # iter -1..1
                
                i_shifted = i + x
                if i_shifted < 0 or i_shifted == r:
                    continue
                    
                new_grid[i_shifted] = removeBomb(new_grid[i_shifted], j)
                
            for y in range(-1, 2):
                j_shifted = j + y
                if j_shifted < 0 or j_shifted == c:
                    continue
                    
                new_grid[i] = removeBomb(new_grid[i], j_shifted)
                
    return new_grid
    
    
def calculate_final_t(cycle_start, cycle_end, n):
    n_minus_cycle_start = n - cycle_start
    moves_to_make = n_minus_cycle_start // 2
    
    diff = cycle_end - cycle_start
    cycle_len = diff // 2 + 1
    
    remainder = moves_to_make % cycle_len
    
    final_t = cycle_start + remainder * 2
    
    return final_t

def bomberMan(n, grid):
    r = len(grid)
    c = len(grid[0])
    
    grid_hash = gridHash(grid)
    grid_to_t = {grid_hash: 1}
    t_to_grid = {1: grid}
    
    if n == 1:
        return grid
        
    if n % 2 == 0:
        return createAllBombsGrid(r, c)
    
    for t in range(3, n + 1, 2):
        grid = gridAfterExplode(grid, r, c)
        
        if t == n:
            return grid
        
        grid_hash = gridHash(grid)
        
        if grid_hash in grid_to_t:
            break
        else:
            grid_to_t[grid_hash] = t
            t_to_grid[t] = grid
    
    cycle_start = grid_to_t[grid_hash]
    cycle_end = t - 2
    
    final_t = calculate_final_t(cycle_start, cycle_end, n)

    return t_to_grid[final_t]