#include <iostream>
#include <vector>
#include <string>
#include <conio.h>
#include <windows.h>
#include <random>
#include <chrono>
#include <algorithm>
#include <thread>
#include <queue>

using namespace std;

// 地图大小
const int WIDTH = 60;
const int HEIGHT = 30;

// 地图元素
const char EMPTY = ' ';
const char WALL = '#';
const char PLAYER = 'P';
const char NPC = 'N';
const char EXIT = 'E';

// 方向
enum Dir { UP, DOWN, LEFT, RIGHT };

// 坐标
struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    bool operator!=(const Point& other) const {
        return !(*this == other);
    }
};

// 双缓冲
class DoubleBuffer {
private:
    HANDLE hConsole;
    CHAR_INFO* buffer;
    int w, h;
    
public:
    DoubleBuffer(int _w, int _h) : w(_w), h(_h) {
        hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
        buffer = new CHAR_INFO[w * h];
        CONSOLE_CURSOR_INFO ci;
        GetConsoleCursorInfo(hConsole, &ci);
        ci.bVisible = FALSE;
        SetConsoleCursorInfo(hConsole, &ci);
    }
    
    ~DoubleBuffer() { delete[] buffer; }
    
    void clear() {
        for (int i = 0; i < w * h; i++) {
            buffer[i].Char.AsciiChar = ' ';
            buffer[i].Attributes = 7;
        }
    }
    
    void setChar(int x, int y, char ch, int color = 7) {
        if (x >= 0 && x < w && y >= 0 && y < h) {
            int idx = y * w + x;
            buffer[idx].Char.AsciiChar = ch;
            buffer[idx].Attributes = color;
        }
    }
    
    void render() {
        COORD pos = { 0, 0 };
        SMALL_RECT rect = { 0, 0, (SHORT)(w - 1), (SHORT)(h - 1) };
        WriteConsoleOutputA(hConsole, buffer, { (SHORT)w, (SHORT)h }, pos, &rect);
    }
};

// 随机地图生成器 - 带分叉和死路
class MapGenerator {
private:
    random_device rd;
    mt19937 gen;
    int width, height;
    vector<string> map;
    vector<vector<bool>> visited;
    
public:
    MapGenerator() : gen(rd()) {}
    
    // 检查位置是否可通行（用于BFS）
    bool isWalkable(int x, int y) {
        if (x <= 0 || x >= width - 1 || y <= 0 || y >= height - 1) return false;
        return map[y][x] != WALL;
    }
    
