基于群智能的NPC行为建模研究

魏凌华,张栋冰,范 祺

（淮北师范大学 计算机科学与技术学院，安徽 淮北 235000）

自1956年正式提出以后，人工智能［1］获得极大的发展，成为一门交叉前沿的学科，在多个领域得到应用，特别是在游戏中的应用，极大地提高游戏的可玩性，这些技术包括：有限状态自动机，、脚本设计、基于规则的人工智能和系统、人工生命、决策树、遗传算法［2-4］等.

其中有限状态机（Finite State Machine，简称FSM）是最常见的人工智能技术之一，有限状态机被广泛地应用于游戏［5-6］设计研究中，有限状态机技术极大地提高了游戏中NPC（非玩家角色，Non-Player Character）的智能程度，但在NPC之间并没有协同［7-9］能力，这极大地降低游戏的可玩性.

1 相关知识

1.1 有限状态机概念

FSM是表示有限个状态以及在这些状态之间转移和动作等行为的数学模型，在给定输入集IN和状态集SN，一旦输入in和状态sn确定，通过状态转移函数T，则能确定下一个状态sn+1和输出o+1.它把复杂的行为抽象为多种状态，且不同状态在一定的条件下可以相互转移.

1.2 群智能概述

群智能（Swarm Intelligence）作为人工智能的一个重要分支，最初是受社会性昆虫的集体行为的启发而提出的，群智能［10-11］是一种有限智能个体表现出来的集体智能方法，最早由多瑞哥等于1999年在《群智能：从自然到人工系统》中首先正式提出，其算法在众多领域得到广泛的应用.

群智能中最经典的算法有蚁群算法、粒子群算法以及其他一些算法，这些算法在旅行商问题、工业问题、生物信息学问题［12-14］等众多领域取得了非常好的效果.这些算法都体现协同处理的优势，实验表明在自然界中动物之间存在多种通讯方式，包括物理和化学刺激，其中物理通讯有光、声音、压力，对应于视觉、听觉和触觉通讯，化学的刺激对应于嗅觉和味觉的化学通讯［15］.

在自然界中，觅食、栖息地选择、迁徙以及竞争等动物的本能行为，是为了更好的生存，特别是对具有社会性的昆虫.社会性昆虫具有高度发达的社会组织，其重要特征就是分工与合作.在蜜蜂、蚂蚁、鸟类以及鱼类等群居性动物中表现尤为明显.

作为一个智能体应该具备两个方面的能力，第一，自控能力.对自己的行为和状态具有控制权；第二社交能力.能与其他主体进行交互交流和沟通，可以实现合作、协商和竞争等行为.

1.3 游戏中的知识定义

定义1人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支.其近期的主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术.

定义2群智能：任何一种受昆虫群体或其他动物社会行为机制启发而设计出的算法或分布式解决问题的策略均属于群智能范畴.

设NPC的状态有S=｛巡逻P，进攻A，逃跑E｝；T=｛敌人出现1；敌人死亡或逃跑2；NPC处于危险状态3｝.斜线的左边表示输入，斜线的右边表示输出，初始状态从P开始.当前状态sn和条件t的组合指示出下一个状态sn+1，从图1中可以看出状态转换的过程.

图1 NPC的三状态机

鉴于系统设计的需要，本系统中设置以下两条规则.

规则1：系统中每种NPC都可以和其他NPC进行通信；

规则2：系统中所有的NPC状态变化都遵循FSM规则.

2 基于群智能的协同算法

在没有通信和交流的能力之前，NPC各自为战，没有合作的功能，这极大地降低游戏的可玩性和模拟真实情况的能力.

算法NPC-Coop

＜1＞NPC处于巡逻状态；

＜2＞NPC遇到敌人，读取敌人信息，判断敌人状态和自我状态；

＜3＞NPC开始进攻，做以下选择：

（1）开始进攻目标；

（2）根据规则1，在进攻的同时向其他NPC发出请求支援信息；

（3）根据规则2，所有参与的NPC根据自身状态，直至所有参与的NPC全部死亡或撤退或敌人撤退或死亡；

＜4＞本次战斗暂时结束.

3 量化分析

3.1 设计分析

