三亩地 三亩地SAN MU DI · CODE DIARY
交流投稿
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天，欢迎挑你感兴趣的翻一翻。

首页/学习日记/日记详情

C++算法模拟器：用贪心、BFS、DP实现游戏角色AI对抗

发布时间：2026/8/6 7:25:11 三亩地 编程学习日记
C++算法模拟器：用贪心、BFS、DP实现游戏角色AI对抗

1. 项目概述：当算法竞赛遇上游戏设计

几年前，我还在算法竞赛的圈子里打转，每天琢磨着怎么用更优的时间复杂度去解决那些经典的图论、动态规划问题。后来机缘巧合，我开始接触游戏开发，突然发现，那些曾经让我绞尽脑汁的算法，在游戏世界里找到了绝佳的用武之地。比如，一个简单的BFS（广度优先搜索）可以用来实现游戏中的寻路系统；状态压缩DP（动态规划）能优雅地处理复杂的游戏状态；而贪心算法，则可能是设计一个公平又有趣的AI对手的关键。

“超能力者大赛”这个项目，正是这种跨界思维的产物。它不是一个传统的、画面华丽的商业游戏，而是一个基于控制台的、以算法逻辑为核心的模拟器。它的核心目标，是让你亲手用C++，将一群拥有不同“超能力”（本质上是不同的算法行为模式）的角色，放在一个竞技场中，观察他们如何博弈、对抗，并最终决出胜负。这听起来有点像“吃鸡”或“大逃杀”的简化版，但内核完全不同——我们关注的是算法策略的对抗性，而非图形渲染或用户操作。

这个项目非常适合两类朋友：一是有一定C++基础，想通过一个综合性项目提升工程能力的开发者；二是对算法感兴趣，想看看抽象的逻辑如何转化为具体、可交互的模拟的爱好者。你不需要掌握复杂的图形库（如OpenGL或Unity），只需要一个能跑C++的编译器（比如VS Code + MinGW，或者Visual Studio）和一颗好奇心。我们将从零开始，构建角色、定义能力、设计规则、实现核心循环，并最终得到一个可以运行、可以观察、甚至可以由你定制规则的完整程序。

2. 核心设计思路：从抽象规则到具体代码

在动手写代码之前，我们必须把“超能力者大赛”这个模糊的想法，拆解成清晰、可实现的模块。一个好的设计能让你在编码时思路清晰，避免后期陷入混乱的重构。

2.1 游戏世界与核心规则定义

首先，我们需要一个“舞台”。为了简化，我们设计一个二维网格世界。假设它是一个 20x20 的方格地图，每个格子可以容纳一个角色。角色们在这个地图上移动、使用能力、相互对抗。

游戏的核心规则采用回合制。这非常关键，因为回合制给了我们充足的时间去计算每个角色的复杂决策（算法），而不用担心实时渲染带来的性能压力。每一回合，所有存活的角色按一定顺序（比如随机顺序或根据某个属性）依次执行他们的“行动”。一个完整的行动可能包括：感知环境（收集信息）、决策（选择移动方向或使用能力）、执行（移动或发动攻击/效果）。

胜利条件很简单：最后一个存活在场地上的角色获胜。这模拟了“大逃杀”的最终生存者模式。

2.2 “超能力”的算法化诠释

“超能力”是这个项目的灵魂。我们不能把它做成简单的属性增减，而是要赋予每个能力独特的算法逻辑。这里我们设计四个初始角色，分别对应四种经典的算法思想：

  1. “闪现者” - 贪心算法的化身：它的能力是“闪现”。每回合，它会计算移动到哪个格子能最大化其“收益”。这个收益函数可以是“距离最近敌人的距离的负值”（即离敌人越近收益越高），也可以是“移动到资源点”。它总是选择当前看来最优的一步，目光短浅但反应迅速。这完美体现了贪心算法“局部最优”的特点。

  2. “预言家” - 动态规划的窥探者：它的能力是“预判”。它不会只看眼前，而是会尝试向前推演未来2-3个回合可能发生的情况（包括对手的可能行动）。基于这个推演，它选择一个从长远看（多个回合累计）收益最高的行动。这需要维护一个“状态”的概念，并计算状态转移的代价，是动态规划思想的简化体现。

  3. “追踪者” - 图论搜索的执行者：它的能力是“精准追踪”。它每回合会以自己为中心，使用广度优先搜索（BFS）或Dijkstra算法，扫描整个地图，找到所有敌人的位置，并规划出一条避开障碍（如果有的话）到达最近敌人的最短路径。然后沿着这条路径移动一步。这展示了图论算法在路径规划和全局感知中的应用。

  4. “混沌法师” - 随机化与概率的代言人：它的能力是“混沌波动”。它的行动完全随机，或者按照某种概率分布进行。比如，有50%概率向随机方向移动，30%概率对随机敌人造成伤害，20%概率给自己加一个随机buff。它代表了算法中的随机化策略，在复杂环境中有时能产生意想不到的效果，也是对确定性算法的一种补充和干扰。