    // 获取邻居（用于迷宫生成）
    vector<Point> getNeighbors(int x, int y, int step) {
        vector<Point> neighbors;
        int dx[] = {0, 0, step, -step};
        int dy[] = {step, -step, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > 0 && nx < width - 1 && ny > 0 && ny < height - 1 && !visited[ny][nx]) {
                neighbors.push_back(Point(nx, ny));
            }
        }
        return neighbors;
    }
    
    // 使用递归回溯生成基础迷宫
    void generateBaseMaze() {
        // 初始化地图为墙
        map.assign(height, string(width, WALL));
        visited.assign(height, vector<bool>(width, false));
        
        // 起点
        Point start(1, 1);
        map[1][1] = EMPTY;
        visited[1][1] = true;
        
        vector<Point> stack;
        stack.push_back(start);
        
        while (!stack.empty()) {
            Point cur = stack.back();
            auto neighbors = getNeighbors(cur.x, cur.y, 2);
            
            if (!neighbors.empty()) {
                // 随机选择一个邻居
                uniform_int_distribution<> dis(0, neighbors.size() - 1);
                Point next = neighbors[dis(gen)];
                
                // 打通墙壁
                map[(cur.y + next.y) / 2][(cur.x + next.x) / 2] = EMPTY;
                map[next.y][next.x] = EMPTY;
                visited[next.y][next.x] = true;
                stack.push_back(next);
            } else {
                stack.pop_back();
            }
        }
    }
    
    // 添加分叉和死路
    void addBranchesAndDeadEnds() {
        uniform_int_distribution<> dis(0, 100);
        uniform_int_distribution<> xDis(2, width - 3);
        uniform_int_distribution<> yDis(2, height - 3);
        
        // 收集所有空地
        vector<Point> emptySpaces;
        for (int y = 2; y < height - 2; y++) {
            for (int x = 2; x < width - 2; x++) {
                if (map[y][x] == EMPTY) {
                    emptySpaces.push_back(Point(x, y));
                }
            }
        }
        
        // 随机选择一些空地，开辟新的分支
        shuffle(emptySpaces.begin(), emptySpaces.end(), gen);
        int branchesToAdd = emptySpaces.size() / 8;  // 大约12.5%的空地变为分支点
        
        for (int i = 0; i < min(branchesToAdd, (int)emptySpaces.size()); i++) {
            Point p = emptySpaces[i];
            
            // 检查周围是否有墙可以打通
            vector<int> dirs = {0, 1, 2, 3};
            shuffle(dirs.begin(), dirs.end(), gen);
            
            int dx[] = {0, 0, 1, -1};
            int dy[] = {1, -1, 0, 0};
            
            for (int d : dirs) {
                int nx = p.x + dx[d] * 2;
                int ny = p.y + dy[d] * 2;
                int mx = p.x + dx[d];
                int my = p.y + dy[d];
                
                if (nx > 0 && nx < width - 1 && ny > 0 && ny < height - 1 &&
                    map[ny][nx] == EMPTY && map[my][mx] == WALL) {
                    // 打通墙壁，创建分支
                    map[my][mx] = EMPTY;
                    break;
                }
            }
        }
        
        // 创建死路 - 在一些分支末端添加死胡同
        for (int i = 0; i < branchesToAdd / 2; i++) {
            Point p = emptySpaces[dis(gen) % emptySpaces.size()];
            
            // 找到这个点的一个方向，可以挖出一条死路
            vector<int> dirs = {0, 1, 2, 3};
            shuffle(dirs.begin(), dirs.end(), gen);
            
            int dx[] = {0, 0, 1, -1};
            int dy[] = {1, -1, 0, 0};
            
            for (int d : dirs) {
                int nx = p.x + dx[d] * 3;
                int ny = p.y + dy[d] * 3;
                int mx1 = p.x + dx[d];
                int my1 = p.y + dy[d];
                int mx2 = p.x + dx[d] * 2;
                int my2 = p.y + dy[d] * 2;
                
                if (nx > 0 && nx < width - 1 && ny > 0 && ny < height - 1 &&
                    map[ny][nx] == WALL && map[my2][mx2] == WALL) {
                    // 挖一条死路
                    map[my1][mx1] = EMPTY;
                    map[my2][mx2] = EMPTY;
                    break;
                }
            }
        }
    }
    
    // 创建循环路径（增加多个出口路径）
    void addLoops() {
        uniform_int_distribution<> dis(0, 100);
        
        // 找一些空地，创建循环
        vector<Point> emptySpaces;
        for (int y = 2; y < height - 2; y++) {
            for (int x = 2; x < width - 2; x++) {
                if (map[y][x] == EMPTY) {
                    emptySpaces.push_back(Point(x, y));
                }
            }
        }
        
        shuffle(emptySpaces.begin(), emptySpaces.end(), gen);
        int loopsToAdd = emptySpaces.size() / 10;
        
        for (int i = 0; i < min(loopsToAdd, (int)emptySpaces.size()); i++) {
            Point p = emptySpaces[i];
            
            // 检查是否可以创建一个2x2的循环
            if (p.x + 1 < width - 1 && p.y + 1 < height - 1) {
                if (map[p.y][p.x + 1] == WALL && map[p.y + 1][p.x] == WALL &&
                    map[p.y + 1][p.x + 1] == EMPTY) {
                    map[p.y][p.x + 1] = EMPTY;
                    map[p.y + 1][p.x] = EMPTY;
                } else if (map[p.y][p.x + 1] == EMPTY && map[p.y + 1][p.x] == WALL &&
                           map[p.y + 1][p.x + 1] == WALL) {
                    map[p.y + 1][p.x] = EMPTY;
                    map[p.y + 1][p.x + 1] = EMPTY;
                }
            }
        }
    }
    
    // BFS检查路径是否存在
    bool hasPath(Point start, Point target) {
        if (!isWalkable(start.x, start.y) || !isWalkable(target.x, target.y)) {
            return false;
        }
        
        vector<vector<bool>> visited2(height, vector<bool>(width, false));
        queue<Point> q;
        q.push(start);
        visited2[start.y][start.x] = true;
        
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        
        while (!q.empty()) {
            Point cur = q.front();
            q.pop();
            
            if (cur.x == target.x && cur.y == target.y) {
                return true;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx > 0 && nx < width - 1 && ny > 0 && ny < height - 1 &&
                    !visited2[ny][nx] && map[ny][nx] != WALL) {
                    visited2[ny][nx] = true;
                    q.push(Point(nx, ny));
                }
            }
        }
        return false;
    }
    
    // BFS找多条路径（用于验证）
    int countPaths(Point start, Point target) {
        if (!isWalkable(start.x, start.y) || !isWalkable(target.x, target.y)) {
            return 0;
        }
        
        vector<vector<int>> ways(height, vector<int>(width, 0));
        queue<Point> q;
        q.push(start);
        ways[start.y][start.x] = 1;
        
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        
        int pathCount = 0;
        
        while (!q.empty()) {
            Point cur = q.front();
            q.pop();
            
            if (cur.x == target.x && cur.y == target.y) {
                pathCount += ways[cur.y][cur.x];
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx > 0 && nx < width - 1 && ny > 0 && ny < height - 1 &&
                    map[ny][nx] != WALL) {
                    if (ways[ny][nx] == 0) {
                        q.push(Point(nx, ny));
                    }
                    ways[ny][nx] += ways[cur.y][cur.x];
                }
            }
        }
        return pathCount;
    }
    
    vector<string> generate(int w, int h) {
        width = w;
        height = h;
        
        // 生成基础迷宫
        generateBaseMaze();
        
        // 添加分叉
        addBranchesAndDeadEnds();
        
        // 添加循环
        addLoops();
        
        // 确保边界是墙
        for (int y = 0; y < height; y++) {
            map[y][0] = WALL;
            map[y][width - 1] = WALL;
        }
        for (int x = 0; x < width; x++) {
            map[0][x] = WALL;
            map[height - 1][x] = WALL;
        }
        
        // 开入口和出口
        map[1][0] = EMPTY;
        map[height - 2][width - 1] = EMPTY;
        
        // 确保入口和出口可通行
        Point start(1, 1);
        Point exitPos(width - 2, height - 2);
        
        // 如果出口被堵，清空周围
        if (map[exitPos.y][exitPos.x] == WALL) {
            map[exitPos.y][exitPos.x] = EMPTY;
            map[exitPos.y - 1][exitPos.x] = EMPTY;
            map[exitPos.y][exitPos.x - 1] = EMPTY;
        }
        
        // 验证是否有路径，如果没有，强制开一条
        if (!hasPath(start, exitPos)) {
            // 简单方案：从起点到终点直线打通
            for (int y = start.y; y <= exitPos.y; y++) {
                map[y][start.x] = EMPTY;
            }
            for (int x = start.x; x <= exitPos.x; x++) {
                map[exitPos.y][x] = EMPTY;
            }
        }
        
        return map;
    }
    
    // 在安全距离外找空位
    Point findSafePosition(const vector<string>& map, Point playerPos, int minDist = 8) {
        uniform_int_distribution<> xDis(2, width - 3);
        uniform_int_distribution<> yDis(2, height - 3);
        
        vector<Point> candidates;
        
        for (int y = 2; y < height - 2; y++) {
            for (int x = 2; x < width - 2; x++) {
                if (map[y][x] == EMPTY) {
                    int dist = abs(x - playerPos.x) + abs(y - playerPos.y);
                    if (dist >= minDist) {
                        // 检查这个位置周围是否开阔（避免NPC卡在死路）
                        int openCount = 0;
                        if (map[y-1][x] == EMPTY) openCount++;
                        if (map[y+1][x] == EMPTY) openCount++;
                        if (map[y][x-1] == EMPTY) openCount++;
                        if (map[y][x+1] == EMPTY) openCount++;
                        if (openCount >= 2) {
                            candidates.push_back(Point(x, y));
                        }
                    }
                }
            }
        }
        
        if (candidates.empty()) {
            return Point(3, 3);
        }
        
        uniform_int_distribution<> idxDis(0, candidates.size() - 1);
        return candidates[idxDis(gen)];
    }
};

