# polygon-game

**Repository Path**: delusion-2022/polygon-game

## Basic Information

- **Project Name**: polygon-game
- **Description**: 可视化动态规划小游戏
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 6
- **Forks**: 1
- **Created**: 2026-05-21
- **Last Updated**: 2026-05-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 多边形游戏

算法设计与分析实践项目 - 基于经典多边形游戏问题的Web游戏

## 项目结构

```
game/
├── backend/                # 后端 Spring Boot 项目
│   ├── src/main/java/com/huangwei/ai/polygon/
│   │   ├── controller/     # REST API 和 WebSocket
│   │   ├── service/        # 业务逻辑（含 DpSolver 求解器）
│   │   ├── model/          # 数据模型（DTO、实体）
│   │   ├── dao/            # 数据访问层
│   │   └── config/         # 配置类
│   ├── src/main/resources/
│   │   ├── application.yml
│   │   └── database/       # SQL 初始化脚本
│   └── pom.xml
├── frontend/               # 前端 React 项目
│   ├── src/
│   │   ├── pages/          # 页面（首页、单机、房间、对战）
│   │   ├── components/     # 组件（Canvas渲染、游戏控制、记分板）
│   │   ├── services/       # API 调用封装
│   │   └── types/          # TypeScript 类型定义
│   ├── vite.config.ts
│   └── package.json
├── deploy/                 # 服务器部署配置样例
│   └── application.yaml
└── polygon-game-architecture.md  # 架构设计文档
```

## 技术栈

### 后端
- Java 21 + Spring Boot 3.2
- Spring WebSocket（实时通信）
- MyBatis-Plus（ORM）
- MySQL 8（数据存储）
- Redis（房间状态、会话缓存）
- Sa-Token（用户认证）

### 前端
- React 18 + TypeScript
- Vite（构建工具）
- Tailwind CSS（样式）
- Canvas API（多边形渲染）
- WebSocket API（联机通信）

## 核心算法

采用**区间动态规划**求解最优解，时间复杂度 O(n^3)：

1. **枚举首边**：遍历每条边作为第一条删除的边，将环形结构转化为线性链
2. **区间 DP**：对线性链执行区间 DP，维护 `dpMax[i][j]` 和 `dpMin[i][j]` 分别记录区间 [i,j] 的最大值和最小值
3. **路径记录**：使用 HashMap 以 `"i,j"` 为 key 记录每个区间的最优合并路径
4. **负数处理**：乘法运算同时考虑四种组合 (max*max, max*min, min*max, min*min)，正确处理负负得正
5. **大数支持**：全程使用 `BigInteger` 运算，无溢出风险

## 核心功能

1. **单机模式**：自由操作，支持撤销、重置、求解最优解
2. **联机模式**：实时 WebSocket 对战，支持合作和对抗两种模式
3. **房间管理**：创建/加入/退出房间
4. **最优解求解**：O(n^3) DP 算法，支持任意整数和大数运算

## 快速开始

### 1. 环境准备

- JDK 21+
- Node.js 18+
- MySQL 8.0+
- Redis 6.0+

### 2. 数据库初始化

```sql
CREATE DATABASE polygon_game DEFAULT CHARACTER SET utf8mb4;
-- 执行 backend/src/main/resources/database/ 下的 SQL 脚本
```

### 3. 配置

编辑 `backend/src/main/resources/application.yml`，配置 MySQL 和 Redis 连接信息。

### 4. 启动后端

```bash
cd backend
./mvnw spring-boot:run
```

后端默认运行在 http://localhost:9093

### 5. 启动前端

```bash
cd frontend
npm install
npm run dev
```

前端默认运行在 http://localhost:3000

### 6. 访问游戏

打开浏览器访问 http://localhost:3000

## 游戏规则

1. 初始状态：n 个顶点的多边形，每个顶点有整数值，每条边有运算符（+ 或 *）
2. 操作：选择一条边删除，该边连接的两个顶点合并为一个
3. 合并规则：新值 = 左顶点 运算符 右顶点
4. 目标：通过 n-1 次操作，获得最高分数

## API 接口

### 单机模式

| 方法 | 路径 | 说明 |
|------|------|------|
| POST | /api/polygon/game/create | 创建新游戏 |
| POST | /api/polygon/game/action | 执行操作（删除边） |
| POST | /api/polygon/game/undo | 撤销操作 |
| GET | /api/polygon/game/state | 获取当前游戏状态 |
| GET | /api/polygon/game/solve | 求解最优解 |
| POST | /api/polygon/game/reset | 重置游戏 |

### 联机模式

| 方法 | 路径 | 说明 |
|------|------|------|
| POST | /api/polygon/room/create | 创建房间 |
| POST | /api/polygon/room/join | 加入房间 |
| GET | /api/polygon/room/list | 房间列表 |
| GET | /api/polygon/room/{id} | 房间详情 |
| POST | /api/polygon/room/start | 开始游戏 |
| DELETE | /api/polygon/room/{id} | 退出房间 |

### WebSocket

```
ws://host/api/polygon/ws/game/{roomId}
```

## 服务器部署

项目部署在服务器 `/game` 路径下

- 前端静态资源：`/opt/polygon-game/frontend/`
- 后端 JAR：`/opt/polygon-game/polygon-game-1.0.0.jar`
- 后端端口：9094
- Nginx 反向代理：`/game/` -> 前端，`/game/api/` -> 后端

## License

MIT