算法在游戏中的应用¶
国际化课程
Lecture 1¶
概述¶
游戏的分类
- 策略游戏：实时策略、塔防。
- 运动：单人、团队、竞速。
- 模拟：飞行模拟、商业模拟。
- 冒险。
- 角色扮演：肉鸽。
- 动作：射击、格斗、音乐、平台游戏（platformer）
Pygame 游戏引擎¶
建议阅读 Python 三剑客的项目实战。
MVC 模式¶
以棋盘游戏为例：
- Model 管理数据。在棋盘游戏中负责：初始化期盼、移动棋子、判断输赢。
- View 负责显示。
- Controller 处理输入。除了键盘、鼠标等，在多人游戏中还包括网络。将输入动作映射为 model 或 view 的动作。
图像¶
剩下半节课讲了如何用 Pygame 画图。
Lecture 2¶
一整节课都在讲 Pygame。
Lecture 3：迷宫¶
迷宫基础知识¶
- Cell：迷宫中的一个格子。
- Perfect maze：任意两个 cell 之间有且仅有一条路径。这意味着很多分支，但是没有环。
- Unicursal maze：没有分支，从头到尾只有一条路径。
- Braided maze：有环，但是没有死胡同。
- Weave maze：有高度分层的迷宫。
迷宫的指标：
- Passage length：路径的长度。
- Dead ends：多少 cell 只有一个出口？
- Crossroads：多少 cell 有三个或以上的出口？
- Blas：迷宫的随机性有多均匀？
- 见 Understanding Biases. An excerpt from Mazes for Programmers… | by The Pragmatic Programmers | The Pragmatic Programmers | Medium。
- 姑且可以理解为“倾向”。比如二叉树算法倾向于生成对角线路径。
- Difficulty：迷宫的难度。
迷宫生成¶
大多数算法以全不相连的 cell 开始，然后逐渐连接它们，称为 carving。另一些算法则在 cell 之间添加 wall，称为 wall adders。
- Binary Tree：
- 见 Buckblog: Maze Generation: Binary Tree algorithm
- 生成一个完美迷宫。
- 因为是以 cell 为单位进行计算，非常容易并行
- 生成出来的迷宫没有 entry 和 exit，因为是完美迷宫，所以可以随意放置。
- Sidewinder：
- 见 Buckblog: Maze Generation: Sidewinder algorithm
- 第一行全连接。接下来每一行中，每走一格决定要不要连接到下一格。每次决定不连接时，就从之前连接的 cell 中随机选择一个连接到上一行。
- 逐行生成。各行可以并行。
- 有很多短的死胡同。
- 有南北向的倾向。
- Aldous-Broder（Random walk）：
- 见 Buckblog: Maze Generation: Aldous-Broder algorithm
- 随机游走。产生一个生成树（spanning tree）。
- 没有 bias，生成的迷宫比较好看。
- 可能耗费大量时间。
- Wilson：
- 见 Buckblog: Maze Generation: Wilson's algorithm
- loop-erasing 的随机游走。
- 比 AB 算法快很多。
- Recursive Backtracker