// 游戏主类
class Game {
private:
    vector<string> map;
    Point player;
    vector<Point> npcs;
    Point exitPos;
    bool gameOver;
    bool levelComplete;
    int moves;
    int score;
    DoubleBuffer* display;
    MapGenerator generator;
    chrono::steady_clock::time_point lastNPCMove;
    random_device rd;
    mt19937 gen;
    
    const int COLOR_PLAYER = 10;
    const int COLOR_NPC = 12;
    const int COLOR_WALL = 8;
    const int COLOR_EXIT = 14;
    const int COLOR_UI = 15;
    
public:
    Game() : gameOver(false), levelComplete(false), moves(0), score(0), gen(rd()) {
        display = new DoubleBuffer(WIDTH + 2, HEIGHT + 10);
        generateNewMap();
        lastNPCMove = chrono::steady_clock::now();
    }
    
    ~Game() { delete display; }
    
    void generateNewMap() {
        // 生成带分叉和死路的迷宫
        map = generator.generate(WIDTH, HEIGHT);
        
        // 放置玩家在入口
        player = Point(1, 1);
        
        // 放置出口
        exitPos = Point(WIDTH - 2, HEIGHT - 2);
        map[exitPos.y][exitPos.x] = EXIT;
        
        // 生成NPC - 确保不在玩家附近
        npcs.clear();
        int npcCount = 6 + gen() % 7;  // 6-12个NPC
        
        for (int i = 0; i < npcCount * 3 && (int)npcs.size() < npcCount; i++) {
            Point pos = generator.findSafePosition(map, player, 8);
            
            if (pos == exitPos) continue;
            
            bool overlap = false;
            for (auto& npc : npcs) {
                if (npc == pos) {
                    overlap = true;
                    break;
                }
            }
            if (overlap) continue;
            
            npcs.push_back(pos);
        }
        
        gameOver = false;
        levelComplete = false;
        moves = 0;
        score++;
    }
    
