数学建模—植物大战僵尸.doc

数学建模竞赛论文 论文题目： 人机游戏中的数学模型 队 长： 学号： 学院： 队员1： 学号： 学院： 队员2： 学号： 学院： 联系电话： 2012 年 05月 01日承 诺 书我们仔细阅读了2012年全国大学生数学建模竞赛东华理工大学预选赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛队选择的题号是（从A/B/C中选择一项填写）： C 参赛队员(打印并签名) ： 所属院系（请填写完整的全名）： 1. 签名: 院系: 2. 签名: 院系: 3. 签名: 院系: 日期： 2012 年 月 日题 目 人机游戏中的数学模型 关 键 词 植物大战僵尸 线性规划 Lingo软件 摘 要：随着计算机网络技术的不断发展，计算机游戏在社会和生活中享有特殊的地位。与网络游戏不同，植物大战僵尸这种人机游戏通过其易学性、趣味性和界面友好性等特点使玩家百玩不厌。本文从颇有新意的角度出发，重点研究了“植物大战僵尸”的游戏问题。针对不同的游戏规则，通过数学建模的方法，为玩家提供各种既满足设计要求且又十分刺激的游戏方案。“植物大战僵尸”游戏中有三个角色：向日葵、豌豆荚和一群僵尸。向日葵产生阳光，阳光可以种植向日葵和豌豆荚，豌豆荚发射的一定量豌豆击中僵尸后让僵尸消亡。通过构建模型，在豌豆荚发射豌豆打击僵尸的过程中，使豌豆荚和向日葵不被僵尸吃完，也不会让僵尸走到最左端。 针对问题二提出的游戏规则，本文利用相遇问题的原理和线性规划，求出有随机因素的合理方案；应用提出的游戏规则，建立模型，求出问题三的最优方案；在此基础上，利用Lingo软件求得问题四的最优方案。 一、问题重述 植物大战僵尸是由PopCap Games为Windows、Mac OS X及iPhone OS系统开发，并于2009年5月5日发售的一款益智策略类塔防御战游戏。现在只考虑有三种角色：向日葵、豌豆荚和一种僵尸。向日葵产生阳光时，要点击阳光并收集存储，否则阳光过一段时间会消失。种植向日葵和豌豆荚需要花费阳光；豌豆荚当其所在格或右侧有僵尸存在时就发射豌豆，并豌豆数量无限；豌豆向右飞行且打同一路线上的僵尸。豌豆不受向日葵和豌豆荚的阻挡，但不能射穿僵尸；僵尸只从屏幕最右边产生，沿着直线从右向左行进和吃掉沿途遇到的向日葵和豌豆荚，但会被豌豆打死立即消失。僵尸走到屏幕最左边，则计算机获胜，游戏结束。屏幕上的游戏场地是横平竖直、大小相等的网格，一个格内只能种植一株豌豆荚或向日葵，但可以有任意多个僵尸。 假设僵尸3 步走一个格，豌豆荚发射豌豆的频率与僵尸的步频相等，豌豆飞行6 格的时间僵尸走一步，僵尸被9 粒豌豆打中立即消亡。僵尸走到豌豆荚或向日葵所在的格开始吞噬，用走3 步的时间将其吃掉。向日葵产生1 朵阳光所用时间僵尸恰好走4 个格，僵尸走1 格的时间不点击阳光，阳光就会消失。2 朵阳光可以种植1 株向日葵，4 朵阳光可以种植1 棵豌豆荚。场地只有从左至右的9 个格。 1. 将以上假设用更简洁明了的方式进行复述； 2. 场地只在最左边的1 个格内有豌豆荚，没有向日葵和阳光。问最小多大间隔产生1 个僵尸，计算机永远不会赢？ 3. 场地在最左边的若干格内种有豌豆荚，没有向日葵和阳光，等间隔每次产生1 个僵尸。问最少种几棵豌豆荚，使产生僵尸的间隔最小，而计算机永远不会赢。 4. 假设游戏开始时有6 朵阳光，每次产生1 个僵尸。请设置最佳的种植方案和僵尸产生方案，使计算机永远不会赢，并且游戏紧张有趣。 二、问题分析 针对问题一，我们可用简洁明了的语言将以上的假设进行复述。 针对问题二，因为每次产生僵尸的间隔属于非负数，故我们有如下三种类型的讨论：第一种：假设每次产生僵尸的间隔是不一样，所以同一时刻可以产生两只僵尸，即产生1个僵尸的最小间隔应为0，而在这种情况下计算机永远不会应赢；第二种：假设每次产生僵尸的间隔是一样的且僵尸的数量是无穷多的，如果后面的僵尸死在前一只僵尸的前面的话，那么后面的僵尸死的位置就会在前一只死的位置的前面，以此类推，终有一只僵尸会到达豌豆荚所在的格子里并把豌豆荚吃掉，这是计算机就胜利；为了使计算机永远不赢且间隔最小，后面僵尸应该在前一只僵尸死后才出来且每只僵尸要死在同一个位置，通过相遇问题方法的解决，我们可以算出第一只僵尸死的位置是在8.8421步，为了使每只僵尸死在同一个位置，所以间隔最小应取9步，才能使计算机永远不赢。第三种，假设每次产生僵尸的间隔在0步与9步之间，那么后一个僵尸总消亡在前一个僵尸的前面，以此类推终有那么一个僵尸会威胁着第9格，使得计算机不可以永远不会赢，故特以僵尸的个数随机确定在20到25之间，以目标规划模型来求得。 针对问题三，我们把场地在最左边种豌豆荚的所有可能的格数的运用枚举法，所对应的最小间隔求出来，在利用表格的直观性，就可以得到：使产生僵尸的间隔最小且计算机永远不会赢，所种的豌豆荚的最少棵数为5棵。针对问题四，我们从以下两大类考虑：种植三株向日葵、种植一株向日葵和一棵豌豆荚。三、模型假设与约定 1、本文以僵尸走一步的“步”为基本单位，而不是场地的“格”。 2、本文在需对僵尸的个数有约束，约定其范围在20到25之间，并由计算机随机确定。3、阳光全都被点击到，没有损少。=四、符号说明及名词定义符号符号说明僵尸走一步所用的时间（）第个僵尸产生即已准备被豌豆击中的位置（单位为：步）（）第个僵尸被第9个豌豆击中消亡的位置（单位为：步） （； ；且） 第个僵尸与第（即）个僵尸之间的间隔（单位为：步）(特别说明:为游戏开始到第一个僵尸出现的间隔）第个僵尸第个僵尸从产生到消亡的位置变化第次增加种植的向日葵棵树第次增加种植的豌豆荚棵树从左到右第格五、模型建立与求解5.1 针对问题一：假设场地只有从左到右的9个格，僵尸每走一步的速度为，豌豆荚发射豌豆的频率与僵尸的步频相等，豌豆飞行一步的速度为，僵尸被9粒豌豆打中立即消亡。僵尸走到豌豆荚或向日葵所在的格开始吞噬，将其吃掉所用3t时间。向日葵产生1朵阳光所用时间为，后阳光就会消失。2朵阳光可以种植1株向日葵，4朵阳光可以种植1棵豌豆荚，那么可得表1-1。表1-1 复述假设屏幕上的游戏场地情况1行从左到右的9个格僵尸走一步所需时间豌豆飞行一步所需时间僵尸被豌豆击中至消亡所需豌豆颗数9僵尸吞噬豌豆荚或向日葵所需时间31株向日葵产生1朵阳光所用时间为不点击阳光则消失所需时间3种植1株向日葵所需阳光朵数2种植1棵豌豆荚所需阳光朵数45.2 针对问题二：，那么根据题意可考虑。5.2.1 当时，即第（即）个僵尸与第个僵尸同一时刻产生，那么因豌豆不能射穿僵尸，则只有在第个僵尸消亡后，第（即）个僵尸才开始面对被豌豆击中的情形，即，=16.4211那么当另一组（两个僵尸）出现的间隔若是均大于前一组僵尸的产生的到消亡的位置变化，即是大于17步，则计算机永远不会赢。5.2.2 当时，则必然出现第个僵尸被打中消亡才产生第个僵尸，那么，即是无穷个僵尸均是进行第一个僵尸的被打中消亡的循环情况，并有，如此计算机永远不会赢；但无法满足游戏本身的所应具有的趣味性和难度性。5.2.3 当时，取得最小为多少，计算机永远不会赢？5.2.3.1 运用“相遇问题”的原理求第一个僵尸被第一到第九颗豌豆击中的位置，。第一个僵尸从准备被击中到被第9个豌豆击中消亡这一整个过程中，豌豆荚发出的豌豆击中僵尸所进行的飞行时间是一个以僵尸离豌豆荚的距离位置递减为自变量的函数。由于豌豆荚发射豌豆的频率与僵尸的步频相等，且豌豆飞行6 格的时间僵尸走一步，那么可知僵尸每走一步的速度为，豌豆飞行一步的速度为，又僵尸与豌豆飞行的速度均不变，求僵尸被豌豆击中的位置即是求僵尸与豌豆的相遇问题。即可得 =，=，此即为第一个僵尸从准备被击中到被第9个豌豆击中消亡的位置变化为，5.2.3.2 确定第二个僵尸要比第一个僵尸死得更快的函数=。第二个僵尸是与第一个僵尸有时间或是说位置的间隔的，这导致的第二个僵尸距离豌豆荚就越近，那么第二个僵尸就死得越快，即第二个僵尸从准备被击中到被第9个豌豆击中消亡的位置变化就越小。另外，第二个僵尸在第一个僵尸承受豌豆击中中获得安全向左前进的时间，即其准备被击中的位置，并有是第一个僵尸消亡位置（即是）-第一、二个僵尸的间隔的取整，即可表达为=。画出函数的图像为（图-1）图-1利用、来检验这个模型的准确性和可靠性是较完美的。以此可确定第个僵尸比第个僵尸要消亡得更快，但终有那么一个僵尸走到豌豆荚所在格并将其吃掉。5.2.3.3 运用目标规划模型确定最小间隔。假定为游戏中所有僵尸的个数，并由计算机在区间中随机选取确定。即，这么做的原因有两个，一是模型中的僵尸需为有限，但不应太大，会使得游戏的进行时间太过长久，降低其中的趣味性；二是由计算机随机选取确定，可以加入影响游戏时间等，但却不影响结果的随机因素。综上所述，可以利用目标规划来确定最小的间隔。min , s.t 求得，95.3 针对问题三：假设在场地最左边种植1棵豌豆荚时，则需要它发射9粒豌豆才能把僵尸打死。第1个僵尸死的位置是第8步和第9步之间（如下图，同理下面的情况也可用图表图-2所示），为了保证计算机永远不会赢，只需僵尸等间隔为9步。图-21、 假设在场地最左边种植2棵豌豆荚时，第1个僵尸死的位置是第4步和第5步之间，为了保证计算机永远不会赢，只需僵尸等间隔为4步。2、 假设在场地最左边种植3棵豌豆荚时，第1个僵尸死的位置是第3步和第4步之间，为了保证计算机永远不会赢，只需僵尸等间隔为3步。3、 假设在场地最左边种植4棵豌豆荚时，第1个僵尸死的位置是第3步和第4步之间，为了保证计算机永远不会赢，只需僵尸等间隔为3步。4、 假设在场地最左边种植5棵豌豆荚时，第1个僵尸死的位置是第2步和第3 步之间，为了保证计算机永远不会赢，只需僵尸等间隔为2步。5、 假设在场地最左边种植6棵豌豆荚时，第1个僵尸死的位置是第2步，第2个僵尸死的位置是第2步和第3步之间，为了保证计算机永远不会赢，只需僵尸等间隔为2步。6、 假设在场地最左边种植7棵豌豆荚时，第1个僵尸死的位置是第2步，第2个僵尸死的位置是第2步，第3个僵尸死的位置是第2步和第3步之间，为了保证计算机永远不会赢，只需僵尸等间隔为2步。8、 假设在场地最左边种植8棵豌豆荚时，第1个僵尸死的位置是第2步，第2个僵尸死的位置是第2步，第3个僵尸死的位置是第2步，第4个僵尸死的位置是第2步和第3步之间，为了保证计算机永远不会赢，只需僵尸等间隔为2步。 9、 假设在场地最左边种植9棵豌豆荚时，第1个僵尸走1步就要吞噬豌豆荚，就回到8棵豌豆荚的情况了。综上所述，可以得到以下表格： 表1-2 豌豆荚的棵数与最小间隔的关系豌豆荚的棵数123456789最小的间隔943322222由格可以得到，最少种5棵豌豆荚，使产生僵尸的间隔最小，而计算机永远不会赢。5.4、针对问题四：我们从下列的树状图可知种植1株向日葵和1棵豌豆荚，即种向日葵，种豌豆荚是最优方案。计算机会赢1株向日葵和1棵豌豆荚3株向日葵向日葵，种向日葵，种豌豆荚到时，消亡到时，向日葵生产1朵阳光计算机不会赢到时，消亡计算机赢6朵阳光种向日葵当向日葵生产一次阳光时，出现，直至走到计算机赢当向日葵生产一次阳光时， 出现计算机不会赢六、模型检验针对问题二建立的线性规划，可用之前的前两个模型即和中的和来验证，可知该模型具有较好的合理性。七、模型评价内容要点： 7.1优点（1） 能充分考虑各种情况，并从中发现规律，利用规律很好解决问题；（2） 文字分析、函数式、表格以及图像交错穿插，相辅相成，使得本文更有说服力；（3） 充分利用数据来说明解决该问题。（4） 模型合理简单易懂 7.2、缺点（结合模型假设）（1） 计算冗长 7.3、改进方法八、参考文献1 冯杰，黄力伟，王勤，尹成