根据NPC-Coop算法，本文在输出函数中加入通信的能力，以此提高协调能力.

图2 NPC的新三状态机

O’=｛攻击A，巡逻P，逃跑E，盟友通信M｝，此时的状态见表2.

表2 NPC的新状态

根据图2和图1比较可以看出，NPC状态没有增多，也没有提高状态转移表的复杂度，唯一变化的是NPC多了通信的能力.

3.2 时间比较

在时间方面，主角消耗的时间主要包括搜索时间和作战时间.

设Search（t）为搜索时间，Fight（t）为作战时间，FullTime（t）为主角消耗总时间；

假设主角消灭一个NPC需要K秒，寻找一个NPC需要M秒，NPC的数目为N个.

为了做一个平均时间测试，做两个假设前提：

前提1：巡逻时，不同NPC不会同时和其他NPC出现在一个地方；

前提2：主角生命值无限大.

在NPC-Coop算法下，会出现两种较为极端的情况.

第一：最好情况.在主角寻找到并消灭第一个NPC的时候，其他NPC都接收到指令并赶到现场，则主角消灭所有NPC的时间N*K+M秒；

第二：最差情况.主角需要找到每个NPC并且分别消灭每个NPC的时间N（K+M）秒；

由此可以看出，在时间上随着NPC数量的增加，主角节约的时间越多，在相同NPC数目下最好情况和最坏情况时间比N（K+M）/（N*K+M），当N≫M时两者时间相差为一倍多.

假设K为2，M为6，由图3可以看到两者时间的对比情况.

图3 时间对比

通过NPC-Coop算法，增加NPC之间的通信能力和智能程度，提高游戏的可玩性.

4 结语

通过协同算法提高NPC之间的协同能力，完成单个NPC无法完成的任务，也优化NPC的智能程度，并以此提高游戏的可玩性.希望可以为其他游戏的开发提供一些有意义的借鉴.由于系统在实际设计时需要考虑较多的参数，因此游戏的数值平衡、NPC的通信方式等问题还有待完善.

［1］史忠植.高级人工智能［M］.3版.北京：科学出版社，2011.

［2］BARAS J S，JAMES M R.Robust and risk-sensitive output feedback control for finite state machines and hidden markov models［J］.To Appear J Math Systems，Estimation and Control.

［3］胡喜玲，李洪波，胡俊.基于自适应混沌遗传算法的路径规划［J］.计算机工程与应用，2013，49（9）：68-73.

［4］李志强，胡晓峰，杨雪生，等.虚拟环境中大规模群体行为建模研究进展［J］.计算机工程与应用，2008，44（8）：45-48.

［5］朱全银，章慧，孙文杰.基于J2ME技术的手机网络游戏研究与开发［J］.计算机工程与应用，2008，44（32）：76-78.

［6］董改芳，许道云.游戏中寻找路径的改进算法［J］.计算机工程与应用，2009，45（23）：38-39.

［7］HILLS D.Co-evolving parasites improves simulated evolution as an optimization procedure［J］.Physica D，1990，42（1）：228-234.

［8］PAREDIS J.Coevolutionary computation［J］.Artificial Life，1995，2（4）：355-375.

［9］董红斌，黄厚宽，印桂生，等.协同演化算法研究进展［J］.计算机研究与发展，2008，45（3）：454-463.

［10］余建平，周新民，陈明.群体智能典型算法研究综述［J］.计算机工程与应用，2010，46（5）：1-4.

［11］BLUM C，MERKLE D.群智能［M］.龙飞，译.北京：国防工业出版社，2011.

［12］ONWUBOLU G，CLERC M.Optimal path for automated drilling operations by a new heuristic approach using parti⁃cle swarm optimization［J］.International Journal of Production Research，2004，42（3/1）：473-491.

［13］李德福，郭海湘，刘龙辉，等.改进型粒子群优化算法求解车辆路径优化问题［J］.计算机工程与应用，2012，48（20）：216-223.

［14］冀俊忠，黄振，刘椿年，等.基于多粒度的旅行商问题描述及其蚁群优化算法［J］.计算机研究与发展，2010，47（3）：434-444.

［15］孙儒泳.动物生态学原理［M］.3版.北京：北京师范大学出版社，2001.