text: /**
  * Copyright (c) 2017-present, Facebook, Inc.
  * All rights reserved.
  *
  * This source code is licensed under the BSD-style license found in the
  * LICENSE file in the root directory of this source tree. An additional grant
  * of patent rights can be found in the PATENTS file in the same directory.
  */
  
  #include "map.h"
  #include "time.h"
  
  // Constructor
  RTSMap::RTSMap() {
      load_default_map();
      reset_intermediates();
  }
  
  bool RTSMap::find_two_nearby_empty_slots(const std::function<uint16_t(int)>& f, int *x1, int *y1, int *x2, int *y2, int i) const {
      const int kDist = 4;
      int kMaxTrial = 100;
      for (int j = 0; j < kMaxTrial; ++j) {
          *x1 = float(f(GetXSize())) / 3 + i * float(GetXSize()) / 3 * 2;
          *y1 = float(f(GetYSize())) / 3 + i * float(GetYSize()) / 3 * 2;
          if (! CanPass(Coord(*x1, *y1), INVALID)) continue;
  
          *x2 = f(2 * kDist + 1) - kDist + *x1;
          *y2 = f(2 * kDist + 1) - kDist + *y1;
          if (CanPass(Coord(*x2, *y2), INVALID) && ((*x1 != *x2) || (*y1 != *y2))) return true;
      }
      return false;
  }
  
  bool RTSMap::GenerateImpassable(const std::function<uint16_t(int)>& f, int nImpassable) {
      _map.assign(_m * _n * _level, MapSlot());
      for (int i = 0; i < nImpassable; ++i) {
          const int x = f(_m);
          const int y = f(_n);
          _map[GetLoc(Coord(x, y))].type = IMPASSABLE;
      }
      return true;
  }
  
  bool RTSMap::GenerateTDMaze(const std::function<uint16_t(int)>& f) {
      const int blank = 3;
      int m = _m / 2;
      int n = _n / 2;
      _map.assign(_m * _n * _level, MapSlot());
      for (int x = 0; x < _m; x++) {
          for (int y = 0; y < _n; y++) {
          if ((x < _m - blank * 2) || (y < _n - blank * 2))
              _map[GetLoc(Coord(x, y))].type = IMPASSABLE;
          }
      }
      int maze[m * n];
      for (int i = 0; i < m * n; i++) {
          maze[i] = 0;
      }
      vector<int> current;
      // base
      // wave starting area
      for (int x = m - blank; x < m ; x++) {
          for (int y = n - blank; y < n; y++) {
              maze[x * m + y] = 1;
              if ((x == m - blank) || (y == n - blank)) current.push_back(x * m + y);
          }
      }
      int dx[] = { 1, 0, -1, 0 };
      int dy[] = { 0, 1, 0, -1 };
      vector<int> next;
      vector<int> previous;
      for (int c : current) {
          for (size_t i = 0; i < sizeof(dx) / sizeof(int); ++i) {
              int xn = c / m + dx[i];
              int yn = c % m + dy[i];
              if ((xn < 0) || (xn >= m) || (yn < 0) || (yn >= n) || (maze[xn * m + yn] == 1)) continue;
              next.push_back(xn * m + yn);
              previous.push_back(i);
          }
      }
  
      //91 slots to be filled
      int iter = 0;
      while (iter < m * n - blank * blank) {
          int next_size = next.size();
          int rd = f(next_size);
          int curr = next[rd];
          int coming_from = previous[rd];
          next.erase(next.begin() + rd);
          previous.erase(previous.begin() + rd);
          if (maze[curr] == 1) {
              continue;
          }
          iter ++;
          maze[curr] = 1;
          int xc = curr / m;
          int yc = curr % m;
          _map[GetLoc(Coord(xc * 2, yc * 2))].type = NORMAL;
          _map[GetLoc(Coord(xc * 2 - dx[coming_from], yc * 2 - dy[coming_from]))].type = NORMAL;
          for (size_t i = 0; i < sizeof(dx) / sizeof(int); ++i) {
              int xn = xc + dx[i];
              int yn = yc + dy[i];
              if ((xn < 0) || (xn >= m) || (yn < 0) || (yn >= n) || (maze[xn * m + yn] == 1)) continue;
              next.push_back(xn * m + yn);
              previous.push_back(i);
          }
      }
      return true;
  }
  
  bool RTSMap::GenerateMap(const std::function<uint16_t(int)>& f, int nImpassable, int num_player, int init_resource) {
      // load a map for now simple format.
      bool success;
      do {
          success = true;
          GenerateImpassable(f, nImpassable);
          int x1, y1, x2, y2;
          _infos.clear();
          for (PlayerId i = 0; i < num_player; ++i) {
              if (! find_two_nearby_empty_slots(f, &x1, &y1, &x2, &y2, i)) {
                  cout << "player " << i << " (" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << ") failed" << endl;
                  success = false;
                  break;
              }
              PlayerMapInfo info;
              info.player_id = i;
              info.base_coord = Coord(x1, y1);
              info.resource_coord = Coord(x2, y2);
              info.initial_resource = init_resource;
              _infos.emplace_back(info);
              // cout << "Player " << i << ": BASE: (" << x1 << ", " << y1 << ") RESOURCE: (" << x2 << ", " << y2 << ")" << endl;
          }
      } while(! success);
  
      reset_intermediates();
      return true;
  }
  
  void RTSMap::reset_intermediates() {
      // Locality Search
      _locality = LocalitySearch<UnitId>(PointF(-0.5, -0.5), PointF(_m + 0.5, _n + 0.5));
  
      // Precompute map structure.
      precompute_all_pair_distances();
  }
  
  void RTSMap::load_default_map() {
      _m = 20;
      _n = 20;
      _level = 1;
      _map.assign(_m * _n * _level, MapSlot());
  }
  
  void RTSMap::precompute_all_pair_distances() {
      // All-pair shortest distance for path-planning.
      // Floyd–Warshall algorithm O(V^3) = O(m^3n^3)
      // Not extremely fast, but since it is only computed
      // once for each map, we could just use it.
  }
  
  bool RTSMap::AddUnit(const UnitId &id, const PointF& new_p) {
      if (_locality.Exists(id)) return false;
      if (! _locality.IsEmpty(new_p, kUnitRadius, INVALID)) return false;
  
      _locality.Add(id, new_p, kUnitRadius);
      return true;
  }
  
  bool RTSMap::MoveUnit(const UnitId &id, const PointF& new_p) {
      if (! _locality.Exists(id)) return false;
      if (! _locality.IsEmpty(new_p, kUnitRadius, id)) return false;
  
      _locality.Remove(id);
      _locality.Add(id, new_p, kUnitRadius);
      return true;
  }
  
  bool RTSMap::RemoveUnit(const UnitId &id) {
      if (! _locality.Exists(id)) return false;
      _locality.Remove(id);
      return true;
  }
  
  UnitId RTSMap::GetClosestUnitId(const PointF& p, float max_r) const {
      float dist_sqr;
      const UnitId *res = _locality.Loc2Key(p, &dist_sqr);
      if (res == nullptr || dist_sqr >= max_r * max_r ) return INVALID;
      return *res;
  }
  
  set<UnitId> RTSMap::GetUnitIdInRegion(const PointF &left_top, const PointF &right_bottom) const {
      return _locality.KeysInRegion(left_top, right_bottom);
  }
  
  vector<Loc> RTSMap::GetSight(const Loc& loc, int range) const {
      Coord c = GetCoord(loc);
      vector<Loc> res;
  
      const int xmin = std::max(0, c.x - range);
      const int xmax = std::min(_m - 1, c.x + range);
  
      for (int x = xmin; x <= xmax; ++x) {
          const int yrange = range - std::abs(c.x  - x);
          const int ymin = std::max(0, c.y - yrange);
          const int ymax = std::min(_n - 1, c.y + yrange);
          for (int y = ymin; y <= ymax; ++y) {
              res.push_back(GetLoc(x, y));
          }
      }
      return res;
  }
  
  string RTSMap::PrintCoord(Loc loc) const {
      // Print the coordinate.
      Coord coord = GetCoord(loc);
  
      stringstream ss;
      ss << "(" << coord.x << "," << coord.y << "," << coord.z << ")";
      return ss.str();
  }
  
  Coord RTSMap::GetCoord(Loc loc) const {
      int xy = loc % (_m * _n);
      int z = loc / (_m * _n);
      return Coord(xy % _m,  xy / _m, z);
  }
  
  Loc RTSMap::GetLoc(int x, int y, int z) const {
      return (z * _n + y) * _m + x;
  }
  
  Loc RTSMap::GetLoc(const Coord &c) const {
      return GetLoc(c.x, c.y, c.z);
  }
  
  // Draw the map
  string RTSMap::Draw() const {
      stringstream ss;
      ss << "m " << _m << " " << _n << " " << endl;
      for (int j = 0; j < _n; ++j) {
          for (int i = 0; i < _m; ++i) {
              // Draw the map (only level 0)
              Loc loc = GetLoc(i, j, 0);
              ss << _map[loc].type << " ";
          }
          ss << endl;
      }
      return ss.str();
  }
  
  string RTSMap::PrintDebugInfo() const {
      return _locality.PrintDebugInfo();
  }
  