第六章地图布置与地图相关算法

1、第六章地图布置与地图相关算法第六章 地图布置与地图相关算法 教学提要 游戏地图的组成方式 几种常用的地图编码方式 扫雷游戏的编码与算法的实现掌握掌握Flash游戏中的地图编码及其算法游戏中的地图编码及其算法1 游戏地图的组成方式地图是许多游戏的重要组成。小游戏例如俄罗斯方块、各种棋类游戏、搬运工游戏等，大型游戏例如英雄无敌、魔兽争霸，无不与地图紧密关联。地图的组成： 地图元件编码数据 基于编码的算法右图是一款用 Flash制作的滚 方块游戏:1.1 地图的组成其地图（即游戏中的地板方块组合）的三个部分分为为： 地图元件：一个个的小地砖对象，他们都是同一个类的实例，只是一些属性值（如位置，显示效

2、果和编码值）不同而已。 编码数据：显然这个地图应该采用二维数组进行编码。在一个M*N的二维数组中，1表示有地砖，0表示没有地砖，就可以准确无误地表示出这个地图的实际情况。 基于编码的算法：根据编码数据创建地砖实例并平铺在舞台上就是一个算法，这是具有整齐排列特征的地图常用的做法。先获得方柱所在的位置编码，根据编码在地图编码数据中判断这个位置的值是否都为1，如果是，就表示这个方柱是“稳固”的，否则就是“不稳”的，这就是一个简单的基于编码的算法的描述，它用来支持游戏的运行逻辑。2 几种常用的地图编码方式 地图元件的制作采用角色设计思想进行设计即可。所以地图设计的一个关键就是进行地图编码。地图编码的作

3、用：在地图元件与算法之间建立一个最简的沟通桥梁。基于编码方式设计算法，然后通过编码找到对应的元件； 从元件出发获取其编码值，然后用这个编码值参与算法过程。 例如：扫雷游戏，可以建立一个二维数组，每个数据项存储一个方块的引用，这样二维数组就是游戏的编码方式。然后基于二维数组索引（即数组的下标）找到每个方块，同时，在每个方块中定义变量indexX和indexY，用于记录其索引值，当点击了某个方块之后，可通过读取这个方块的索引值来确定它在二维数组中的位置。好的地图编码算法应该是既满足记录数据的需要，又是最简的。 2.1 常见的地图编码方式 一维数组（队列，堆栈） 例如开心碎碎冰游戏2.2 常见的地图

4、编码方式 二维数组 例如炸方块游戏 2.3 常见的地图编码方式 变形的二维数组编码方式 例如蜂窝状地图，这样的地图每个格子有六个方向的通路。也有可能是菱形或者六边形，如下图所示：2.4 常见的地图编码方式完全可以参考二维方阵的编码方法。上面两张图，可以分别编码成4*8和7*7的方阵。如下图所示：于是我们又可以用一个二维数组保存地图信息了。基于不同的编码规则，就要使用不同的算法规则。例如采用菱形边编码规则，那么当考察第i行第j列位置的通路时，需要判断的六个位置的编码如下图所示：2.5 常见的地图编码方式 非二维阵列地图的阵列化事实证明，二维阵列是游戏地图非常简单、非常有用的编码与索引方式。如果可

5、能，应尽量采用阵列编码，以便获得阵列计算的简单性。例如九子游戏，每个位置的编码不仅要起到互相区分的作用，还要能够以此判断棋子之间是否同在一条连线上。如果仅是从上到下，从左到右对位置逐个编码，则难以实现同线判断。但事实上，这个地图还是有规律可循的，可以将地图理解成是一个二维阵列上分布的点。这样我们又可以使用二维数组来存储索引每个位置单元了，此时同线与否就再明显不过了。 2.6 常见的地图编码方式 用图进行地图编码 图是一种数据结构，它指出了每个节点的信息以及它的相邻点。 假如游戏中有如下的一张地图： 由于其连线的不规则性，不能采用简单的阵列化编码。2.6 常见的地图编码方式 方法是先对位置按顺序

6、编码，如下图所示： 然后记录每个节点的相邻节点，如右表所示： 这样就可以既简单又完全地表示这张地图。节点编码节点编码相邻节点相邻节点01，2，310，2，4，520，1，3，530，2，5，641，5，751，2，3，4，6，763，5，774，5，62.7 常见的地图编码方式 可以用一个一维数组存储位置数据，用一个二维数组表示位置之间的连线。 示例代码如下：/棋子信息，0表示没有棋子，1表示白棋，2表示黑棋var chesses=new Array(0,0,1,1,2,2,0,0);var path = new Array(8);path 0 = new Array(1,2,3);path

7、1 = new Array(0,2,4,5);path 2 = new Array(0,1,3,5);path 3 = new Array(0,2,5,6);path 4 = new Array(1,5,7);path 5 = new Array(1,2,3,4,6,7);path 6 = new Array(3,5,7);path 7 = new Array(4,5,6); 2.7 常见的地图编码方式 使用这种编码方式的好处是计算相邻棋子非常方便，例如下面的代码判断指定位置是否有指定一方的棋子相邻：function haveNeighbor(position:int,color:int):B

