#include "Player.hh"

#define PLAYER_NAME Felix1

using namespace std;

struct PLAYER_NAME : public Player {
  static Player* factory() {
    return new PLAYER_NAME;
  }

  vector<vector<bool> > claimed;
  vector<vector<bool> > danger;

  virtual void play() {
    int h = number_rows();
    int w = number_universe_columns();
    claimed = vector<vector<bool> >(h, vector<bool>(w, false));
    danger = vector<vector<bool> >(h, vector<bool>(w, false));

    // initialize danger matrix
    vector<Dir> dirs = all_directions();
    for (int y = 0; y < h; ++y) {
      for (int x = 0; x < w; ++x) {
        Pos cur_p = {y, x};
        Cell cur_cell = cell(cur_p);
        if (cur_cell.type == CAR) {
          int owner = player_of(cur_cell.cid);
          if (owner != me()) {
            // mark cells covered by movement
            for (Dir dir : dirs) {
              if (within_universe(cur_p + dir)) {
                mark_danger(cur_p, dir);
              }
            }

            Car s = car(cur_cell.cid);
            if (s.nb_miss > 0) {
              // mark cells covered by missile shooting
              mark_danger(cur_p, {0, 4});
            }
          }
        }
      }
    }

    for (int cid = begin(me()); cid < end(me()); ++cid) {
      Car s = car(cid);
      control_car(s);
    }
  }

  vector<Dir> all_directions() {
    vector<Dir> dirs;
    for (int dx = 0; dx <= 2; ++dx) {
      for (int dy = -1; dy <= 1; ++dy) {
        dirs.emplace_back(Dir{dy, dx});
      }
    }
    return dirs;
  }

  void bfs(Pos p, vector<vector<int> >& dist, vector<vector<Dir> >& ldir) {
    p = normalize_pos(p);

    int h = number_rows();
    int w = number_universe_columns();
    dist = vector<vector<int> >(h, vector<int>(w, -1));
    ldir = vector<vector<Dir> >(h, vector<Dir>(w));
    queue<Pos> q;

    int y0 = first(p);
    int x0 = second(p);
    dist[y0][x0] = 0;
    q.push(p);
    while (!q.empty()) {
      Pos p = q.front();
      q.pop();

      vector<Dir> dirs = all_directions();
      for (Dir dir : dirs) {
        Pos np = normalize_pos(p + dir);
        if (!within_universe(np)) continue;

        int y = first(p);
        int x = second(p);
        if (!within_window(np, round() + dist[y][x] + 1)) continue;

        int ny = first(np);
        int nx = second(np);
        if (dist[ny][nx] != -1) continue;

        if (!is_safe_move(p, dir, round() + dist[y][x])) continue;

        dist[ny][nx] = dist[y][x] + 1;
        ldir[ny][nx] = dir;
        q.push(np);
      }
    }
  }

  void control_car(const Car& c) {
    if (!c.alive) return;

    if (should_shoot(c) && c.nb_miss > 0) {
      shoot(c.cid);
      mark_danger(normalize_pos(c.pos), {0, 4});
      return;
    }

    // compute shortest path to every cell
    vector<vector<int> > dist;
    vector<vector<Dir> > ldir;
    Pos p0 = normalize_pos(c.pos);
    bfs(p0, dist, ldir);

    
    int best_dist = -1;
    Pos best;
    int h = number_rows();
    int w = number_universe_columns();

    // get nearest point bonus
    if (c.gas < 40) { // Look for gas
      for (int y = 0; y < h; ++y) {
	for (int x = 0; x < w; ++x) {
	  if (dist[y][x] == -1) continue;
	  
	  if (claimed[y][x]) continue;
	  
	  Pos cur = {y, x};
	  if (cell(cur).type != GAS_BONUS) continue;
	  
	  if (best_dist == -1 ||
	      dist[y][x] < best_dist ||
	      (dist[y][x] == best_dist &&
	       second(normalize_pos(cur - p0)) < second(normalize_pos(best - p0)))) {
	    best_dist = dist[y][x];
	    best = cur;
	  }
	}
      }      
    }
    

    // get nearest point bonus
    if (best_dist == -1) {
      for (int y = 0; y < h; ++y) {
	for (int x = 0; x < w; ++x) {
	  if (dist[y][x] == -1) continue;
	  
	  if (claimed[y][x]) continue;
	  
	  Pos cur = {y, x};
	  if (cell(cur).type != WATER_BONUS) continue;
	  
	  if (best_dist == -1 ||
	      dist[y][x] < best_dist ||
	      (dist[y][x] == best_dist &&
	       second(normalize_pos(cur - p0)) < second(normalize_pos(best - p0)))) {
	    best_dist = dist[y][x];
	    best = cur;
	  }
	}
      }
    }

    // either get ammo or go hunting
    if (best_dist == -1) {
      // get nearest missile bonus
      for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
          if (dist[y][x] == -1) continue;

          if (claimed[y][x]) continue;

          Pos cur = {y, x};
          if (cell(cur).type != MISSILE_BONUS) continue;

          if (best_dist == -1 ||
              dist[y][x] < best_dist ||
              (dist[y][x] == best_dist &&
               second(normalize_pos(cur - p0)) < second(normalize_pos(best - p0)))) {
            best_dist = dist[y][x];
            best = cur;
          }
        }
      }

