地图之战争迷雾/地图算法/自动导航（一）

战争迷雾

TiledMap 创建黑色覆盖块，然后使用碰撞组件，控制黑色块的显示和隐藏

地图算法

在有些游戏中，地图需要随机生成，比如游戏中的迷宫等，这就需要地图生成的算法；在角色扮演类游戏中，角色需要在地图中找到一条合适的路径，这就需要寻路算法，最常用的寻路算法就是A星路径搜索算法

Roguelike算法（地图生成）

Roguelike是角色扮演游戏（RPG）的一个子类（Roguelike-RPG），其原型——《Rogue》是20世纪80年代初，由Michael Toy和Glenn Wichman两位软件工程师共同在UNIX系统上开发，并在大型机上运行的游戏，Roguelike是角色扮演游戏（RPG）的一个子类（Roguelike-RPG），其原型——《Rogue》是20世纪80年代初，由Michael Toy和Glenn Wichman两位软件工程师共同在UNIX系统上开发，并在大型机上运行的游戏，在2008年的国际Roguelike发展会议上Roguelike游戏有了明确的定义，它的特点包括：

1）生成随机性。每一次新开局游戏都会随机生成游戏场景、敌人、宝物等不同事物。这样玩家的每一次冒险历程也都将是独一无二，不可复制的。

2）进程单向性。存档功能的唯一作用就是记录你当前的游戏进度，每当存档被读取时，对应的进度就会被清空，直到你进行下一次存档。

3）不可挽回性。在大多数Roguelike游戏中，每一个角色只有一次生命，一个角色的死亡意味着玩家将永远失去该角色。无论你是主角、敌人、物品还是场景。在很多玩家眼中，这正是Roguelike的乐趣所在。

4）游戏非线性。严谨而不失灵活性的游戏规则，使游戏具备了很高的自由度，在这类游戏中，玩家可以发挥想象力，利用各种方法实现任何他们想做的事情，或合乎常理，或匪夷所思，目的只在于解决他们在游戏中遇到的问题。

5）系统复杂性。可能会在一款游戏中包括多到无法估量的元素，例如地质、气候和生物分布，以及精细到皮肤、肌肉、血液、骨骼和脂肪的战斗系统，甚至战损痊愈后会留下伤疤以及后遗症。在有些游戏里则可能包括数百种的死亡原因，数千种的生物，数万种的物品。

Roguelike 地图生成算法

地图生成算法是这样一个黑盒，它需要你输入地图的限制规则和大小等信息，它的输出是具体的地图数据，具体到Roguelike游戏的地图生成算法，它有如下特点：

1）要同时有开放的房间和走廊，房间在Roguelike游戏中起着至关重要的作用，开放的空间可以让玩家有空间进行战斗，同时房间也可以通过不同的装饰风格来增强游戏场景的表现力。同时，这个地牢不应该完全由房间组成，玩家需要在游戏过程中有不同的感受，走廊会让他们有封闭感，同时增加游戏的策略性。

2）地图生成中部分参数是可调的，由于关卡的难度要有梯度，所以生成规则应该是可调的，理想的做法是将生成器的一些参数设置成可调，可以通过同一套代码生成不同风格和感觉的地牢。

3）地图不是完美的，完美的地图意味着两点之间只有唯一的一条通路，这样玩起来缺少乐趣。当玩家遇到一个死胡同的时候，必须要回溯到之前的路线去，然后寻找新的可探索的地方。游戏是一个决定和做出不同选择的过程。因此，过于完美的地图不能让游戏变得更有趣。

生成地图的具体步骤包括：

1）随机生成房间，保证房间之间不相互覆盖。

2）计算如何连接各个房间。

3）把房间之外的空地用迷宫填满，移除掉死胡同。

4）连接相连的迷宫和房间，增加少量连接。首先是生成房间，这个过程需要注意的是要检查房间之间不相互重叠，每一个房间的生成过程包括随机生成房间左下角坐标和尺寸，判断重叠与否，创建房间。需要注意的是横纵方向个数要保证为奇数。然后是生成迷宫，生成迷宫的过程可以抽象为树的生成，生成的过程为连接每一个节点。首先判断起点上下左右是否在一个方向有连接，不存在就需要将节点放入列表中，如果第一步完成后列表不为空，则将节点向列表中的某一个方向移动两格并将移动后的坐标压入栈中，重复第一步。如果列表为空，则弹出栈顶元素，直到栈为空时。对于每一个走廊的块，如果其四个方向中有3个为空，则把它删除，就可以移除死胡同了。连接迷宫和房间，需要把每个区域联系起来，首先随机找到一个点，连通合并两个区域，然后删除p以外所有能连通两个区域的点，继续第一步，直到所有区域连通，为所有连通区域创建走廊，使所有房间可以连通。

