教学游戏ＡＩＦＳＭ实现策略研究传奇的

时间:2011-08-17 文章来源:投稿人气: 次

　　24第27卷第4期2008年12月《新疆师范大学学报》(自然科学版)JournalofXinjiangNormalUniversity(NaturalSciencesEdition)VoL27。No．4Dec．2008教学游戏AIFSM实现策略研究潘伟民，彭成(新疆师范大学数理信息学院，新疆乌鲁木齐8j0054)摘要：FsM是游戏中重要的人工智能实现的技术，具有简单，实用。求解能力强，具有计算额外开销小，并且能够与神经元网络．模糊逻辑混合使用的优点．文章以一个教学游戏为例，说明FSM的实现方法，展望了复杂系统的实现方法．关键{司：教学游戏}有限状态机I模糊逻辑-神经网络中图分类号：TP311．5文献标识码：A文章编号：1008?9659(2008)04-0024-031FSM的概念与方法FSM(FiniteStateMachine)理论自上世纪40年代提出后，尤其是近十年来伴随着计算机科学的迅猛发展，FSM理论已经在计算机科学和信息科学等许多学科领域得到了长足发展和应用，FSM理论是系统理论的一部分，和该理论密切相关的理论包括：信息论、控制论及柔性制造系统理论。FSM是一个有限状态数的装置，它的每一个状态都包涵FSM对应特定条件的完整描述，FSM只能根据状态机目前的状态以及输入状态转换到另一个状态。一个FSM包涵有限个状态，但是任意时刻只能有一个状态，状态的变化是事件驱动的，实现状态机设计的关键是在它的状态空间中找到状态转换的轨迹。教学游戏中的人工智能可以看作一个典型的FSM，在该系统中，实体的数量有限且各实体的状态是有限的，因此系统的状态空间是有限维的，所以用FSM描述是完全可行的，对于一个有，1个实体的教学游戏系统，S=(已-，e2，“)，若实体白有P』种可能的状态，那么系统的可能的状态数为：Ns=Ⅱ岛。FSM分为Mealy型和Moore型两类，差别在于前者的输出是当前状态和所有输入信号的函数，后者仅仅是当前状态的函数，4种状态的状态图见图1和图2。考虑到教学游戏的复杂性，图中清晰的显示，本游戏Mealy型更适合，除非游戏的结构非常简单，智能状态呈线性结构可以采用Moore型。，，／～、、111001／一、：，／7一、、1，／??、、Ⅺ0000辽So≥==：==：文s1pxfl001(So：}=二==啾s1)、‘了F7，7’。
　　、、～‘f1。。，／’、、了F777、、、}1+，，770／0000ii{{0111000l{0}i}|，强l{。
　　哆／川、、1门1”，，×、／“、、1／7、’lX／1111《's3jAF====_j／。s2px，1001IS3厣=======tS2，j、一面1Mealy型状毒机一7圈2Mo泖型状态机状态圈对不同的状态机有不同的描述方式，描述方式的不同使得综合出来的门级网表也不同，因此必须要根据[收稿日期]z008一06一17[作者筒介]潘伟民(1963一)，男，新疆鸟鲁木齐人，硕士，副教授。主要从事计算机应用方向的教学与研究．第4期潘伟民等教学游戏A腰SM实现策略研究25具体的特性选择相应的描述方式r11。对于一个具体的状态机，描述的内容包括：(1)状态编码的描述；(2)状态机状态变量描述；(3)次态编码的描述；(4)输出描述。
　　该状态机在游戏程序设计需要注意的几个问题是：(1)类型定义：状态类型一般采用枚举类型，状态名可以任意选取传奇的，为程序设计方便名称最好带有解释性意义。状态变量可以定义为一维数组，便于信息传递。(2)状态的转换：因为状态机的下一状态取决于当前状态和当前输入信号值，可以使用case语句检查当前状态，然后使用i厂一娩e，t?PZse语句决定下一个状态。(3)王控程序：主控程序的目标是根据外部输入控制信号或当前状态值确定下一状态的走向，并完成下一状态的转换。2教学游戏中的FSM的建模与程序设计教学游戏人工智能的FSM模型可以采用有向图描述和实现，对于一个状态机而言，最简单的结构是两个状态好传奇，即主控时序和主控组合，必要时可以引进其它状态。和本游戏中的FSM采用一个有向图描述，见图3。对应的FSM的状态集合、状态转换见表1，状态输出定义见表2。FSM的实现方法很多，其组成部分一般都包括：状态及子状态描述；状态转移；转移条件；输入事件四部分。另外需详细考虑每个状态对象的表达，包括当前状态，转移关系和相关的创建和编辑操作；状态对象的链表大家，将所有状态链接为一个表，并提供相应的编辑和遍历操作；FSM的表达。我们采用的方法是：把状态对象的表达封装为FSMS类，它定义了一个状态数据元素以及向其他状态的迁移关系，还包括状态对象的基本操作(如添加、删除等)。
　　状态对象定义为一个双向链表，对应的数据项是每一个状态对象的指针及状态ID。FSM的表达封装为FSMC类，它在FSMs类和状态对象链表的基础上定义所有状态、当前状态以及输入事件。封装的基本操作主要包括：创建、删除FSM的状态；读取、设置FSM当前状态；修改FSM的状态转移关系和条件；设置当前的输入条件；根据目前的状态执行状态转移等。3FSM的验证和优化FSM的验证是游戏功能验证中的重要环节，FSM问题可以抽象圈3FSM有向圈表1PSM的状态集合、状态转换图输入壁垄墨堡兰!堡123SoS1S2S3S1s2S3so&SslS2SoSoSoSo表2状态输出图为一个有向图，FSM验证的实质是按照各种状态转移条件运行FSM，确认FSM能准确到达规定的各个状态，在对应的有向图中是一个遍历问题。
　　验证时有两个方面需要加以考虑，一是如何全面覆盖状态转移条件，二是如何提高测试效率，通过精心安排测试计划实现。可以采用EDPN生成测试用例，验证FSM的工作情况[扪．EDPN是对传统Petri网的改进，能更接近并更好地描述事件驱动系统。EDPN是一种多向图(P，D，S，In，Out)，包括三个节点集合P，D，S，以及两个输入输出函数集合In，Out。其中P是输人事件的集合；D是数据地点的集合；S是转移的集合；In是(PUD)×S的有序对偶集合；Out是S×(PUD)的有序对偶集合。当FSM状态高度内聚的时候，会出现路径爆炸以及死锬等问题，因此，验证的优化问题十分重要Is-4]。
　　路径爆炸是FSM系统每增加一个新的状态，其路径数量激增，引发MM路径(模块执行和消息交替序列)爆炸，导致验证困难。死锁是在事件驱动系统中，原子功能系统由静止点分开，遇到系统空闲以及等待端口输入输出时间触发时，就会出现死锁的情况，导致功能异常。路径爆炸和死锁等问题可以通过优化的方法加以觚一&s&s塑：三26新疆师范大学学报(自然科学版)2008年规避。
　　因为FSM可以抽象为有向图，我们可以利用成熟的图论技术对验证方法加以优化，比如，可以采用构造Euler回路实现FSM的遍历；其二，可以采用合适的算法(例如Dijkstra算法)选择最短路径；其三，采用相关的数学规划算法实现(例如选择矩阵)。此外，也可以借助自动化测试工具，制订好满足全覆盖的测试用例后，按照测试设计人员的测试用例录入脚本，进行自动化测试[副。此不赘述。4结论和改进FSM作为一种方法，具有易于理解，实现简单，调试容易，适用面广并且可以与其它技术混合使用等特点，成为游戏设计人工智能体现的重要工具，在“帝国时代”、“半条命”等网络游戏中得到了广泛应用[6]。但是该方法缺点也是明显的：问题求解结构差；大规模的问题求解的路径爆炸；需要预先确定所有的可能性；同题求解结果过于确定，缺少应有的变通等。因此，FSM仅仅适用与小规模和简单的智能需求方面。对于规模比较大的教学游戏可以采用模糊逻辑、决策树、神经网络乃至遗传算法等技术。模糊逻辑适合求解比较复杂的问题、求解非线性问题具有更好的灵活性和可变性，不适合简单问题求解。决策树具有强的鲁棒性在有数据噪声和部分缺失的状态下能很好工作，但是需要复杂的调整与训练。神经元网络适用于非线性，非确定性和灵活性问题求解，但是算法复杂。遗传算法具备很多优点，缺点是占用资源多，问题求解速度慢，不太适合实时性强的游戏场合。在规模比较大的教学游戏中，采用FSM和模糊逻辑结合构建模糊状态机是一种很有前途的方法。。参考文献：E1]孔键，等．基于VHDL的有限状态机的VHDL设计及优化[刀．计算机工程，2003．29(15)t73?78．E23BaurhfirC，DssouliR，AboulhamidEMAutomaticTestGenerationforEFSM--basedSyetom[OD／BL-]．httpl／／dteseennj．ne厶com．[3]HaraldRueB，eud．Fromsimulationtoverification(andBack)[A]．InlProceedingsofthe2003WinterSimulationConference，NewOr-leans。Loui$iana，20031888--896．[4]YevtushenkoNina，etaLMultieomponentdigitalcircuitoptimizationbysolvingFSMequationsFA]．InlEuromicroSymposiumonDigitalSys-tentsDesign，Balek--Antalya，Turkey，2003162?68．[5]张毅坤，等．基于UML状态图的类测试用例自动生成方法[刀．计算机工程与应用，2001，(01)；14．[63耿卫东。陈为编．计算机游戏程序设计[wO．北京。电子工业出版社，2005，274．ResearchofStrategyUseFSMMethodtoImplementationEducationalGames"AIPANWeimin，PENGCheng(CollegeofMathematics--physicsinformationxi,qiangNormalUniversity，Ururruli溉巧iang830054)Abstract：Abstract：FSMisanimportantgameartificialintelligencetechnique，whichissimple，prac-tical，solvingability，smalladditionalcostiscalculated，andwithneuralnetworks，fuzzylogic，n[1ixeduseadvantages．Inthispaper交流，aeducationalgameasanexampleofhowtheFSMmethod，lookedtotherealizationofcomplexsystems．Keywords：Educationalgames；FSM)Fussylogic；Nervousnetwork教学游戏AIFSM实现策略研究作者：潘伟民，彭成，PANWeimin，PENGCheng作者单位：新疆师范大学数理信息学院,新疆乌鲁木齐,830084刊名：新疆师范大学学报（自然科学版）英文刊名：JOURNALOFXINJIANGNORMALUNIVERSITY(NATURALSCIENCESEDITION)年，卷(期)：2008,27(4)参考文献(6条)1.YevtushenkoNinaMulticomponentdigitalcircuitoptimizationbysolvingFSMequations20032.耿卫东;陈为计算机游戏程序设计20053.张毅坤基于UML状态图的类测试用例自动生成方法[期刊论文]-计算机工程与应用2001(01)4.HaraldRueBFromsimulationtoverification(andBeck)20035.BourhfirC;DssouliR;AboulhamidEMAutomaticTestGenerationforEFSM-basedSyetem6.孔键基于VHDL的有限状态机的VHDL设计及优化2003(15)。

-------------------------------------------------------------------------------------------

上一篇：动员百位明星全面启动‘仙剑娱乐风暴’计划《仙剑Online》正式启
下一篇：1y011thePe

教学游戏ＡＩＦＳＭ实现策略研究传奇的

最近更新文章