经典游戏算法精华整理

简介：
本书精选并深入剖析了多种经典游戏算法，旨在为游戏开发者和计算机科学爱好者提供宝贵的学习资源与灵感。 A*寻路算法初探 长久以来我都知道A*算法的存在，但从未深入研究过它的原理或代码实现，只是对其有一个模糊的概念。这次决定从头开始学习这个被广泛推崇的简单方法，并以此作为人工智能学习的第一步。 这篇文章以形象、简洁且风趣的语言介绍了这一复杂的寻路算法，帮助读者逐步理解其基本原理和应用方式。通过阅读本段落后，相信每位读者都能对A*算法有更深的认识。（如果未能理解，则可能是翻译水平有限所致） 我们从头开始探索... ### 搜索区域 假设有人需要从点A移动到被墙隔开的B点（如下图所示）。绿色表示起点A，红色是终点B，蓝色方块代表中间障碍物。 [图1] 首先注意到的是搜索区域已被划分成方形网格。通过这种方式简化了路径寻找的过程，使得整个问题可以转化为处理一个二维数组的问题。每个单元格被标记为可通行或不可通行，并且最终的路径将由一系列连接这些单元格的节点构成。当一个人移动时，他们从一个节点中心走到另一个节点中心直到到达目的地。 ### 开始搜索 在A*算法中，我们通过从起点向外扩展来寻找最短路径。具体步骤如下： 1. 以点A作为起始位置，并将其加入到“开启列表”里。“开启列表”的作用类似于购物清单，它包含了所有需要进一步检查的节点。 2. 寻找起点周围的可通行方格（忽略有墙、水等不可通过地形），并将这些方格也添加进开启列表。同时保存点A作为它们的父节点信息。 3. 将起始位置从“开启列表”中移除并加入到“关闭列表”，表示不再需要检查。 此时，你应该能看到如下结构：起点被浅蓝色边框标记，并且所有相邻可通行方格都在开启列表内（用浅绿色边框标示）。每个节点指向其父节点的箭头以灰色显示。[图2] ### 选择路径 在A*算法中，我们通过计算F值来决定下一步搜索哪个位置： - **G** 是从起点到当前节点的实际移动成本。 - **H** 是一个启发式估计，表示剩余距离的成本。 公式为：`F = G + H` 其中： - 水平或垂直方向的移动耗散设为10，对角线方向则为14。这简化了计算同时保持了一定精度。 - 计算H值时我们使用曼哈顿方法（忽略障碍物），即从当前节点到目标节点沿水平和垂直路径的距离之和。 ### 继续搜索 为了继续进行搜索： 4. 选择开启列表中F值最低的方格，并将其移至关闭列表。 5. 检查所有相邻未检查过的可通行方格，将它们加入开启列表并设置当前节点为新添加节点的父亲。 6. 如果一个已经存在于开启列表中的邻居可以通过新的路径到达且G值更小，则更新其父亲信息和相关成本。 通过上述步骤不断重复直到找到终点或搜索空间耗尽。