1  package hlt;
  2  
  3  import java.util.ArrayList;
  4  
  5  public class GameMap {
  6      public final int width;
  7      public final int height;
  8      private final MapCell[][] cells;
  9      private int totalHalite;
 10  
 11      private GameMap(final int width, final int height) {
 12          this.width = width;
 13          this.height = height;
 14  
 15          cells = new MapCell[height][];
 16          for (int y = 0; y < height; ++y) {
 17              cells[y] = new MapCell[width];
 18          }
 19      }
 20  
 21      public MapCell at(final Position position) {
 22          final Position normalized = normalize(position);
 23          return cells[normalized.y][normalized.x];
 24      }
 25  
 26      public MapCell at(final Entity entity) {
 27          return at(entity.position);
 28      }
 29  
 30      public int calculateDistance(final Position source, final Position target) {
 31          final Position normalizedSource = normalize(source);
 32          final Position normalizedTarget = normalize(target);
 33  
 34          final int dx = Math.abs(normalizedSource.x - normalizedTarget.x);
 35          final int dy = Math.abs(normalizedSource.y - normalizedTarget.y);
 36  
 37          final int toroidal_dx = Math.min(dx, width - dx);
 38          final int toroidal_dy = Math.min(dy, height - dy);
 39  
 40          return toroidal_dx + toroidal_dy;
 41      }
 42  
 43      public Position normalize(final Position position) {
 44          final int x = ((position.x % width) + width) % width;
 45          final int y = ((position.y % height) + height) % height;
 46          return new Position(x, y);
 47      }
 48  
 49      public ArrayList<Direction> getUnsafeMoves(final Position source, final Position destination) {
 50          final ArrayList<Direction> possibleMoves = new ArrayList<>();
 51  
 52          final Position normalizedSource = normalize(source);
 53          final Position normalizedDestination = normalize(destination);
 54  
 55          final int dx = Math.abs(normalizedSource.x - normalizedDestination.x);
 56          final int dy = Math.abs(normalizedSource.y - normalizedDestination.y);
 57          final int wrapped_dx = width - dx;
 58          final int wrapped_dy = height - dy;
 59  
 60          if (normalizedSource.x < normalizedDestination.x) {
 61              possibleMoves.add(dx > wrapped_dx ? Direction.WEST : Direction.EAST);
 62          } else if (normalizedSource.x > normalizedDestination.x) {
 63              possibleMoves.add(dx < wrapped_dx ? Direction.WEST : Direction.EAST);
 64          }
 65  
 66          if (normalizedSource.y < normalizedDestination.y) {
 67              possibleMoves.add(dy > wrapped_dy ? Direction.NORTH : Direction.SOUTH);
 68          } else if (normalizedSource.y > normalizedDestination.y) {
 69              possibleMoves.add(dy < wrapped_dy ? Direction.NORTH : Direction.SOUTH);
 70          }
 71  
 72          return possibleMoves;
 73      }
 74  
 75      /**
 76       * @return An ArrayList of normalized unsafe positions adjacent to source by which to reach destination
 77       */
 78      public ArrayList<Position> getUnsafePositions(final Position source, final Position destination){
 79          final ArrayList<Position> possiblePositions = new ArrayList<>();
 80          for (Direction direction : getUnsafeMoves(source, destination)){
 81              possiblePositions.add(normalize(source.directionalOffset(direction)));
 82          }
 83          return possiblePositions;
 84      }
 85  
 86      /**
 87       * @param minimizeCost Whether to seek the lower halite cell (smaller cost next turn)
 88       */
 89      public Direction naiveNavigate(final Ship ship, final Position destination, boolean minimizeCost) {
 90          if (minimizeCost) return lowCostNavigate(ship, destination);
 91  
 92          // getUnsafeMoves normalizes for us
 93          for (final Direction direction : getUnsafeMoves(ship.position, destination)) {
 94              final Position targetPos = ship.position.directionalOffset(direction);
 95              if (!at(targetPos).isOccupied()) {
 96                  at(targetPos).markUnsafe(ship);
 97                  return direction;
 98              }
 99          }
100  
101          return Direction.STILL;
102      }
103  
104      /**
105       * Seek adjacent cell with less halite (smaller cost next turn)
106       */
107      private Direction lowCostNavigate(final Ship ship, final Position destination) {
108          Direction targetDir = Direction.STILL;
109          Position targetPos = null;
110  
111          // getUnsafeMoves normalizes for us
112          for (final Direction direction : getUnsafeMoves(ship.position, destination)) {
113              final Position adjacentPos = ship.position.directionalOffset(direction);
114              if (!at(adjacentPos).isOccupied() && (targetPos == null || at(targetPos).halite > at(adjacentPos).halite)){
115                  targetDir = direction;
116                  targetPos = adjacentPos;
117              }
118          }
119          if (targetPos != null) at(targetPos).markUnsafe(ship);
120          return targetDir;
121      }
122  
123      /**
124       * @return Whether ship has enough halite to move
125       */
126      public boolean canMove(Ship ship){
127          return ship.getHalite() >= Math.ceil(at(ship).halite * (1.0 / Constants.MOVE_COST_RATIO));
128      }
129  
130      /**
131       * @return True if 'positionA' and 'positionB' are adjacent
132       */
133      public boolean areAdjacent(Position positionA, Position positionB){
134          return calculateDistance(positionA, positionB) == 1;
135      }
136  
137      /**
138       * @return The position in 'positions' closest to origin
139       */
140      public Position closest(Position origin, ArrayList<Position> positions){
141          if (positions == null || positions.isEmpty()){
142              return null;
143          }
144          Position closest = positions.get(0);
145          for (Position position : positions){
146              if (calculateDistance(position, origin) < calculateDistance(closest, origin)){
147                  closest = position;
148              }
149          }
150          return closest;
151      }
152  
153      /**
154       * @return The closest map cell to origin within distance that has at least halite halite
155       * Returns null if no such cell exists
156       */
157      public MapCell nearestCellWithHalite(Position origin, int distance, int halite){
158          Ripple ripple = new Ripple(this, origin, distance);
159          while (ripple.hasNext()){
160              Position next = ripple.next();
161              if (at(next).halite >= halite){
162                  return at(next);
163              }
164          }
165          return null;
166      }
167  
168      /**
169       * @return The map cell with the most halite within distance of origin
170       */
171      public MapCell densestCell(Position origin, int distance){
172          Ripple ripple = new Ripple(this, origin, distance);
173          MapCell best = at(origin);
174          while (ripple.hasNext()){
175              Position next = ripple.next();
176              if (at(next).halite > best.halite){
177                  best = at(next);
178              }
179          }
180          return best;
181      }
182  
183      /**
184       * @return A list of ships within distance of origin
185       */
186      public ArrayList<Ship> shipsInRadius(Position origin, int distance){
187          Ripple ripple = new Ripple(this, origin, distance);
188          ArrayList<Ship> ships = new ArrayList<Ship>();
189          while (ripple.hasNext()){
190              MapCell cell = at(ripple.next());
191              if (cell.isOccupied()){
192                  ships.add(cell.ship);
193              }
194          }
195          return ships;
196      }
197  
198      /**
199       * @return The total amount of halite within distance of origin
200       */
201      public int haliteWithinDistance(Position origin, int distance){
202          Ripple ripple = new Ripple(this, origin, distance);
203          int totalHalite = 0;
204          while (ripple.hasNext()){
205              totalHalite += at(ripple.next()).halite;
206          }
207          return totalHalite;
208      }
209  
210      /**
211       * @return The position of player's closet dropoff to origin
212       * The player's shipyard is considered a valid dropoff
213       */
214      public Position closestDropoff(Player player, Position origin){
215          Position closest = player.shipyard.position;
216          for (Dropoff dropoff : player.dropoffs.values()){
217              if (calculateDistance(dropoff.position, origin) < calculateDistance(closest, origin)){
218                  closest = dropoff.position;
219              }
220          }
221          return closest;
222      }
223  
224      /**
225       * @return The total amount of halite on the map
226       */
227      public int getTotalHalite(){
228          return totalHalite;
229      }
230  
231      /**
232       * Update the average halite on the map once per turn
233       */
234      void updateTotalHalite(){
235          int total = 0;
236          for (MapCell[] row : cells){
237              for (MapCell cell : row){
238                  total += cell.halite;
239              }
240          }
241          totalHalite = total;
242      }
243  
244      /**
245       * @return The average amount of halite on the map
246       */
247      public double getAverageHalite(){
248          return totalHalite / (double)(width * height);
249      }
250  
251      /**
252       * WARNING: Run this method sparingly
253       *
254       * @return List of positions with halite amount >= 'halite'
255       */
256      public ArrayList<Position> getPositionsAbove(int halite){
257          ArrayList<Position> heavyCells = new ArrayList<>();
258          for (MapCell[] row : cells){
259              for (MapCell cell : row){
260                  if (cell.halite >= halite){
261                      heavyCells.add(cell.position);
262                  }
263              }
264          }
265          return heavyCells;
266      }
267  
268      void _update() {
269          for (int y = 0; y < height; ++y) {
270              for (int x = 0; x < width; ++x) {
271                  cells[y][x].ship = null;
272              }
273          }
274  
275          final int updateCount = Input.readInput().getInt();
276  
277          for (int i = 0; i < updateCount; ++i) {
278              final Input input = Input.readInput();
279              final int x = input.getInt();
280              final int y = input.getInt();
281  
282              cells[y][x].halite = input.getInt();
283          }
284      }
285  
286      static GameMap _generate() {
287          final Input mapInput = Input.readInput();
288          final int width = mapInput.getInt();
289          final int height = mapInput.getInt();
290  
291          final GameMap map = new GameMap(width, height);
292  
293          for (int y = 0; y < height; ++y) {
294              final Input rowInput = Input.readInput();
295  
296              for (int x = 0; x < width; ++x) {
297                  final int halite = rowInput.getInt();
298                  map.cells[y][x] = new MapCell(new Position(x, y), halite);
299              }
300          }
301  
302          map.updateTotalHalite();
303  
304          return map;
305      }
306  }