设计心得：为每个能力设计一个清晰、独立的决策函数接口至关重要。例如，每个角色类都有一个makeDecision(const GameState& state)的纯虚函数。这样，新增角色只需要继承并实现这个接口，极大地提高了扩展性。

2.3 系统架构与类设计

基于以上思路，我们可以规划出几个核心的类：

  • Game：游戏主控类。负责初始化、运行主循环、判断游戏结束、管理回合。
  • GameState：游戏状态类。这是一个只读的、快照式的数据结构，包含当前所有角色的位置、血量、状态，以及地图信息。它被传递给每个角色用于决策，确保角色不能直接修改游戏世界，只能通过返回“行动指令”来影响世界。这是保持逻辑清晰和数据安全的关键。
  • Character（基类）：角色基类。包含通用属性（ID、位置、血量、状态）和虚函数接口（决策函数makeDecision， 执行函数act）。
  • Blinker, Prophet, Tracker, ChaosMage：继承自Character的具体角色类。它们各自实现独特的makeDecision逻辑。
  • Action：行动指令类。这是角色决策的产出，可能是一个移动指令（MOVE_TO [x, y]），一个攻击指令（ATTACK [target_id]），或者一个使用技能的指令（USE_ABILITY）。Game类收集所有角色的Action，然后按顺序安全地执行它们，解决可能的冲突（比如两个角色想移动到同一格）。

这种“状态快照 -> 角色决策 -> 行动收集 -> 统一执行”的流水线，是回合制策略模拟的经典架构，逻辑清晰且易于调试。

3. 核心模块实现详解

有了设计图，我们开始砌砖。这里我会重点讲解几个核心模块的实现细节和背后的考量。

3.1 游戏状态（GameState）的设计与实现

GameState是整个模拟的“事实来源”。它必须高效、不可变（对角色而言），并且包含决策所需的所有信息。

// GameState.h #pragma once #include <vector> #include <memory> #include "Character.h" // 前向声明可能更好，这里简单包含 struct GameState { int currentRound; int mapWidth, mapHeight; // 使用智能指针管理角色，避免内存泄漏 std::vector<std::shared_ptr<Character>> characters; // 可以扩展：地形信息、资源点等 // std::vector<std::vector<Tile>> mapGrid; // 关键方法：提供一个只读的角色视图和地图视图 const std::vector<std::shared_ptr<Character>>& getCharacters() const { return characters; } // 辅助方法：查找特定角色，计算距离等 std::shared_ptr<Character> findCharacterById(int id) const; double calculateDistance(int id1, int id2) const; bool isPositionValid(int x, int y) const; // 检查位置是否在地图内且未被阻挡 };

为什么使用std::shared_ptr？在模拟中，角色对象会被频繁地传递和访问（例如，在GameState中存储，被各个决策函数读取）。使用原始指针容易导致所有权混乱和内存泄漏。std::shared_ptr实现了引用计数，当最后一个持有该角色指针的对象（如GameState， 或某个正在计算的角色）释放它时，角色对象会被自动销毁，安全省心。

“只读”的重要性：GameState提供给角色决策函数时，必须是const引用。这强制角色只能读取当前状态，而不能修改其他角色或地图。所有对世界的修改，都必须通过返回Action， 由Game主循环在下一阶段统一、顺序地处理。这避免了并发修改带来的数据竞争和不可预测的bug，尤其在模拟复杂交互时。

3.2 角色基类与能力接口

角色基类定义了所有角色的共同框架。

