#include <iostream>
#include <vector>
#include <deque>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <chrono>
#include <thread>
#include <conio.h>

// Game constants
constexpr int BOARD_WIDTH = 20;
constexpr int BOARD_HEIGHT = 15;
constexpr char WALL = '#';
constexpr char SNAKE_BODY = 'o';
constexpr char SNAKE_HEAD = 'O';
constexpr char FOOD = '*';
constexpr char EMPTY = ' ';

// Directions
enum class Direction { UP, DOWN, LEFT, RIGHT };

struct Position {
    int x, y;
    bool operator==(const Position& other) const {
        return x == other.x && y == other.y;
    }
};

struct GameState {
    std::deque<Position> snake;
    Position food;
    Direction dir;
    Direction next_dir;
    int score;
    bool game_over;
    bool paused;
};

char board[BOARD_HEIGHT][BOARD_WIDTH + 1];

void place_food(GameState& state);

void init_board() {
    for (int y = 0; y < BOARD_HEIGHT; y++) {
        for (int x = 0; x < BOARD_WIDTH; x++) {
            if (y == 0 || y == BOARD_HEIGHT - 1 || x == 0 || x == BOARD_WIDTH - 1) {
                board[y][x] = WALL;
            } else {
                board[y][x] = EMPTY;
            }
        }
        board[y][BOARD_WIDTH] = '\0';
    }
}

void init_game(GameState& state) {
    Position head = {BOARD_WIDTH / 2, BOARD_HEIGHT / 2};
    state.snake = {head, {head.x - 1, head.y}, {head.x - 2, head.y}};
    state.dir = Direction::RIGHT;
    state.next_dir = Direction::RIGHT;
    state.score = 0;
    state.game_over = false;
    state.paused = false;
    place_food(state);
}

void place_food(GameState& state) {
    Position pos;
    bool on_snake;
    do {
        on_snake = false;
        pos.x = 1 + std::rand() % (BOARD_WIDTH - 2);
        pos.y = 1 + std::rand() % (BOARD_HEIGHT - 2);
        for (const auto& segment : state.snake) {
            if (segment == pos) {
                on_snake = true;
                break;
            }
        }
    } while (on_snake);
    state.food = pos;
}

void render(const GameState& state) {
    system("cls");  // Windows clear screen
    
    init_board();
    
    board[state.food.y][state.food.x] = FOOD;
    
    for (size_t i = 0; i < state.snake.size(); i++) {
        const auto& segment = state.snake[i];
        board[segment.y][segment.x] = (i == 0) ? SNAKE_HEAD : SNAKE_BODY;
    }
    
    std::cout << "=== SNAKE GAME ===\n";
    std::cout << "Score: " << state.score << "\n";
    std::cout << "Controls: WASD/Arrows to move, Q to quit, P to pause\n";
    std::cout << "==================\n";
    
    for (int y = 0; y < BOARD_HEIGHT; y++) {
        std::cout << board[y] << "\n";
    }
    
    if (state.game_over) {
        std::cout << "\n=== GAME OVER! ===\n";
        std::cout << "Final Score: " << state.score << "\n";
        std::cout << "Press R to restart or Q to quit.\n";
    } else if (state.paused) {
        std::cout << "\n=== PAUSED ===\n";
        std::cout << "Press P to continue.\n";
    }
}

bool kbhit() {
    return _kbhit() != 0;
}

char get_char() {
    return _getch();
}

void update_direction(GameState& state, Direction new_dir) {
    Direction opposite = Direction::UP;
    switch (state.dir) {
        case Direction::UP:    opposite = Direction::DOWN;  break;
        case Direction::DOWN:  opposite = Direction::UP;    break;
        case Direction::LEFT:  opposite = Direction::RIGHT; break;
        case Direction::RIGHT: opposite = Direction::LEFT;  break;
    }
    if (new_dir != opposite) {
        state.next_dir = new_dir;
    }
}

bool move_snake(GameState& state) {
    state.dir = state.next_dir;
    
    Position head = state.snake.front();
    switch (state.dir) {
        case Direction::UP:    head.y--; break;
        case Direction::DOWN:  head.y++; break;
        case Direction::LEFT:  head.x--; break;
        case Direction::RIGHT: head.x++; break;
    }
    
    // Check wall collision
    if (head.x <= 0 || head.x >= BOARD_WIDTH - 1 || 
        head.y <= 0 || head.y >= BOARD_HEIGHT - 1) {
        return false;
    }
    
    // Check self collision (skip tail as it will move)
    for (size_t i = 0; i < state.snake.size() - 1; i++) {
        if (state.snake[i] == head) {
            return false;
        }
    }
    
    state.snake.push_front(head);
    
    // Check food
    if (head == state.food) {
        state.score += 10;
        place_food(state);
    } else {
        state.snake.pop_back();
    }
    
    return true;
}

void handle_input(GameState& state) {
    if (kbhit()) {
        char c = get_char();
        
        if (state.game_over) {
            if (c == 'r' || c == 'R') {
                init_game(state);
            }
            return;
        }
        
        if (state.paused) {
            if (c == 'p' || c == 'P') {
                state.paused = false;
            }
            return;
        }
        
        switch (c) {
            case 'w': case 'W': case 72: update_direction(state, Direction::UP);    break;
            case 's': case 'S': case 80: update_direction(state, Direction::DOWN);  break;
            case 'a': case 'A': case 75: update_direction(state, Direction::LEFT);   break;
            case 'd': case 'D': case 77: update_direction(state, Direction::RIGHT); break;
            case 'q': case 'Q': state.game_over = true; state.score = -1; break;
            case 'p': case 'P': state.paused = true; break;
        }
    }
}

int main() {
    std::srand(static_cast<unsigned>(std::time(nullptr)));
    
    GameState state;
    init_game(state);
    
    while (true) {
        render(state);
        
        if (!state.game_over && !state.paused) {
            if (!move_snake(state)) {
                state.game_over = true;
            }
        }
        
        handle_input();
        
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
    
    return 0;
}