@staticmethod
def step(actions, curr_board, curr_agents, curr_bombs, curr_items, curr_flames, max_blast_strength=10):
    board_size = len(curr_board)
    flames = []
    for flame in curr_flames:
        position = flame.position
        if flame.is_dead():
            item_value = curr_items.get(position)
            if item_value:
                del curr_items[position]
            else:
                item_value = constants.Item.Passage.value
            curr_board[position] = item_value
        else:
            flame.tick()
            flames.append(flame)
    curr_flames = flames
    for flame in curr_flames:
        curr_board[flame.position] = constants.Item.Flames.value
    alive_agents = [agent for agent in curr_agents if agent.is_alive]
    desired_agent_positions = [agent.position for agent in alive_agents]
    for (num_agent, agent) in enumerate(alive_agents):
        position = agent.position
        curr_board[position] = constants.Item.Passage.value
        action = actions[agent.agent_id]
        if (action == constants.Action.Stop.value):
            pass
        elif (action == constants.Action.Bomb.value):
            position = agent.position
            if (not utility.position_is_bomb(curr_bombs, position)):
                bomb = agent.maybe_lay_bomb()
                if bomb:
                    curr_bombs.append(bomb)
        elif utility.is_valid_direction(curr_board, position, action):
            desired_agent_positions[num_agent] = agent.get_next_position(action)
    desired_bomb_positions = [bomb.position for bomb in curr_bombs]
    for (num_bomb, bomb) in enumerate(curr_bombs):
        curr_board[bomb.position] = constants.Item.Passage.value
        if bomb.is_moving():
            desired_position = utility.get_next_position(bomb.position, bomb.moving_direction)
            if (utility.position_on_board(curr_board, desired_position) and (not utility.position_is_powerup(curr_board, desired_position)) and (not utility.position_is_wall(curr_board, desired_position))):
                desired_bomb_positions[num_bomb] = desired_position
    crossings = {}

    def crossing(current, desired):
        'Checks to see if an agent is crossing paths'
        (current_x, current_y) = current
        (desired_x, desired_y) = desired
        if (current_x != desired_x):
            assert (current_y == desired_y)
            return ('X', min(current_x, desired_x), current_y)
        assert (current_x == desired_x)
        return ('Y', current_x, min(current_y, desired_y))
    for (num_agent, agent) in enumerate(alive_agents):
        if (desired_agent_positions[num_agent] != agent.position):
            desired_position = desired_agent_positions[num_agent]
            border = crossing(agent.position, desired_position)
            if (border in crossings):
                desired_agent_positions[num_agent] = agent.position
                (num_agent2, _) = crossings[border]
                desired_agent_positions[num_agent2] = alive_agents[num_agent2].position
            else:
                crossings[border] = (num_agent, True)
    for (num_bomb, bomb) in enumerate(curr_bombs):
        if (desired_bomb_positions[num_bomb] != bomb.position):
            desired_position = desired_bomb_positions[num_bomb]
            border = crossing(bomb.position, desired_position)
            if (border in crossings):
                desired_bomb_positions[num_bomb] = bomb.position
                (num, is_agent) = crossings[border]
                if (not is_agent):
                    desired_bomb_positions[num] = curr_bombs[num].position
            else:
                crossings[border] = (num_bomb, False)
    agent_occupancy = defaultdict(int)
    bomb_occupancy = defaultdict(int)
    for desired_position in desired_agent_positions:
        agent_occupancy[desired_position] += 1
    for desired_position in desired_bomb_positions:
        bomb_occupancy[desired_position] += 1
    change = True
    while change:
        change = False
        for (num_agent, agent) in enumerate(alive_agents):
            desired_position = desired_agent_positions[num_agent]
            curr_position = agent.position
            if ((desired_position != curr_position) and ((agent_occupancy[desired_position] > 1) or (bomb_occupancy[desired_position] > 1))):
                desired_agent_positions[num_agent] = curr_position
                agent_occupancy[curr_position] += 1
                change = True
        for (num_bomb, bomb) in enumerate(curr_bombs):
            desired_position = desired_bomb_positions[num_bomb]
            curr_position = bomb.position
            if ((desired_position != curr_position) and ((bomb_occupancy[desired_position] > 1) or (agent_occupancy[desired_position] > 1))):
                desired_bomb_positions[num_bomb] = curr_position
                bomb_occupancy[curr_position] += 1
                change = True
    agent_indexed_by_kicked_bomb = {}
    kicked_bomb_indexed_by_agent = {}
    delayed_bomb_updates = []
    delayed_agent_updates = []
    for (num_bomb, bomb) in enumerate(curr_bombs):
        desired_position = desired_bomb_positions[num_bomb]
        if (agent_occupancy[desired_position] == 0):
            continue
        agent_list = [(num_agent, agent) for (num_agent, agent) in enumerate(alive_agents) if (desired_position == desired_agent_positions[num_agent])]
        if (not agent_list):
            continue
        assert (len(agent_list) == 1)
        (num_agent, agent) = agent_list[0]
        if (desired_position == agent.position):
            if (desired_position != bomb.position):
                delayed_bomb_updates.append((num_bomb, bomb.position))
            continue
        if (not agent.can_kick):
            delayed_bomb_updates.append((num_bomb, bomb.position))
            delayed_agent_updates.append((num_agent, agent.position))
            continue
        direction = constants.Action(actions[agent.agent_id])
        target_position = utility.get_next_position(desired_position, direction)
        if (utility.position_on_board(curr_board, target_position) and (agent_occupancy[target_position] == 0) and (bomb_occupancy[target_position] == 0) and (not utility.position_is_powerup(curr_board, target_position)) and (not utility.position_is_wall(curr_board, target_position))):
            bomb_occupancy[desired_position] = 0
            delayed_bomb_updates.append((num_bomb, target_position))
            agent_indexed_by_kicked_bomb[num_bomb] = num_agent
            kicked_bomb_indexed_by_agent[num_agent] = num_bomb
            bomb.moving_direction = direction
        else:
            delayed_bomb_updates.append((num_bomb, bomb.position))
            delayed_agent_updates.append((num_agent, agent.position))
    for (num_bomb, bomb_position) in delayed_bomb_updates:
        desired_bomb_positions[num_bomb] = bomb_position
        bomb_occupancy[bomb_position] += 1
        change = True
    for (num_agent, agent_position) in delayed_agent_updates:
        desired_agent_positions[num_agent] = agent_position
        agent_occupancy[agent_position] += 1
        change = True
    while change:
        change = False
        for (num_agent, agent) in enumerate(alive_agents):
            desired_position = desired_agent_positions[num_agent]
            curr_position = agent.position
            if ((desired_position != curr_position) and ((agent_occupancy[desired_position] > 1) or (bomb_occupancy[desired_position] != 0))):
                if (num_agent in kicked_bomb_indexed_by_agent):
                    num_bomb = kicked_bomb_indexed_by_agent[num_agent]
                    bomb = curr_bombs[num_bomb]
                    desired_bomb_positions[num_bomb] = bomb.position
                    bomb_occupancy[bomb.position] += 1
                    del agent_indexed_by_kicked_bomb[num_bomb]
                    del kicked_bomb_indexed_by_agent[num_agent]
                desired_agent_positions[num_agent] = curr_position
                agent_occupancy[curr_position] += 1
                change = True
        for (num_bomb, bomb) in enumerate(curr_bombs):
            desired_position = desired_bomb_positions[num_bomb]
            curr_position = bomb.position
            if ((desired_position == curr_position) and (num_bomb not in agent_indexed_by_kicked_bomb)):
                continue
            bomb_occupancy_ = bomb_occupancy[desired_position]
            agent_occupancy_ = agent_occupancy[desired_position]
            if ((bomb_occupancy_ > 1) or (agent_occupancy_ != 0)):
                desired_bomb_positions[num_bomb] = curr_position
                bomb_occupancy[curr_position] += 1
                num_agent = agent_indexed_by_kicked_bomb.get(num_bomb)
                if (num_agent is not None):
                    agent = alive_agents[num_agent]
                    desired_agent_positions[num_agent] = agent.position
                    agent_occupancy[agent.position] += 1
                    del kicked_bomb_indexed_by_agent[num_agent]
                    del agent_indexed_by_kicked_bomb[num_bomb]
                change = True
    for (num_bomb, bomb) in enumerate(curr_bombs):
        if ((desired_bomb_positions[num_bomb] == bomb.position) and (not (num_bomb in agent_indexed_by_kicked_bomb))):
            bomb.stop()
        else:
            bomb.position = desired_bomb_positions[num_bomb]
    for (num_agent, agent) in enumerate(alive_agents):
        if (desired_agent_positions[num_agent] != agent.position):
            agent.move(actions[agent.agent_id])
            if utility.position_is_powerup(curr_board, agent.position):
                agent.pick_up(constants.Item(curr_board[agent.position]), max_blast_strength=max_blast_strength)
    exploded_map = np.zeros_like(curr_board)
    has_new_explosions = False
    for bomb in curr_bombs:
        bomb.tick()
        if bomb.exploded():
            has_new_explosions = True
        elif (curr_board[bomb.position] == constants.Item.Flames.value):
            bomb.fire()
            has_new_explosions = True
    while has_new_explosions:
        next_bombs = []
        has_new_explosions = False
        for bomb in curr_bombs:
            if (not bomb.exploded()):
                next_bombs.append(bomb)
                continue
            bomb.bomber.incr_ammo()
            for (_, indices) in bomb.explode().items():
                for (r, c) in indices:
                    if (not all([(r >= 0), (c >= 0), (r < board_size), (c < board_size)])):
                        break
                    if (curr_board[r][c] == constants.Item.Rigid.value):
                        break
                    exploded_map[r][c] = 1
                    if (curr_board[r][c] == constants.Item.Wood.value):
                        break
        curr_bombs = next_bombs
        for bomb in curr_bombs:
            if bomb.in_range(exploded_map):
                bomb.fire()
                has_new_explosions = True
    for bomb in curr_bombs:
        curr_board[bomb.position] = constants.Item.Bomb.value
    flame_positions = np.where((exploded_map == 1))
    for (row, col) in zip(flame_positions[0], flame_positions[1]):
        curr_flames.append(characters.Flame((row, col)))
    for flame in curr_flames:
        curr_board[flame.position] = constants.Item.Flames.value
    for agent in alive_agents:
        if (curr_board[agent.position] == constants.Item.Flames.value):
            agent.die()
        else:
            curr_board[agent.position] = utility.agent_value(agent.agent_id)
    return (curr_board, curr_agents, curr_bombs, curr_items, curr_flames)