// Character.h #pragma once #include "Action.h" #include <memory> class GameState; // 前向声明 class Character { protected: int id; std::string name; int health; int positionX, positionY; // 可能还有能量、冷却时间等属性 public: Character(int id, std::string name, int x, int y, int health); virtual ~Character() = default; // 核心：基于当前游戏状态做出决策，返回一个行动 virtual Action makeDecision(const GameState& state) = 0; // 执行行动的效果（由Game类调用，修改角色自身状态） virtual void applyAction(const Action& action); // Getter 和 Setter int getId() const { return id; } // ... bool isAlive() const { return health > 0; } };

纯虚函数makeDecision：这是多态的关键。Game主循环遍历所有角色时，只需要调用character->makeDecision(state)， 无需关心具体是哪种角色。具体的决策逻辑完全由子类实现。

接下来，我们以实现“追踪者”（Tracker）的BFS寻路为例，看看如何实现一个具体的决策逻辑。

// Tracker.cpp (部分) #include "Tracker.h" #include <queue> #include <unordered_map> #include <algorithm> Action Tracker::makeDecision(const GameState& state) { if (!isAlive()) return Action(ActionType::IDLE); // 死亡角色不行动 // 1. 使用BFS找到最近的敌人 std::queue<std::pair<int, int>> q; // 队列存储 (x, y) std::unordered_map<int, std::unordered_map<int, std::pair<int, int>>> cameFrom; // 记录路径 (x, y) -> (parentX, parentY) std::unordered_map<int, std::unordered_map<int, bool>> visited; // 访问标记 q.push({positionX, positionY}); visited[positionX][positionY] = true; cameFrom[positionX][positionY] = {-1, -1}; // 起点的父节点设为无效 int targetX = -1, targetY = -1; std::vector<std::pair<int, int>> directions = {{1,0},{-1,0},{0,1},{0,-1}}; // 四方向移动 while (!q.empty()) { auto [x, y] = q.front(); q.pop(); // 检查这个位置是否有敌人（非自己且存活） bool isEnemyHere = false; for (const auto& ch : state.getCharacters()) { if (ch->getId() != id && ch->isAlive() && ch->getPositionX() == x && ch->getPositionY() == y) { targetX = x; targetY = y; isEnemyHere = true; break; } } if (isEnemyHere) break; // 向四个方向扩展 for (auto [dx, dy] : directions) { int nx = x + dx, ny = y + dy; if (state.isPositionValid(nx, ny) && !visited[nx][ny]) { visited[nx][ny] = true; cameFrom[nx][ny] = {x, y}; q.push({nx, ny}); } } } // 2. 如果找到了敌人，回溯路径，得到下一步该走的位置 if (targetX != -1) { // 回溯到起点，找到第一步 int backX = targetX, backY = targetY; while (cameFrom[backX][backY].first != positionX || cameFrom[backX][backY].second != positionY) { if (cameFrom[backX][backY].first == -1) break; // 安全保护 auto [px, py] = cameFrom[backX][backY]; backX = px; backY = py; } // 如果下一步就是敌人位置，说明相邻，可以攻击 if (backX == targetX && backY == targetY) { // 查找该位置敌人的ID for (const auto& ch : state.getCharacters()) { if (ch->getId() != id && ch->isAlive() && ch->getPositionX() == targetX && ch->getPositionY() == targetY) { return Action(ActionType::ATTACK, ch->getId()); } } } // 否则，移动到路径上的下一个格子 return Action(ActionType::MOVE_TO, backX, backY); } // 3. 没找到敌人，随机移动或待机 return generateRandomMove(state); }

BFS实现要点：

  • 队列 (queue)：用于实现广度优先的遍历顺序，保证找到的路径是最短步数（在网格权重一致的情况下）。
  • 路径记录 (cameFrom)：一个二维映射，记录每个格子是从哪个格子访问过来的。这是回溯重建路径的关键。我们使用unordered_map套unordered_map来实现稀疏的二维访问，比使用一个大大的二维vector更节省空间，尤其当地图很大但角色很少时。
  • 边界与有效性检查：state.isPositionValid()函数封装了对地图边界和障碍物的检查，使BFS逻辑更清晰。
  • 性能考虑：每次决策都做一次全图BFS，在角色很多、地图很大时可能成为性能瓶颈。在实际优化中，可以考虑缓存结果、使用更高效的搜索算法（如A*），或者限制搜索深度。但对于我们这个中等规模的模拟，完全可接受。

