// Snake: L = turn left, R = turn right (from the snake's point of view). Eat, grow, do not hit the wall or yourself.
// The Nano has 2 KB of RAM, so the body is not a list of cells: a bitmap says which cells are taken
// and a ring of 2-bit steps remembers the way from the tail to the head.
#pragma once

const uint8_t SNAKE_W = 32;
const uint8_t SNAKE_H = 14;
const uint16_t SNAKE_CELLS = SNAKE_W * SNAKE_H;
const int8_t STEP_X[4] = {1, 0, -1, 0};      // 0 right, 1 down, 2 left, 3 up
const int8_t STEP_Y[4] = {0, 1, 0, -1};

struct SnakeState {
  uint8_t taken[SNAKE_CELLS / 8];
  uint8_t steps[SNAKE_CELLS / 4];
  uint16_t first, len;                       // ring: steps[first .. first + len - 1]
  uint8_t head_x, head_y, tail_x, tail_y, food_x, food_y, dir, wait, pending;
  bool turned;
};

bool snake_taken(SnakeState &g, uint8_t x, uint8_t y) {
  uint16_t i = y * SNAKE_W + x;
  return g.taken[i / 8] & (1 << (i % 8));
}

void snake_mark(SnakeState &g, uint8_t x, uint8_t y, bool on) {
  uint16_t i = y * SNAKE_W + x;

  if (on) {
    g.taken[i / 8] |= 1 << (i % 8);
  } else {
    g.taken[i / 8] &= ~(1 << (i % 8));
  }
}

uint8_t snake_step(SnakeState &g, uint16_t n) {
  uint16_t i = (g.first + n) % SNAKE_CELLS;
  return (g.steps[i / 4] >> ((i % 4) * 2)) & 3;
}

void snake_push(SnakeState &g, uint8_t d) {
  uint16_t i = (g.first + g.len) % SNAKE_CELLS;
  g.steps[i / 4] = (g.steps[i / 4] & ~(3 << ((i % 4) * 2))) | (d << ((i % 4) * 2));
  g.len++;
}

void snake_food(SnakeState &g) {
  do {
    g.food_x = random(SNAKE_W);
    g.food_y = random(SNAKE_H);
  } while (snake_taken(g, g.food_x, g.food_y));
}

void snake_init(SnakeState &g) {
  memset(&g, 0, sizeof g);
  g.tail_x = 10;
  g.tail_y = 7;
  g.head_x = 12;
  g.head_y = 7;

  for (uint8_t x = 10; x <= 12; x++) {
    snake_mark(g, x, 7, true);
  }

  snake_push(g, 0);
  snake_push(g, 0);
  snake_food(g);
}

void snake_update(SnakeState &g) {
  // one turn per step: a second quick tap waits for the next step, so two taps never turn the snake into itself
  for (uint8_t k = KEY_L; k <= KEY_R; k += 2) {
    if (!key_tap[k]) {
      continue;
    }

    uint8_t turn = k == KEY_L ? 3 : 1;

    if (!g.turned) {
      g.dir = (g.dir + turn) % 4;
      g.turned = true;
    } else {
      g.pending = turn;
    }
  }

  uint8_t delay_frames = score < 20 ? 5 - score / 10 : 3;

  if (++g.wait < delay_frames) {
    return;
  }

  g.wait = 0;
  g.turned = false;
  int8_t nx = g.head_x + STEP_X[g.dir];
  int8_t ny = g.head_y + STEP_Y[g.dir];
  bool eat = nx == g.food_x && ny == g.food_y;

  if (!eat) {
    snake_mark(g, g.tail_x, g.tail_y, false);
    uint8_t d = snake_step(g, 0);
    g.tail_x += STEP_X[d];
    g.tail_y += STEP_Y[d];
    g.first = (g.first + 1) % SNAKE_CELLS;
    g.len--;
  }

  if (nx < 0 || ny < 0 || nx >= SNAKE_W || ny >= SNAKE_H || snake_taken(g, nx, ny)) {
    end_game();
    return;
  }

  snake_push(g, g.dir);
  g.head_x = nx;
  g.head_y = ny;
  snake_mark(g, nx, ny, true);

  if (g.pending) {                           // the queued second turn, now that the first one has made a step
    g.dir = (g.dir + g.pending) % 4;
    g.pending = 0;
    g.turned = true;
  }

  if (eat) {
    score++;

    if (g.len + 2 < SNAKE_CELLS) {
      snake_food(g);
    } else {
      end_game();
    }
  }
}

void snake_draw(SnakeState &g) {
  oled.setFont(u8g2_font_5x7_tr);
  oled.drawStr(1, 7, "SNAKE");
  oled.drawStr(60, 7, "HI");
  draw_number(best, 90, 7, true);
  draw_number(score, 127, 7, true);
  oled.drawFrame(0, 8, 128, 56);

  for (uint8_t y = 0; y < SNAKE_H; y++) {
    for (uint8_t x = 0; x < SNAKE_W; x++) {
      if (snake_taken(g, x, y)) {
        box(x * 4, 8 + y * 4, 3, 3);
      }
    }
  }

  box(g.head_x * 4, 8 + g.head_y * 4, 4, 4);
  box(g.food_x * 4 + 1, 8 + g.food_y * 4, 2, 4);
  box(g.food_x * 4, 9 + g.food_y * 4, 4, 2);
}