@staticmethod
def step(actions, curr_board, curr_agents, curr_bombs, curr_items, curr_flames, max_blast_strength=10):
    board_size = len(curr_board)
    flames = []
    for flame in curr_flames:
        position = flame.position
        if flame.is_dead():
            item_value = curr_items.get(position)
            if item_value:
                del curr_items[position]
            else:
                item_value = constants.Item.Passage.value
            curr_board[position] = item_value
        else:
            flame.tick()
            flames.append(flame)
    curr_flames = flames
    for flame in curr_flames:
        curr_board[flame.position] = constants.Item.Flames.value
    alive_agents = [agent for agent in curr_agents if agent.is_alive]
    desired_agent_positions = [agent.position for agent in alive_agents]
    for (num_agent, agent) in enumerate(alive_agents):
        position = agent.position
        curr_board[position] = constants.Item.Passage.value
        action = actions[agent.agent_id]
        if (action == constants.Action.Stop.value):
            pass
        elif (action == constants.Action.Bomb.value):
            position = agent.position
            if (not utility.position_is_bomb(curr_bombs, position)):
                bomb = agent.maybe_lay_bomb()
                if bomb:
                    curr_bombs.append(bomb)
        elif utility.is_valid_direction(curr_board, position, action):
            desired_agent_positions[num_agent] = agent.get_next_position(action)
    desired_bomb_positions = [bomb.position for bomb in curr_bombs]
    for (num_bomb, bomb) in enumerate(curr_bombs):
        curr_board[bomb.position] = constants.Item.Passage.value
        if bomb.is_moving():
            desired_position = utility.get_next_position(bomb.position, bomb.moving_direction)
            if (utility.position_on_board(curr_board, desired_position) and (not utility.position_is_powerup(curr_board, desired_position)) and (not utility.position_is_wall(curr_board, desired_position))):
                desired_bomb_positions[num_bomb] = desired_position
    crossings = {}

    def crossing(current, desired):
        'Checks to see if an agent is crossing paths'
        (current_x, current_y) = current
        (desired_x, desired_y) = desired
        if (current_x != desired_x):
            assert (current_y == desired_y)
            return ('X', min(current_x, desired_x), current_y)
        assert (current_x == desired_x)
        return ('Y', current_x, min(current_y, desired_y))
    for (num_agent, agent) in enumerate(alive_agents):
        if (desired_agent_positions[num_agent] != agent.position):
            desired_position = desired_agent_positions[num_agent]
            border = crossing(agent.position, desired_position)
            if (border in crossings):
                desired_agent_positions[num_agent] = agent.position
                (num_agent2, _) = crossings[border]
                desired_agent_positions[num_agent2] = alive_agents[num_agent2].position
            else:
                crossings[border] = (num_agent, True)
    for (num_bomb, bomb) in enumerate(curr_bombs):
        if (desired_bomb_positions[num_bomb] != bomb.position):
            desired_position = desired_bomb_positions[num_bomb]
            border = crossing(bomb.position, desired_position)
            if (border in crossings):
                desired_bomb_positions[num_bomb] = bomb.position
                (num, is_agent) = crossings[border]
                if (not is_agent):
                    desired_bomb_positions[num] = curr_bombs[num].position
            else:
                crossings[border] = (num_bomb, False)
    agent_occupancy = defaultdict(int)
    bomb_occupancy = defaultdict(int)
    for desired_position in desired_agent_positions:
        agent_occupancy[desired_position] += 1
    for desired_position in desired_bomb_positions:
        bomb_occupancy[desired_position] += 1
    change = True
    while change:
        change = False
        for (num_agent, agent) in enumerate(alive_agents):
            desired_position = desired_agent_positions[num_agent]
            curr_position = agent.position
            if ((desired_position != curr_position) and ((agent_occupancy[desired_position] > 1) or (bomb_occupancy[desired_position] > 1))):
                desired_agent_positions[num_agent] = curr_position
                agent_occupancy[curr_position] += 1
                change = True
        for (num_bomb, bomb) in enumerate(curr_bombs):
            desired_position = desired_bomb_positions[num_bomb]
            curr_position = bomb.position
            if ((desired_position != curr_position) and ((bomb_occupancy[desired_position] > 1) or (agent_occupancy[desired_position] > 1))):
                desired_bomb_positions[num_bomb] = curr_position
                bomb_occupancy[curr_position] += 1
                change = True
    agent_indexed_by_kicked_bomb = {}
    kicked_bomb_indexed_by_agent = {}
    delayed_bomb_updates = []
    delayed_agent_updates = []
    for (num_bomb, bomb) in enumerate(curr_bombs):
        desired_position = desired_bomb_positions[num_bomb]
        if (agent_occupancy[desired_position] == 0):
            continue
        agent_list = [(num_agent, agent) for (num_agent, agent) in enumerate(alive_agents) if (desired_position == desired_agent_positions[num_agent])]
        if (not agent_list):
            continue
        assert (len(agent_list) == 1)
        (num_agent, agent) = agent_list[0]
        if (desired_position == agent.position):
            if (desired_position != bomb.position):
                delayed_bomb_updates.append((num_bomb, bomb.position))
            continue
        if (not agent.can_kick):
            delayed_bomb_updates.append((num_bomb, bomb.position))
            delayed_agent_updates.append((num_agent, agent.position))
            continue
        direction = constants.Action(actions[agent.agent_id])
        target_position = utility.get_next_position(desired_position, direction)
        if (utility.position_on_board(curr_board, target_position) and (agent_occupancy[target_position] == 0) and (bomb_occupancy[target_position] == 0) and (not utility.position_is_powerup(curr_board, target_position)) and (not utility.position_is_wall(curr_board, target_position))):
            bomb_occupancy[desired_position] = 0
            delayed_bomb_updates.append((num_bomb, target_position))
            agent_indexed_by_kicked_bomb[num_bomb] = num_agent
            kicked_bomb_indexed_by_agent[num_agent] = num_bomb
            bomb.moving_direction = direction
        else:
            delayed_bomb_updates.append((num_bomb, bomb.position))
            delayed_agent_updates.append((num_agent, agent.position))
    for (num_bomb, bomb_position) in delayed_bomb_updates:
        desired_bomb_positions[num_bomb] = bomb_position
        bomb_occupancy[bomb_position] += 1
        change = True
    for (num_agent, agent_position) in delayed_agent_updates:
        desired_agent_positions[num_agent] = agent_position
        agent_occupancy[agent_position] += 1
        change = True
    while change:
        change = False
        for (num_agent, agent) in enumerate(alive_agents):
            desired_position = desired_agent_positions[num_agent]
            curr_position = agent.position
            if ((desired_position != curr_position) and ((agent_occupancy[desired_position] > 1) or (bomb_occupancy[desired_position] != 0))):
                if (num_agent in kicked_bomb_indexed_by_agent):
                    num_bomb = kicked_bomb_indexed_by_agent[num_agent]
                    bomb = curr_bombs[num_bomb]
                    desired_bomb_positions[num_bomb] = bomb.position
                    bomb_occupancy[bomb.position] += 1
                    del agent_indexed_by_kicked_bomb[num_bomb]
                    del kicked_bomb_indexed_by_agent[num_agent]
                desired_agent_positions[num_agent] = curr_position
                agent_occupancy[curr_position] += 1
                change = True
        for (num_bomb, bomb) in enumerate(curr_bombs):
            desired_position = desired_bomb_positions[num_bomb]
            curr_position = bomb.position
            if ((desired_position == curr_position) and (num_bomb not in agent_indexed_by_kicked_bomb)):
                continue
            bomb_occupancy_ = bomb_occupancy[desired_position]
            agent_occupancy_ = agent_occupancy[desired_position]
            if ((bomb_occupancy_ > 1) or (agent_occupancy_ != 0)):
                desired_bomb_positions[num_bomb] = curr_position
                bomb_occupancy[curr_position] += 1
                num_agent = agent_indexed_by_kicked_bomb.get(num_bomb)
                if (num_agent is not None):
                    agent = alive_agents[num_agent]
                    desired_agent_positions[num_agent] = agent.position
                    agent_occupancy[agent.position] += 1
                    del kicked_bomb_indexed_by_agent[num_agent]
                    del agent_indexed_by_kicked_bomb[num_bomb]
                change = True
    for (num_bomb, bomb) in enumerate(curr_bombs):
        if ((desired_bomb_positions[num_bomb] == bomb.position) and (not (num_bomb in agent_indexed_by_kicked_bomb))):
            bomb.stop()
        else:
            bomb.position = desired_bomb_positions[num_bomb]
    for (num_agent, agent) in enumerate(alive_agents):
        if (desired_agent_positions[num_agent] != agent.position):
            agent.move(actions[agent.agent_id])
            if utility.position_is_powerup(curr_board, agent.position):
                agent.pick_up(constants.Item(curr_board[agent.position]), max_blast_strength=max_blast_strength)
    exploded_map = np.zeros_like(curr_board)
    has_new_explosions = False
    for bomb in curr_bombs:
        bomb.tick()
        if bomb.exploded():
            has_new_explosions = True
        elif (curr_board[bomb.position] == constants.Item.Flames.value):
            bomb.fire()
            has_new_explosions = True
    while has_new_explosions:
        next_bombs = []
        has_new_explosions = False
        for bomb in curr_bombs:
            if (not bomb.exploded()):
                next_bombs.append(bomb)
                continue
            bomb.bomber.incr_ammo()
            for (_, indices) in bomb.explode().items():
                for (r, c) in indices:
                    if (not all([(r >= 0), (c >= 0), (r < board_size), (c < board_size)])):
                        break
                    if (curr_board[r][c] == constants.Item.Rigid.value):
                        break
                    exploded_map[r][c] = 1
                    if (curr_board[r][c] == constants.Item.Wood.value):
                        break
        curr_bombs = next_bombs
        for bomb in curr_bombs:
            if bomb.in_range(exploded_map):
                bomb.fire()
                has_new_explosions = True
    for bomb in curr_bombs:
        curr_board[bomb.position] = constants.Item.Bomb.value
    flame_positions = np.where((exploded_map == 1))
    for (row, col) in zip(flame_positions[0], flame_positions[1]):
        curr_flames.append(characters.Flame((row, col)))
    for flame in curr_flames:
        curr_board[flame.position] = constants.Item.Flames.value
    for agent in alive_agents:
        if (curr_board[agent.position] == constants.Item.Flames.value):
            agent.die()
        else:
            curr_board[agent.position] = utility.agent_value(agent.agent_id)
    return (curr_board, curr_agents, curr_bombs, curr_items, curr_flames)