3.3 游戏主循环与行动裁决

这是驱动整个模拟的引擎。主循环必须清晰地区分“决策阶段”和“执行阶段”。

// Game.cpp (主循环部分) void Game::runSimulation() { int round = 1; while (!isGameOver()) { std::cout << "===== Round " << round << " =====" << std::endl; // 阶段1: 决策阶段 - 所有存活角色基于当前状态做出决策 std::vector<Action> actions; for (auto& character : gameState.characters) { if (character->isAlive()) { Action act = character->makeDecision(gameState); act.setSourceId(character->getId()); // 记录行动发起者 actions.push_back(std::move(act)); // 使用移动语义提高效率 } } // 阶段2: 行动裁决与执行阶段 - 按顺序或特定规则处理行动 // 这里采用简单的随机顺序执行，增加不确定性 std::shuffle(actions.begin(), actions.end(), randomEngine); for (auto& action : actions) { if (!action.isValid()) continue; executeAction(action); // 执行单个行动，并更新gameState } // 阶段3: 回合结束处理 - 更新状态，打印日志 resolveRoundEnd(); printGameState(); round++; // 可以加一个延时，方便观察 // std::this_thread::sleep_for(std::chrono::milliseconds(500)); } announceWinner(); }

executeAction函数是另一个核心，它负责解释Action指令并实际修改游戏世界。例如，处理MOVE_TO指令时，需要检查目标位置是否合法（是否出界、是否已被占据），如果合法则更新角色的坐标。处理ATTACK指令时，需要找到目标角色，减少其血量，并判断是否被击败。

避坑指南：行动冲突处理这是一个常见的难点。比如，角色A和角色B在同一回合都决定移动到同一个空位上，或者角色A攻击B的同时B也攻击了A。我们的处理策略是：

  1. 顺序执行：如上代码所示，我们按某种顺序（这里随机打乱）执行行动。后执行的角色会“看到”先执行角色行动后的世界状态。这更符合“同时发生但总有细微先后”的现实感。
  2. 先判后执：在执行移动前，检查目标位置在当前时刻是否被占据。如果已被本回合先执行的角色占据，则移动失败。攻击同理，判断目标是否还存活。
  3. 日志记录：务必详细记录每个行动的执行结果（成功、失败及原因），这对调试和复盘至关重要。可以在executeAction中加入日志输出。

4. 代码整合、运行与观察

将上述所有模块组合起来，我们还需要一个main.cpp来设置初始场景。

// main.cpp #include "Game.h" #include "Blinker.h" #include "Prophet.h" #include "Tracker.h" #include "ChaosMage.h" #include <memory> int main() { // 1. 创建游戏实例，设置地图大小 Game game(20, 20); // 2. 创建并添加角色到游戏中 game.addCharacter(std::make_shared<Blinker>(1, "Blinker_Alpha", 5, 5, 100)); game.addCharacter(std::make_shared<Prophet>(2, "Prophet_Beta", 15, 5, 100)); game.addCharacter(std::make_shared<Tracker>(3, "Tracker_Gamma", 5, 15, 100)); game.addCharacter(std::make_shared<ChaosMage>(4, "Chaos_Delta", 15, 15, 100)); // 3. 可以设置随机种子，使每次运行结果可复现（调试用）或不可预测（模拟用） // game.setRandomSeed(12345); // 4. 运行模拟 std::cout << "=== 超能力者大赛模拟开始 ===" << std::endl; game.runSimulation(); return 0; }

编译并运行这个程序（例如，使用g++ -std=c++17 *.cpp -o super_arena），你将在控制台看到一场安静的、由算法驱动的生死斗。每一回合，程序会打印出所有角色的位置和状态，以及他们执行的关键行动。

如何从输出中获取洞见？不要只看最后谁赢了。仔细观察过程：

  • “追踪者”是否总能直线冲向敌人？是的，BFS保证了最短路径。
  • “预言家”的行为是否显得更有“远见”？它可能会为了躲避未来的围攻而提前走位，即使当前离敌人更远了。
  • “贪心者”是否容易落入陷阱？比如，为了追击一个残血敌人，冲进了另外两个敌人的攻击范围。
  • “混沌法师”的战绩如何？它的胜率可能不稳定，但偶尔能乱拳打死老师傅，这说明了随机策略在复杂系统中的作用。