实现

1、地图参数初始化

        //计算房间数量范围calculateRoomSize(size, cell){var max = Math.floor((size/cell) ＊ 0.8);var min = Math.floor((size/cell) ＊ 0.25);if (min < 2) {min = 2;}if (max < 2) {max = 2;}return [min, max];},//初始化地图initMap(){//地图宽高的格子this._width = 96this._height = 64this._options = {cellWidth: 10,     //单元格宽cellHeight: 10,    //单元格高roomWidth: [2,10], //房间个数范围roomHeight: [2,7], //房间个数范围};if (! this._options.hasOwnProperty("roomWidth")) {this._options["roomWidth"] = this.calculateRoomSize(this._width, this._options["cellWidth"]);}if (! this._options.hasOwnProperty("roomHeight")) {this._options["roomHeight"]=this.calculateRoomSize(this._height, this._options["cellHeight"]);}},//入口函数onLoad(){//初始化this.initMap()//地图生成this.mapGenerate()//绘制地图this.drawMap()},

地图生成主要根据如上三步进行，每一步都有一些需要注意的地方。当然，在做这些之前，首先需要进行地图数据的初始化，在这里首先初始化map数组，这是一个二维数组。用来存储最后地图表示的数据。首先把这个数组中的每一个值都初始化为0，也就是所有的位置都是空地，然后初始化房间和房间联通的数组

2、地图的初始化和生成步骤

        //设置map数值，初始化为一个值fillMap(value) {var map = [];for (var i = 0; i < this._width; i ++){map.push([]);for (var j = 0; j < this._height; j ++){map[i].push(value);}}return map;},//初始化房间的数量initRooms() {for (var i = 0; i < this._options.cellWidth; i++) {this.rooms.push([]);for(var j = 0; j < this._options.cellHeight; j++) {this.rooms[i].push({"x":0, "y":0, "width":0, "height":0,"connections":[], "cellx":i, "celly":j});}}},//地图生成过程mapGenerate(){this.map = this.fillMap(0); //初始化地图数据this.rooms = [];              //房间this.connectedCells = [];    //连通的房间//初始化房间this.initRooms()//连接房间this.connectRooms()this.connectUnconnectedRooms()//创建房间this.createRooms()//创建走廊this.createCorridors()},

在initRooms函数里，只是初始化了房间数组，并没有创建房间的数据。生成房间的过程从connectRooms开始，首先连接房间，然后遍历一下房间，看看有没有“被遗忘”的角落，一定要确保所有房间都是连通的，这样才能避免死角的出现，最后才生成房间的数据，调用createRooms生成房间数据

3、生成房间和连接房间

        //创建房间createRooms() {var w = this._width;var h = this._height;var cw = this._options.cellWidth;var ch = this._options.cellHeight;var cwp = Math.floor(this._width / cw);var chp = Math.floor(this._height / ch);//房间属性var roomw;var roomh;var roomWidth = this._options["roomWidth"];var roomHeight = this._options["roomHeight"];var sx;var sy;var otherRoom;//遍历房间中每一个点for (var i = 0; i < cw; i++) {for (var j = 0; j < ch; j++) {sx = cwp ＊ i;sy = chp ＊ j;if (sx == 0) {sx = 1;}if (sy == 0) {sy = 1;}//房间宽高，随机获得roomw = GlobalHandle.getRandomInt(roomWidth[0], roomWidth[1]);roomh = GlobalHandle.getRandomInt(roomHeight[0], roomHeight[1]);if (j > 0) {otherRoom = this.rooms[i][j-1];while (sy - (otherRoom["y"] + otherRoom["height"] ) < 3) {sy++;}}if (i > 0) {otherRoom = this.rooms[i-1][j];while(sx - (otherRoom["x"] + otherRoom["width"]) < 3) {sx++;}}var sxOffset = Math.round(GlobalHandle.getRandomInt(0, cwp - roomw)/2);var syOffset = Math.round(GlobalHandle.getRandomInt(0, chp - roomh)/2);while (sx + sxOffset + roomw >= w) {if(sxOffset) {sxOffset--;} else {roomw--;}}while (sy + syOffset + roomh >= h) {if(syOffset) {syOffset--;} else {roomh--;}}sx = sx + sxOffset;sy = sy + syOffset;this.rooms[i][j]["x"] = sx;this.rooms[i][j]["y"] = sy;this.rooms[i][j]["width"] = roomw;this.rooms[i][j]["height"] = roomh;//设置地图for (var ii = sx; ii < sx + roomw; ii++) {for (var jj = sy; jj < sy + roomh; jj++) {this.map[ii][jj] = 1;}}}}},

