游戏算法图解

图 1.1广度优先搜索。在格子上拖动可以画墙，拖动 S / G 可以移动起点和终点。单独打开 ↗

先看懂，再写代码

每一章都从一个具体的游戏问题出发，先用图和演示建立直觉，再进入实现。

演示就是代码

网页里运行的演示由正文中的 C++ 编译而来，文中的代码片段直接取自仓库源码。

拿来就能用

算法与渲染完全分离，每个头文件都附带单元测试，可以直接放进你的引擎。

序
基础工具
Foundations
I
寻路
Pathfinding
II
碰撞检测与物理
Collision & Physics
1. 2.1基础相交测试：AABB、圆与射线阅读
2. 2.2分离轴定理（SAT）计划中
3. 2.3GJK 与 EPA计划中
4. 2.4宽相检测：均匀网格与空间哈希计划中
5. 2.5宽相检测：四叉树与八叉树计划中
6. 2.6宽相检测：BVH 与 Sweep and Prune计划中
7. 2.7数值积分：Euler、Verlet 与 RK4计划中
8. 2.8碰撞响应与冲量计划中
9. 2.9连续碰撞检测：子弹为什么会穿墙计划中
III
游戏 AI
Game AI
1. 3.1有限状态机与分层状态机计划中
2. 3.2行为树计划中
3. 3.3GOAP：目标导向行为规划计划中
4. 3.4Utility AI：效用评分决策计划中
5. 3.5转向行为与 Boids 群体模拟计划中
6. 3.6影响力图计划中
7. 3.7Minimax 与 Alpha-Beta 剪枝计划中
8. 3.8蒙特卡洛树搜索计划中
9. 3.9视野与感知：阴影投射计划中
IV
程序化生成
Procedural Generation
1. 4.1噪声：Value Noise 与 Perlin Noise计划中
2. 4.2噪声：Simplex、Worley 与分形布朗运动计划中
3. 4.3用噪声生成地形计划中
4. 4.4地牢生成：BSP、随机游走、房间与走廊计划中
5. 4.5元胞自动机生成洞穴计划中
6. 4.6泊松圆盘采样计划中
7. 4.7Voronoi 与 Delaunay 三角剖分计划中
8. 4.8波函数坍缩计划中
9. 4.9L-System计划中
V
动画与表现
Animation & Rendering
1. 5.1贝塞尔曲线与 Catmull-Rom 样条计划中
2. 5.2反向动力学：CCD 与 FABRIK计划中
3. 5.3相机算法：跟随、死区与震屏计划中
4. 5.4粒子系统设计计划中
5. 5.5视锥剔除与遮挡剔除计划中
VI
架构、性能与网络
Architecture & Networking
1. 6.1对象池与内存布局计划中
2. 6.2ECS 与数据导向设计计划中
3. 6.3命令模式、录像回放与撤销计划中
4. 6.4定点数与确定性计算计划中
5. 6.5网络同步：帧同步与状态同步计划中
6. 6.6网络同步：客户端预测、回滚与延迟补偿计划中

游戏算法
图解

先看懂，再写代码

演示就是代码

拿来就能用

目录

基础工具

寻路

碰撞检测与物理

游戏 AI

程序化生成

动画与表现

架构、性能与网络