你可以通过修改角色的初始位置、血量、甚至微调他们的决策函数（比如改变“预言家”的推演深度，“追踪者”的搜索范围），来观察对战结果的变化。这本身就是一种简单的参数调优和平衡性测试。

5. 扩展方向与深度优化建议

一个基础版本跑起来后，你可以从多个维度扩展这个项目，让它变得更丰富、更专业。

5.1 游戏性扩展

  • 更复杂的地形：在GameState的mapGrid中加入不同的地形格子，如“森林”（移动消耗增加）、“山地”（无法通行）、“治疗泉”（每回合回复）。角色决策时需要将这些因素纳入收益计算。
  • 更多样的能力：设计基于其他算法思想的能力。
    • “分身者”：使用分治思想。当生命值低于一定阈值时，可以分裂成两个属性减半的角色，共同作战。
    • “时间窃贼”：使用回溯算法。可以花费大量能量，将游戏状态回退到1-2回合前（需要保存历史状态快照），尝试不同的选择。
    • “均衡使徒”：使用模拟退火算法。它的决策不是完全贪心或完全随机，而是以一个较高的“能量”开始，随着回合进行，“温度”下降，逐渐从随机探索转向确定性策略。
  • 资源与成长系统：在地图上随机生成“能量晶体”，角色拾取后可以永久增强其某项属性（如攻击力、视野范围）或解锁二级技能。这引入了长期规划的维度。

5.2 算法与性能优化

  • 空间换时间：对于“追踪者”的BFS，如果地图固定且无障碍，可以预先计算所有格子之间的最短路径距离（Floyd-Warshall算法），存储在一个二维数组中。决策时直接查表，将O(n)的搜索变为O(1)的查找。这适用于角色众多、需要频繁寻路的场景。
  • 决策缓存：“预言家”的推演计算量最大。可以为其实现一个记忆化（Memoization）缓存。将游戏状态的哈希值作为键，将计算出的最优行动作为值存储起来。当遇到相同的状态时（在推演中很常见），直接返回缓存结果，避免重复计算。
  • 并行化决策：在决策阶段，每个角色的makeDecision是相互独立的。可以利用C++的<thread>或<future>库，将不同角色的决策过程放到多个线程中并行执行，充分利用多核CPU，显著提升大规模模拟（如100个角色）的速度。
  • 状态哈希：为了高效比较和缓存游戏状态，需要为GameState实现一个快速的哈希函数。可以将所有角色的位置、血量等信息编码成一个字符串或一个大的整数（比如使用Zobrist Hashing，一种在棋类AI中常用的技术），作为状态的唯一标识。

5.3 工程化与可视化

  • 数据驱动配置：将角色的属性（血量、速度）、能力的参数（贪心算法的收益权重、预言家的推演深度）从代码中剥离，放到JSON或YAML配置文件中。这样，调整平衡性无需重新编译，也方便进行自动化测试（用脚本批量跑不同配置的模拟）。
  • 日志与复盘系统：将完整的对战过程（每一回合的所有状态和行动）以结构化的格式（如JSON Lines）记录到文件中。之后可以编写一个单独的“复盘查看器”程序，加载日志文件，像看录像一样回放整个比赛，甚至可以暂停、分析关键时刻的决策。
  • 简单可视化：虽然我们强调算法核心，但一个简单的可视化能极大提升观察体验。你可以集成一个轻量级的图形库，如EasyX（Windows）或SFML（跨平台）。不需要复杂的动画，只需用不同颜色的方块代表不同角色，每回合刷新一次画面，就能直观地看到角色的移动轨迹和交战情况。这会将你的项目从“黑盒模拟”升级为“可观察实验”。

6. 常见问题与调试技巧

在开发过程中，你肯定会遇到各种问题。这里记录一些我踩过的坑和解决方法。