8、oolean for (var i = 0; ipathposition.length; i+) if (ppathpositioni = color) return true;return false; 小结 元件是游戏地图的展现，编码是游戏地图的结构，算法是地图功能的实现。 地图编码以简单有效为设计准则。 不管使用何种编码方式开发游戏，最好都先画好编码图，甚至打印出来放在电脑旁以便随手翻阅。2.8 常见的地图编码方式常见的地图编码方式3 扫雷游戏的编码与实现 内容包括： 编码与索引 布置雷区 随机分布地雷 计算单元格周围雷数 无雷区自动扩张的设计 判断地雷是否已经全部扫除 人机交互部分的设

9、计 设置难度级别 游戏结束时显示所有地雷3.1 方块角色的设计很明显，扫雷游戏中的每一个方格，都是一个雷区单元角色的实例。这个雷区单元应该包含如下的成员：假设我们已经完成这个角色的设计，并将其链接为Cell。 成员成员成员描述成员描述discovered是否被打开了haveMine是否有地雷haveFlag是否有旗帜i、j雷区单元所在的位置各个视觉界面showMine()显示地雷界面showExplode()显示地雷爆炸界面showInit()显示初始化时的界面showAround(num)显示地雷被排除的界面flag()显示/隐藏旗帜3.2 编码与索引 首先，对每个单元进行编码，以便能够通过

10、特定的单元获取它的编码值。给方块类定义i、j属性，起的就是编码的作用。其次，要能通过编码找到所对应的单元。将方块实例创建在一个二维数组中，而数组的下标正好与编码的i、j对应，那么就可以用编码作为数组的下标直接找到对应的单元，即为索引。使用二维数组存储方块的另一个好处是可以非常方便地找到某个方块的相邻方块。 3.3 布置雷区 设计好Cell之后，要创建Cell实例并将它们排布在舞台上。很显然，通过嵌套的for循环结构即可。这个过程其实包含了方块编码与索引的实现。代码段如下图所示：var cellContainer=new Sprite();var cells:Array=new Array();

11、for (var i=0; ilineCount; i+) var cellList:Array=new Array();for (var j=0; jlineCount*rowCount) return;var mineSet:int = 0;var i,j,k;while (mineSetmineCount) k = int(Math.random()*lineCount*rowCount);i = int(k/rowCount);j = k%rowCount;if (cellsij.haveMine!=true) cellsij.haveMine=true;mineSet+; 3.4 随

12、机分布地雷 3.5 计算单元格周围雷数 同样利用cells数组，假设需要考察的是第i行第j列的单元。那么，我们只要判断下面8个单元，将有雷的单元数累加即可。 function around(i:int,j:int) /统计i，j位置周围的类数var count:Number = 0;for (var int_i=i-1; int_i=i+1; int_i+) for (var int_j=j-1; int_j=j+1; int_j+) if (int_i=lineCount) /超出上下边界break;if (int_j=rowCount) /超出左右边界break;if (cellsint_

13、iint_j.haveMine =true) count+;if (cellsij.haveMine=true) /减去自身被统计进入的雷数count-;return count; 3.6 无雷区自动扩张的设计 当玩家点击的单元周围没有地雷，那么应该将周围的所有单元都自动打开，如果自动打开的单元还有周围无地雷的情况，那么继续打开它周围的单元。这样玩家只要点击一下，就可以成片地排除无雷区。很显然，这是一个递归操作。请描述基于二维阵列，寻找其周边单元的递归操作具有自反性（旁边的旁边可能是自身），要避免这种自反性造成无限递归，程序崩溃。只要限定只有未打开过的单元允许递归就可以解决这个问题。 func

14、tion expand(i,j) /无雷区扩张var count=around(i,j);/周围的雷数cellsij.discovered=true;cellsij.showAround(count);if (count!=0) /非无雷区return;for (var int_i=i-1; int_i=i+1; int_i+) /遍历周围的单元for (var int_j=j-1; int_j=j+1; int_j+) if (int_i=i & int_j=j) /自身，不递归continue;if (cellsint_iint_j.discovered=false) /未打开过，

15、进入递归expand(int_i,int_j); 3.7 判断地雷是否已经全部扫除 当所有的有地雷的单元被插上旗帜并且也只有这些单元被插上旗帜的时候表示全部地雷已经扫除，代码如下：function checkVictory():Boolean if (mineLeft!=0) /没有扫除干净或者有扫错return false;for (var i=0; icells.length; i+) for (var j=0; jcellsi.length; j+) if (cellsij.haveMine=true&cellsij.haveFlag=false) return false;re

16、turn true; 3.8 人机交互部分的设计 这个游戏就只有两个操作： 排除无雷单元 插拔旗帜 遗憾的是Flash并不提供右键操作的事件，而双击事件和单击事件也无法同时使用。经过考虑，使用以下方式进行人机交互： 鼠标单击：排除无雷单元，如果是按下Ctrl按键的同时单击鼠标，则表示插拔旗帜操作。 鼠标滚轮：插拔旗帜，如果玩家鼠标没有滚轮，则改用Ctrl+鼠标单击。 function activeCells() /给单元格添加事件侦听器for (var i=0; icells.length; i+) for (var j=0; jcellsi.length; j+) MovieClip(cellsij).addEventListener(MouseEvent.MOUSE_UP,adjustClick);MovieClip(cellsij).addEventListener(MouseEvent.MOUSE_WHEEL,flagCell);adjustClick与flagCell的实现请看备注3.9 设置难度级别 本例中，设置难度级别非常容易，只要在初始化过程中修改三个参数即可，这三个参数为： lineCount rowCount mineCount 3.10 显示所有地雷 用一个嵌套for循环即可实现：func