#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;
}