问题1：程序运行后很快结束，或者角色行为异常（比如原地不动、穿墙）。

  • 排查思路：
    1. 检查决策函数返回值：确保每个角色的makeDecision在所有分支条件下都返回了一个有效的Action对象。最容易出错的地方是条件分支的遗漏，导致函数没有返回值（未定义行为）。
    2. 验证GameState的传递：在makeDecision函数内部，打印或调试查看传入的state参数。确认它包含了你期望的角色信息和地图信息。检查getCharacters()返回的列表是否正确。
    3. 单步调试决策逻辑：针对一个行为异常的角色，在它的makeDecision函数开始处设置断点。一步一步跟踪，看它的感知（找到敌人了吗？）、计算（BFS路径对吗？）、决策（选择的行动合理吗？）每一步是否符合预期。
    4. 检查行动执行 (executeAction)：在executeAction中为每种行动类型添加详细的日志。例如：“角色[ID]尝试移动到(X,Y)，该位置当前状态为[空/被占]，移动[成功/失败]”。这能清晰地暴露行动冲突或条件判断错误。

问题2：内存使用量不断增长（内存泄漏）。

  • 根本原因：虽然我们用了shared_ptr，但如果在容器间复制或循环引用，仍可能导致内存无法释放。
  • 解决方案：
    • 使用weak_ptr打破循环：如果两个角色对象需要相互引用（比如记录“仇恨目标”），不要使用shared_ptr<Character>， 而应使用weak_ptr<Character>。weak_ptr不会增加引用计数，需要使用时通过lock()方法尝试获取shared_ptr。
    • 注意容器清理：当角色死亡时，将其从GameState::characters中移除。如果只是标记为“死亡”但指针还在向量里，对象就不会被销毁。正确的做法是，在回合结束后，将characters中所有isAlive() == false的元素移除（使用std::erase_if）。
    • 工具辅助：在Linux/macOS下可以使用valgrind， 在Windows下可以使用Visual Studio的内存诊断工具，来检测内存泄漏。

问题3：模拟结果不可复现，每次运行胜者都不同。

  • 这是特性，也可能是bug：如果是因为“混沌法师”的随机行为或行动顺序的随机打乱导致的，那是设计好的特性。但如果所有角色都是确定性的（比如去掉混沌法师，固定行动顺序），结果仍不同，那就是bug。
  • 排查方法：
    • 固定随机种子：在main函数或Game初始化时，调用std::srand(固定值)或传入固定的随机数引擎种子。确保所有“随机”行为（如混沌法师的决策、初始打乱顺序）在每次运行时完全一致。
    • 检查未初始化变量：确保所有类的成员变量、局部变量都被正确初始化。未初始化的变量值是不确定的，会导致程序行为不可预测。养成在构造函数中使用初始化列表的习惯。
    • 检查容器遍历的稳定性：如果你在决策或执行逻辑中遍历characters向量，并且这个遍历顺序会影响结果（例如，先处理哪个角色的攻击），那么你需要对向量进行排序（例如按ID），以确保遍历顺序稳定。

问题4：随着角色增多，程序运行越来越慢。

  • 性能瓶颈分析：
    • 最可能的热点：每个角色的决策函数，尤其是那些包含完整地图搜索（如BFS）的函数。复杂度可能是 O(N * M)，其中N是角色数，M是地图格子数。
    • 使用性能分析工具：如gprof(Linux) 或 Visual Studio Profiler。找出耗时最长的函数。
  • 优化策略：
    • 降低搜索频率：不是每回合都进行全图搜索。可以每2-3回合搜索一次，中间回合沿用之前的路径或进行小范围调整。
    • 缩小搜索范围：为角色增加“视野”属性，只搜索视野范围内的区域。
    • 使用更高效的数据结构：在判断“某个位置是否有角色”时，如果每次都线性扫描characters向量，是O(N)。可以维护一个std::unordered_map<std::pair<int, int>, Character*>来建立位置到角色的快速映射，实现O(1)的查找。
    • 如前所述，考虑并行化决策。

这个项目就像一座桥梁，一端是严谨、抽象的算法世界，另一端是生动、具象的模拟体验。当你看到自己编写的几行BFS代码驱动着一个角色在网格间执着地追逐对手时，那种感觉非常奇妙。它让你深刻理解，算法不是枯燥的公式，而是构建智能行为的基石。你可以不断往里面添加新的“超能力”（算法），调整参数，观察整个系统涌现出的复杂行为。这不仅是编程练习，更是一场关于策略、涌现和复杂系统的微型实验。

编程学习 学习日记 实战经验
← 返回列表