__init__.py
1 #!/usr/bin/env python 2 import abc 3 import json 4 import logging 5 import queue 6 7 from . import commands, networking, constants 8 from .positionals import Direction, Position 9 10 11 class Entity(abc.ABC): 12 """ 13 Base Entity Class from whence Ships, Dropoffs and Shipyards inherit 14 """ 15 def __init__(self, owner, id, position): 16 self.owner = owner 17 self.id = id 18 self.position = position 19 20 @staticmethod 21 def _generate(player_id): 22 """ 23 Method which creates an entity for a specific player given input from the engine. 24 :param player_id: The player id for the player who owns this entity 25 :return: An instance of Entity along with its id 26 """ 27 ship_id, x_position, y_position = map(int, input().split()) 28 return ship_id, Entity(player_id, ship_id, Position(x_position, y_position)) 29 30 def __repr__(self): 31 return "{}(id={}, {})".format(self.__class__.__name__, 32 self.id, 33 self.position) 34 35 36 class Dropoff(Entity): 37 """ 38 Dropoff class for housing dropoffs 39 """ 40 pass 41 42 43 class Shipyard(Entity): 44 """ 45 Shipyard class to house shipyards 46 """ 47 def spawn(self): 48 """Return a move to spawn a new ship.""" 49 return commands.GENERATE 50 51 52 class Ship(Entity): 53 """ 54 Ship class to house ship entities 55 """ 56 def __init__(self, owner, id, position, halite_amount): 57 super().__init__(owner, id, position) 58 self.halite_amount = halite_amount 59 60 @property 61 def is_full(self): 62 """Is this ship at max halite capacity?""" 63 return self.halite_amount >= constants.MAX_HALITE 64 65 def make_dropoff(self): 66 """Return a move to transform this ship into a dropoff.""" 67 return "{} {}".format(commands.CONSTRUCT, self.id) 68 69 def move(self, direction): 70 """ 71 Return a move to move this ship in a direction without 72 checking for collisions. 73 """ 74 raw_direction = direction 75 if not isinstance(direction, str) or direction not in "nsew": 76 raw_direction = Direction.convert(direction) 77 return "{} {} {}".format(commands.MOVE, self.id, raw_direction) 78 79 def stay_still(self): 80 """ 81 Don't move this ship. 82 """ 83 return "{} {} {}".format(commands.MOVE, self.id, commands.STAY_STILL) 84 85 @staticmethod 86 def _generate(player_id): 87 """ 88 Creates an instance of a ship for a given player given the engine's input. 89 :param player_id: The id of the player who owns this ship 90 :return: The ship id and ship object 91 """ 92 ship_id, x_position, y_position, halite = map(int, input().split()) 93 return ship_id, Ship(player_id, ship_id, Position(x_position, y_position), halite) 94 95 def __repr__(self): 96 return "{}(id={}, {}, cargo={} halite)".format(self.__class__.__name__, 97 self.id, 98 self.position, 99 self.halite_amount) 100 101 102 class Game: 103 """ 104 The game object holds all metadata pertinent to the game and all its contents 105 """ 106 def __init__(self): 107 """ 108 Initiates a game object collecting all start-state instances for the contained items for pre-game. 109 Also sets up basic logging. 110 """ 111 self.turn_number = 0 112 113 # Grab constants JSON 114 raw_constants = input() 115 constants.load_constants(json.loads(raw_constants)) 116 117 num_players, self.my_id = map(int, input().split()) 118 119 logging.basicConfig( 120 filename="bot-{}.log".format(self.my_id), 121 filemode="w", 122 level=logging.DEBUG, 123 ) 124 125 self.players = {} 126 for player in range(num_players): 127 self.players[player] = Player._generate() 128 self.me = self.players[self.my_id] 129 self.game_map = GameMap._generate() 130 131 def ready(self, name): 132 """ 133 Indicate that your bot is ready to play. 134 :param name: The name of your bot 135 """ 136 networking.send_commands([name]) 137 138 def update_frame(self): 139 """ 140 Updates the game object's state. 141 :returns: nothing. 142 """ 143 self.turn_number = int(input()) 144 logging.info("=============== TURN {:03} ================".format(self.turn_number)) 145 146 for _ in range(len(self.players)): 147 player, num_ships, num_dropoffs, halite = map(int, input().split()) 148 self.players[player]._update(num_ships, num_dropoffs, halite) 149 150 self.game_map._update() 151 152 # Mark cells with ships as unsafe for navigation 153 for player in self.players.values(): 154 for ship in player.get_ships(): 155 self.game_map[ship.position].mark_unsafe(ship) 156 157 self.game_map[player.shipyard.position].structure = player.shipyard 158 for dropoff in player.get_dropoffs(): 159 self.game_map[dropoff.position].structure = dropoff 160 161 @staticmethod 162 def end_turn(commands): 163 """ 164 Method to send all commands to the game engine, effectively ending your turn. 165 :param commands: Array of commands to send to engine 166 :return: nothing. 167 """ 168 networking.send_commands(commands) 169 170 171 class Player: 172 """ 173 Player object containing all items/metadata pertinent to the player. 174 """ 175 def __init__(self, player_id, shipyard, halite=0): 176 self.id = player_id 177 self.shipyard = shipyard 178 self.halite_amount = halite 179 self._ships = {} 180 self._dropoffs = {} 181 182 def get_ship(self, ship_id): 183 """ 184 Returns a singular ship mapped by the ship id 185 :param ship_id: The ship id of the ship you wish to return 186 :return: the ship object. 187 """ 188 return self._ships[ship_id] 189 190 def get_ships(self): 191 """ 192 :return: Returns all ship objects in a list 193 """ 194 return self._ships.values() 195 196 def get_dropoff(self, dropoff_id): 197 """ 198 Returns a singular dropoff mapped by its id 199 :param dropoff_id: The dropoff id to return 200 :return: The dropoff object 201 """ 202 return self._dropoffs[dropoff_id] 203 204 def get_dropoffs(self): 205 """ 206 :return: Returns all dropoff objects in a list 207 """ 208 return self._dropoffs.values() 209 210 211 @staticmethod 212 def _generate(): 213 """ 214 Creates a player object from the input given by the game engine 215 :return: The player object 216 """ 217 player, shipyard_x, shipyard_y = map(int, input().split()) 218 return Player(player, Shipyard(player, -1, Position(shipyard_x, shipyard_y))) 219 220 def _update(self, num_ships, num_dropoffs, halite): 221 """ 222 Updates this player object considering the input from the game engine for the current specific turn. 223 :param num_ships: The number of ships this player has this turn 224 :param num_dropoffs: The number of dropoffs this player has this turn 225 :param halite: How much halite the player has in total 226 :return: nothing. 227 """ 228 self.halite_amount = halite 229 self._ships = {id: ship for (id, ship) in [Ship._generate(self.id) for _ in range(num_ships)]} 230 self._dropoffs = {id: dropoff for (id, dropoff) in [Dropoff._generate(self.id) for _ in range(num_dropoffs)]} 231 232 233 class MapCell: 234 """A cell on the game map.""" 235 def __init__(self, position, halite): 236 self.position = position 237 self.halite_amount = halite 238 self.ship = None 239 self.structure = None 240 241 @property 242 def is_empty(self): 243 """ 244 :return: Whether this cell has no ships or structures 245 """ 246 return self.ship is None and self.structure is None 247 248 @property 249 def is_occupied(self): 250 """ 251 :return: Whether this cell has any ships 252 """ 253 return self.ship is not None 254 255 @property 256 def has_structure(self): 257 """ 258 :return: Whether this cell has any structures 259 """ 260 return self.structure is not None 261 262 @property 263 def structure_type(self): 264 """ 265 :return: What is the structure type in this cell 266 """ 267 return None if not self.structure else type(self.structure) 268 269 def mark_unsafe(self, ship): 270 """ 271 Mark this cell as unsafe (occupied) for navigation. 272 Use in conjunction with GameMap.get_safe_move. 273 """ 274 self.ship = ship 275 276 def __eq__(self, other): 277 return self.position == other.position 278 279 def __ne__(self, other): 280 return not self.__eq__(other) 281 282 def __str__(self): 283 return 'MapCell({}, halite={})'.format(self.position, self.halite_amount) 284 285 286 class GameMap: 287 """ 288 The game map. 289 Can be indexed by a position, or by a contained entity. 290 Coordinates start at 0. Coordinates are normalized for you 291 """ 292 def __init__(self, cells, width, height): 293 self.width = width 294 self.height = height 295 self._cells = cells 296 297 def __getitem__(self, location): 298 """ 299 Getter for position object or entity objects within the game map 300 :param location: the position or entity to access in this map 301 :return: the contents housing that cell or entity 302 """ 303 if isinstance(location, Position): 304 location = self.normalize(location) 305 return self._cells[location.y][location.x] 306 elif isinstance(location, Entity): 307 return self._cells[location.position.y][location.position.x] 308 return None 309 310 def calculate_distance(self, source, target): 311 """ 312 Compute the Manhattan distance between two locations. 313 Accounts for wrap-around. 314 :param source: The source from where to calculate 315 :param target: The target to where calculate 316 :return: The distance between these items 317 """ 318 resulting_position = abs(source - target) 319 return min(resulting_position.x, self.width - resulting_position.x) + \ 320 min(resulting_position.y, self.height - resulting_position.y) 321 322 def normalize(self, position): 323 """ 324 Normalized the position within the bounds of the toroidal map. 325 i.e.: Takes a point which may or may not be within width and 326 height bounds, and places it within those bounds considering 327 wraparound. 328 :param position: A position object. 329 :return: A normalized position object fitting within the bounds of the map 330 """ 331 return Position(position.x % self.width, position.y % self.height) 332 333 @staticmethod 334 def _get_target_direction(source, target): 335 """ 336 Returns where in the cardinality spectrum the target is from source. e.g.: North, East; South, West; etc. 337 NOTE: Ignores toroid 338 :param source: The source position 339 :param target: The target position 340 :return: A tuple containing the target Direction. A tuple item (or both) could be None if within same coords 341 """ 342 return (Direction.South if target.y > source.y else Direction.North if target.y < source.y else None, 343 Direction.East if target.x > source.x else Direction.West if target.x < source.x else None) 344 345 def get_unsafe_moves(self, source, destination): 346 """ 347 Return the Direction(s) to move closer to the target point, or empty if the points are the same. 348 This move mechanic does not account for collisions. The multiple directions are if both directional movements 349 are viable. 350 :param source: The starting position 351 :param destination: The destination towards which you wish to move your object. 352 :return: A list of valid (closest) Directions towards your target. 353 """ 354 possible_moves = [] 355 distance = abs(destination - source) 356 y_cardinality, x_cardinality = self._get_target_direction(source, destination) 357 358 if distance.x != 0: 359 possible_moves.append(x_cardinality if distance.x < (self.width / 2) 360 else Direction.invert(x_cardinality)) 361 if distance.y != 0: 362 possible_moves.append(y_cardinality if distance.y < (self.height / 2) 363 else Direction.invert(y_cardinality)) 364 return possible_moves 365 366 def _bfs_traverse_safely(self, source, destination): 367 """ 368 Use a BFS to traverse the map safely, storing each previous cell in a visited cell. 369 :param source: The source object 370 :param destination: The destination object 371 :return: The visited map if reachable. None otherwise 372 """ 373 visited_map = [[None for _ in range(self.width)] for _ in range(self.height)] 374 potentials_queue = queue.Queue() 375 potentials_queue.put(source) 376 steps_taken = 0 377 while not potentials_queue.empty(): 378 current_square = potentials_queue.get() 379 if current_square == destination: 380 return visited_map 381 for suitor in current_square.position.get_surrounding_cardinals(): 382 suitor = self.normalize(suitor) 383 if not self[suitor].is_occupied and not visited_map[suitor.y][suitor.x]: 384 potentials_queue.put(self[suitor]) 385 visited_map[suitor.y][suitor.x] = current_square 386 387 steps_taken += 1 388 389 if steps_taken >= constants.MAX_BFS_STEPS: 390 break 391 392 return None 393 394 @staticmethod 395 def _find_first_move(source, destination, visited): 396 """ 397 Given a visited map, find the viable first move near the source and return it 398 :param source: The first position 399 :param destination: The target 400 :param visited: A map containing the visited cell information from _bfs_traverse_safely 401 :return: The first viable move 402 """ 403 current_square = destination 404 previous = None 405 while current_square is not None and current_square != source: 406 previous = current_square 407 current_square = visited[current_square.position.y][current_square.position.x] 408 return previous 409 410 def _naive_navigate(self, source, destination): 411 """ 412 Returns a singular safe move towards the destination. 413 :param source: Starting position 414 :param destination: Ending position 415 :return: A direction, or None if no such move exists. 416 """ 417 for direction in self.get_unsafe_moves(source, destination): 418 target_pos = source.directional_offset(direction) 419 if not self[target_pos].is_occupied: 420 return direction 421 422 return None 423 424 def get_safe_move(self, source, destination): 425 """ 426 Returns the best (read: most optimal) singular safe move 427 towards the destination. 428 :param source: The source MapCell that you wish to move 429 :param destination: The destination MapCell towards which you 430 wish to move your object. 431 :return: A single valid direction towards the destination 432 accounting for collisions, or None if no such move exists. 433 """ 434 if not isinstance(source, MapCell) or not isinstance(destination, MapCell): 435 raise AttributeError("Source and Destination must be of type MapCell") 436 437 if source == destination: 438 return None 439 440 visited_map = self._bfs_traverse_safely(source, destination) 441 if not visited_map: 442 return self._naive_navigate(source.position, destination.position) 443 444 safe_target_cell = self._find_first_move(source, destination, visited_map) 445 if not safe_target_cell: 446 return None 447 448 potential_moves = self.get_unsafe_moves(source.position, safe_target_cell.position) 449 if not potential_moves: 450 return None 451 452 return potential_moves[0] 453 454 @staticmethod 455 def _generate(): 456 """ 457 Creates a map object from the input given by the game engine 458 :return: The map object 459 """ 460 map_width, map_height = map(int, input().split()) 461 game_map = [[None for _ in range(map_width)] for _ in range(map_height)] 462 for y_position in range(map_height): 463 cells = input().split() 464 for x_position in range(map_width): 465 game_map[y_position][x_position] = MapCell(Position(x_position, y_position), 466 int(cells[x_position])) 467 return GameMap(game_map, map_width, map_height) 468 469 def _update(self): 470 """ 471 Updates this map object from the input given by the game engine 472 :return: nothing 473 """ 474 # Mark cells as safe for navigation (will re-mark unsafe cells 475 # later) 476 for y in range(self.height): 477 for x in range(self.width): 478 self[Position(x, y)].ship = None 479 480 for _ in range(int(input())): 481 cell_x, cell_y, cell_energy = map(int, input().split()) 482 self[Position(cell_x, cell_y)].halite_amount = cell_energy