地图生成结果

小方块组成的即“房间”。可以发现，房间之间都互相独立，并不能互相连通，这就是后续我们要做的，即生成走廊。首先在数据上，参考之前生成的房间连通数据，生成走廊，随后在绘制走廊的函数里更新map数据。

        //绘制走廊，设置map值drawCorridor(startPosition, endPosition) {var xOffset = endPosition[0] - startPosition[0];var yOffset = endPosition[1] - startPosition[1];var xpos = startPosition[0];var ypos = startPosition[1];var tempDist;var xDir;var yDir;var move;var moves = [];var xAbs = Math.abs(xOffset);var yAbs = Math.abs(yOffset);var percent = Math.random();var firstHalf = percent;var secondHalf = 1- percent;xDir = xOffset > 0 ? 2 : 6;yDir = yOffset > 0 ? 4 : 0;if (xAbs < yAbs) {tempDist = Math.ceil(yAbs ＊ firstHalf);moves.push([yDir, tempDist]);moves.push([xDir, xAbs]);tempDist = Math.floor(yAbs ＊ secondHalf);moves.push([yDir, tempDist]);} else {tempDist = Math.ceil(xAbs ＊ firstHalf);moves.push([xDir, tempDist]);moves.push([yDir, yAbs]);tempDist = Math.floor(xAbs ＊ secondHalf);moves.push([xDir, tempDist]);}this.map[xpos][ypos] = 2;while (moves.length > 0) {move = moves.pop();while (move[1] > 0) {xpos += GlobalHandle.DIRS[8][move[0]][0];ypos += GlobalHandle.DIRS[8][move[0]][1];this.map[xpos][ypos] = 2;move[1] = move[1] -1;}}},createCorridors() {//创建走廊var cw = this._options.cellWidth;var ch = this._options.cellHeight;var room;var connection;var otherRoom;var wall;var otherWall;for (var i = 0; i < cw; i++) {for (var j = 0; j < ch; j++) {room = this.rooms[i][j];for (var k = 0; k < room["connections"].length; k++) {connection = room["connections"][k];otherRoom = this.rooms[connection[0]][connection[1]];//获得墙体数量if (otherRoom["cellx"] > room["cellx"]) {wall = 2;otherWall = 4;} else if (otherRoom["cellx"] < room["cellx"]) {wall = 4;otherWall = 2;} else if(otherRoom["celly"] > room["celly"]) {wall = 3;otherWall = 1;} else if(otherRoom["celly"] < room["celly"]) {wall = 1;otherWall = 3;}this.drawCorridor(this.getWallPosition(room, wall),this.getWallPosition(otherRoom, otherWall));}}}},

生成地图数据后，接下来的任务就是把这个地图绘制出来，在drawMap中绘制，根据map里每个元素值对应的不同类型渲染不同颜色的方块。

        //绘制地图drawMap(){for (var i = 0; i < this._width; i ++){for (var j = 0; j < this._height; j ++) {if(this.map[i][j] == 1){ //房间地图格var ctx = this.mapLayer.getComponent(cc.Graphics)ctx.fillColor.fromHEX('#FF0000');ctx.rect((i) ＊ this._options.cellWidth, (j) ＊this ._options.cellHeight, this._options.cellWidth, this._options.cellHeight)ctx.fill()ctx.stroke()}else if(this.map[i][j] == 2){ //门口地图格var ctx = this.mapLayer.getComponent(cc.Graphics)ctx.fillColor.fromHEX('#7B68EE');ctx.rect((i)  ＊  this._options.cellWidth, (j)  ＊  this._options.cellHeight, this._options.cellWidth, this._options.cellHeight)ctx.fill()}else if(this.map[i][j] == 3) {//走廊地图格var ctx = this.mapLayer.getComponent(cc.Graphics)ctx.fillColor.fromHEX('#00FF00');ctx.rect((i)  ＊  this._options.cellWidth, (j)  ＊  this._options.cellHeight, this._options.cellWidth, this._options.cellHeight)ctx.fill()}}}},

结果

A星算法

，A星搜索算法用来实现敌人的智能运动，比如敌人巡逻或者角色寻径