游戏开发中的人工智能复习指南

本文档仅供个人复习使用，如需转载，请注明出处：http://blog.csdn.net/hcbbt/article/details/42815479

参考教材：《游戏开发中的人工智能》

关键知识点

1. 移动算法
   
   
   
   • Bresenham算法用于直线绘制，拦截算法用于目标追踪。
     

     // Bresenham算法示例
     if (deltaCol > deltaRow) {
         fraction = deltaRow * 2 - deltaCol;
         while (nextCol != endCol) {
             if (fraction >= 0) {
                 nextRow += stepRow;
                 fraction -= deltaCol;
             }
             nextCol += stepCol;
             fraction += deltaRow;
             pathRow[currentStep] = nextRow;
             pathCol[currentStep] = nextCol;
             currentStep++;
         }
     } else {
         fraction = deltaCol * 2 - deltaRow;
         while (nextRow != endRow) {
             if (fraction >= 0) {
                 nextCol += stepCol;
                 fraction -= deltaRow;
             }
             nextRow += stepRow;
             fraction += deltaCol;
             pathRow[currentStep] = nextRow;
             pathCol[currentStep] = nextCol;
             currentStep++;
         }
     }
     

     
     

     // 拦截算法示例
     void DoIntercept() {
         Vector u, v;
         bool left = false, right = false;
         Vector Vr = Prey.vVelocity - Predator.vVelocity;
         Vector Sr = Prey.vPosition - Predator.vPosition;
         double tc = Sr.Magnitude() / Vr.Magnitude();
         Vector St = Prey.vPosition + (Prey.vVelocity * tc);
         u = VRotate2D(-Predator.fOrientation, (St - Predator.vPosition));
         u.Normalize();
         if (u.x <-_TOL) left = true;
         else if (u.x > _TOL) right = true;
         Predator.SetThrusters(left, right);
     }
     

     
     
   
   
   • 移动模式包括矩形、巡逻和基于物理模拟的移动。
   
   
   
   


2. 群聚行为
   
   
   
   • Reynolds群聚算法的核心在于凝聚、对齐和分隔规则。
   
   
   • 邻近单位的数量由视野角度和视野半径决定。
   
   
   • 避障策略涉及在单位前方设置虚拟触角，检测到障碍物时调整方向。
   
   
   • 领头者机制用于引导群体移动。
   
   
   
   


3. 势函数
   
   
   
   • Lenard-Jones势函数用于模拟吸引和排斥力。U = - A / (r^n) + B / (r^m)
   
   
   • 导数形式为：F = - nA / (r^(n+1)) + nB / (r^(m+1))
   
   
   • A、B分别代表引力和斥力的强度，n、m为衰减指数。
   
   
   • 应用场景包括追逐、闪躲、避障和群集。
   
   
   
   


4. 路径寻找
   
   
   
   • 基本路径寻找方法（略）
   
   
   • 随机移动避障的优势在于灵活性。
   
   
   • 绕行障碍物的技术包括线段绕行和视线绕行。
   
   
   • 面包屑算法通过记录玩家位置并跟随足迹实现导航。
   
   
   • 沿道路行走根据权重选择路径。
   
   
   • 航点寻径利用节点表进行路径规划。
   
   
   
   


5. A*算法
   
   
   
   • A*算法结合了广度优先搜索和优先队列，适用于复杂的路径规划。
   
   
   • 地形成本影响路径选择。
   
   
   • 影响力映射用于动态调整路径成本。
   
   
   
   


6. 脚本AI
   
   
   
   • 脚本语言简化了特定任务的编程。
   
   
   • 脚本AI由语言和引擎组成。
   
   
   • 堆栈机是脚本语言虚拟机的基本形式，包括虚拟机、堆栈和指令指针。
   
   
   • 实例展示了如何描述属性、行为和事件。
   
   
   
   


7. 有限状态机(FSM)
   
   
   
   • FSM是一种行为模型，由状态、转换和动作组成。
   
   
   • 状态转换通过条件判断来实现。
   
   
   • FSM可以看作是有向图。
   
   
   • 状态与转移函数通常通过switch语句实现。
   
   
   
   


8. 模糊逻辑
   
   
   
   • 模糊逻辑处理不确定性和模糊性，使用[0,1]区间上的隶属度函数。
   
   
   • 模糊化、模糊规则生成和反模糊化是模糊逻辑的主要步骤。
   
   
   • 模糊逻辑与布尔逻辑的区别在于运算规则、隶属函数和模糊公理。
   
   
   • 反模糊化方法包括寻找几何中心和单值输出隶属度函数。
   
   
   
   


9. 规则式AI
   
   
   
   • 规则式AI是一组if-then规则，用于推理和决策。
   
   
   • 规则系统由工作记忆和规则记忆组成。
   
   
   • 演绎法通过匹配规则和事实来解决问题。
   
   
   • 归纳法则通过匹配结果来推导规则。
   
   
   
   


10. 概率论与贝叶斯技术
    
    
    
    • 概率论基础包括古典概率和贝叶斯网络。
    
    
    • 贝叶斯网络由网络结构和条件概率表组成，用于表示随机变量之间的关系。
    
    
    • 先验概率、后验概率和条件概率是贝叶斯分析的关键概念。
    
    
    • 贝叶斯公式用于更新概率估计。
    
    
    • 推理方法包括因果链、预测推理、共通成因网络和共通结果网络。
    
    
    • 预测和诊断算法用于计算特定节点的概率。
    
    
    
    


11. 神经网络
    
    
    
    • 神经网络模拟人脑的工作方式，具有非线性逼近、鲁棒性和并行处理能力。
    
    
    • 前馈神经网络通过权重调整和激活函数进行学习。
    
    
    • 监督学习和非监督学习是两种主要的学习方式。
    
    
    • 训练过程包括权重初始化、前向传播、误差计算和权重调整。
    
    
    • 反向传播算法通过梯度下降法最小化误差。
    
    
    
    


12. 遗传算法
    
    
    
    • 遗传算法模拟自然选择过程，通过选择、交叉和变异生成新的解决方案。
    
    
    • 种群、个体、基因和染色体是遗传算法的基本概念。
    
    
    • 轮盘赌算法是一种常见的选择方法。
    
    
    • 简单遗传算法通过迭代过程逐步优化解决方案。