      if (best_dist == -1 || c.nb_miss > 3) {
        // get behind enemy car
        for (int y = 0; y < h; ++y) {
          for (int x = 0; x < w; ++x) {
            if (dist[y][x] == -1) continue;

            if (claimed[y][x]) continue;

            Cell target_cell = cell({y, x + 2});
            if (target_cell.type != CAR) continue;
            if (player_of(target_cell.cid) == me()) continue;

            Pos cur = {y, x};
            if (best_dist == -1 ||
                dist[y][x] < best_dist ||
                (dist[y][x] == best_dist &&
                 second(normalize_pos(cur - p0)) < second(normalize_pos(best - p0)))) {
              best_dist = dist[y][x];
              best = cur;
            }
          }
        }
      }
    }

    if (best_dist == -1) {
      // shoot to clear the way (or be idle)
      bool shoot_to_clear = true;
      for (int right = 1; right < w; ++right) {
        Cell cur_cell = cell(p0 + Dir{0, right});
        if (cur_cell.type == MISSILE ||
            (cur_cell.type == CAR && player_of(cur_cell.cid) == me())) {
          shoot_to_clear = false;
        }

        if (cur_cell.type != EMPTY) break;
      }

      if (shoot_to_clear && c.nb_miss > 0) {
        shoot(c.cid);
        mark_danger(normalize_pos(c.pos), {0, 4});
      } else {
        mark_danger(normalize_pos(c.pos), DEFAULT);
      }
    } else {
      // perform the first step in the path
      Dir dir;
      for (Pos p = best; p != p0;) {
        int y = first(p);
        int x = second(p);
        dir = ldir[y][x];
        p = normalize_pos(p - dir);
      }

      claimed[first(best)][second(best)] = true;
      mark_danger(normalize_pos(c.pos), dir);
      move(c.cid, dir);
    }
  }

  bool is_safe_move(Pos p, Dir dir, int r) {
    p = normalize_pos(p);

    int y0 = min(first(p), first(p + dir));
    int y1 = max(first(p), first(p + dir));
    int x0 = min(second(p), second(p + dir));
    int x1 = max(second(p), second(p + dir));
    for (int y = y0; y <= y1; ++y) {
      for (int x = x0; x <= x1; ++x) {
        Pos cur_p = normalize_pos({y, x});
        if (cur_p == p) continue;

        // check for collision with non-missile object
        CType type = cell(cur_p).type;
        if (type != EMPTY &&
            type != MISSILE &&  // the missile will be gone before the car moves
            type != MISSILE_BONUS &&
            type != WATER_BONUS &&
	    type != GAS_BONUS &&
            (r == round() || type != CAR)) {
          return false;
        }

        if (r == round() && danger[first(cur_p)][second(cur_p)]) {
          return false;
        }

        // check for collision with missile
        for (int left = 0; left <= 2; ++left) {
          Dir miss_dir = {0, 2 * (1 + r - round()) + left};
          Cell left_cell = cell(normalize_pos(cur_p - miss_dir));
          if (left_cell.type == MISSILE) {
            return false;
          }
        }
      }
    }

    return true;
  }

  void mark_danger(Pos p, Dir dir) {
    p = normalize_pos(p);

    int y0 = min(first(p), first(p + dir));
    int y1 = max(first(p), first(p + dir));
    int x0 = min(second(p), second(p + dir));
    int x1 = max(second(p), second(p + dir));
    for (int y = y0; y <= y1; ++y) {
      for (int x = x0; x <= x1; ++x) {
        Pos cur_p = normalize_pos({y, x});
        danger[first(cur_p)][second(cur_p)] = true;
      }
    }
  }

  Pos normalize_pos(Pos p) {
    int y = first(p);
    int x = second(p);
    int w = number_universe_columns();
    return {y, ((x % w) + w) % w};
  }

  bool should_shoot(const Car& s) {
    Pos p = normalize_pos(s.pos);
    for (int right = 1; right <= 4; ++right) {
      Cell cur_cell = cell(p + Dir{0, right});
      if (cur_cell.type == CAR && player_of(cur_cell.cid) != me()) {
        return true;
      }

      if (cur_cell.type != EMPTY) break;
    }

    return false;
  }
};

RegisterPlayer(PLAYER_NAME);