    void draw() {
        display->clear();
        
        // UI
        string title = "========== PARKOUR ==========";
        for (int i = 0; i < (int)title.length(); i++) {
            display->setChar(i, 0, title[i], COLOR_UI);
        }
        
        string info = "Score: " + to_string(score) + "  Moves: " + to_string(moves) + 
                      "  NPCs: " + to_string(npcs.size()) + "  [Infinite Mode]";
        for (int i = 0; i < (int)info.length(); i++) {
            display->setChar(i, 1, info[i], COLOR_UI);
        }
        
        string controls = "WASD:Move  R:Restart  Q:Quit  Reach E to advance!";
        for (int i = 0; i < (int)controls.length(); i++) {
            display->setChar(i, 2, controls[i], COLOR_UI);
        }
        
        string divider(WIDTH, '=');
        for (int i = 0; i < WIDTH; i++) {
            display->setChar(i, 3, divider[i], COLOR_UI);
        }
        
        // 地图
        for (int y = 0; y < HEIGHT; y++) {
            for (int x = 0; x < WIDTH; x++) {
                int sx = x;
                int sy = y + 4;
                
                if (player.x == x && player.y == y) {
                    display->setChar(sx, sy, PLAYER, COLOR_PLAYER);
                } else if (map[y][x] == WALL) {
                    display->setChar(sx, sy, WALL, COLOR_WALL);
                } else if (map[y][x] == EXIT) {
                    display->setChar(sx, sy, EXIT, COLOR_EXIT);
                } else {
                    bool hasNPC = false;
                    for (auto& npc : npcs) {
                        if (npc.x == x && npc.y == y) {
                            hasNPC = true;
                            break;
                        }
                    }
                    if (hasNPC) {
                        display->setChar(sx, sy, NPC, COLOR_NPC);
                    } else {
                        display->setChar(sx, sy, EMPTY, 7);
                    }
                }
            }
        }
        
        // 底部信息
        for (int i = 0; i < WIDTH; i++) {
            display->setChar(i, HEIGHT + 4, '=', COLOR_UI);
        }
        
        if (gameOver) {
            string msg = "GAME OVER! Press R to restart, Q to quit  Score: " + to_string(score);
            for (int i = 0; i < (int)msg.length(); i++) {
                display->setChar(i, HEIGHT + 5, msg[i], COLOR_NPC);
            }
        } else if (levelComplete) {
            string msg = "LEVEL COMPLETE! New map generated!  Score: " + to_string(score);
            for (int i = 0; i < (int)msg.length(); i++) {
                display->setChar(i, HEIGHT + 5, msg[i], COLOR_EXIT);
            }
        } else {
            string msg = "Navigate through branches & dead ends! Avoid N, reach E";
            for (int i = 0; i < (int)msg.length(); i++) {
                display->setChar(i, HEIGHT + 5, msg[i], COLOR_UI);
            }
        }
        
        display->render();
    }
    
    void movePlayer(Dir dir) {
        if (gameOver) return;
        
        int dx = 0, dy = 0;
        switch(dir) {
            case UP: dy = -1; break;
            case DOWN: dy = 1; break;
            case LEFT: dx = -1; break;
            case RIGHT: dx = 1; break;
        }
        
        int nx = player.x + dx;
        int ny = player.y + dy;
        
        if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) return;
        if (map[ny][nx] == WALL) return;
        
        player.x = nx;
        player.y = ny;
        moves++;
        
        if (map[ny][nx] == EXIT) {
            levelComplete = true;
            generateNewMap();
            return;
        }
        
        for (auto& npc : npcs) {
            if (npc.x == player.x && npc.y == player.y) {
                gameOver = true;
                return;
            }
        }
    }
    
    void updateNPCs() {
        if (gameOver || levelComplete) return;
        
        uniform_int_distribution<> dirDis(0, 3);
        uniform_int_distribution<> chanceDis(0, 100);
        
        for (int i = 0; i < (int)npcs.size(); i++) {
            Point& npc = npcs[i];
            
            int dist = abs(npc.x - player.x) + abs(npc.y - player.y);
            bool chase = false;
            
            if (dist < 25) {
                int chaseChance = max(20, 85 - dist * 2);
                if (chanceDis(gen) < chaseChance) {
                    chase = true;
                }
            }
            
            int dx = 0, dy = 0;
            if (chase) {
                if (npc.x < player.x) dx = 1;
                else if (npc.x > player.x) dx = -1;
                if (npc.y < player.y) dy = 1;
                else if (npc.y > player.y) dy = -1;
                
                if (dx != 0 && dy != 0) {
                    if (chanceDis(gen) % 2 == 0) dx = 0;
                    else dy = 0;
                }
                
                if (chanceDis(gen) < 8) {
                    dx = -dx;
                    dy = -dy;
                }
            } else {
                int dir = dirDis(gen);
                if (dir == 0) dy = -1;
                else if (dir == 1) dy = 1;
                else if (dir == 2) dx = -1;
                else dx = 1;
            }
            
            int nx = npc.x + dx;
            int ny = npc.y + dy;
            
            if (nx > 0 && nx < WIDTH - 1 && ny > 0 && ny < HEIGHT - 1 &&
                map[ny][nx] != WALL && map[ny][nx] != EXIT) {
                
                bool occupied = false;
                for (int j = 0; j < (int)npcs.size(); j++) {
                    if (i == j) continue;
                    if (npcs[j].x == nx && npcs[j].y == ny) {
                        occupied = true;
                        break;
                    }
                }
                
                if (!occupied) {
                    if (nx == player.x && ny == player.y) {
                        gameOver = true;
                        return;
                    }
                    npc.x = nx;
                    npc.y = ny;
                }
            }
        }
    }
    
    void restart() {
        generateNewMap();
        lastNPCMove = chrono::steady_clock::now();
    }
    
    bool isGameOver() const { return gameOver; }
    bool isLevelComplete() const { return levelComplete; }
    int getScore() const { return score; }
    
    void run() {
        auto lastUpdate = chrono::steady_clock::now();
        
        while (true) {
            draw();
            
            if (gameOver) {
                if (_kbhit()) {
                    char key = _getch();
                    if (key == 'r' || key == 'R') {
                        restart();
                    } else if (key == 'q' || key == 'Q') {
                        break;
                    }
                }
                this_thread::sleep_for(chrono::milliseconds(50));
                continue;
            }
            
            if (_kbhit()) {
                char key = _getch();
                switch(key) {
                    case 'w': case 'W': movePlayer(UP); break;
                    case 's': case 'S': movePlayer(DOWN); break;
                    case 'a': case 'A': movePlayer(LEFT); break;
                    case 'd': case 'D': movePlayer(RIGHT); break;
                    case 'r': case 'R': restart(); break;
                    case 'q': case 'Q': return;
                }
            }
            
            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast<chrono::milliseconds>(now - lastUpdate);
            if (elapsed.count() > 130) {
                updateNPCs();
                lastUpdate = now;
            }
            
            this_thread::sleep_for(chrono::milliseconds(10));
        }
    }
};

int main() {
    system("mode con: cols=70 lines=45");
    system("title Parkour Game - Complex Maze");
    
    Game game;
    game.run();
    
    return 0;
}