一个增加游戏重玩价值的办法是，允许游戏以程序的方式产生自己的内容——也叫作添加程序生成内容。
在本教程中，我将告诉大家如何使用一种叫作“Drunkard Walk”的算法制作类似地下城的关卡以及用可重复利用的、用于控制关卡生成的Map class。
本教程使用Sprite Kit，它是与iOS 7一起推出的框架工具。你还要用到Xcode 5。如果你对Sprite Kit不太熟悉，我建议你先学习一下网上的相关教程吧。对于已经掌握Sprite Kit的读者，那就没有什么可担心的了。你可以轻易地用Cocos2d将本教程中出现的代码重写出来。
准备工作
在开始以前，我们先澄清一个概念：不要把程序性和随机性混为一谈。随机性意味着你无法控制生成什么内容，而游戏开发是不会出现这种情况的。
甚至在程序生成的关卡中，你的玩家也应该能够到达出口。玩像《屋顶狂奔》那样的“无尽奔跑”游戏时，如果遇到建筑之间的间隙跳不过，那还有意思吗?或者玩平台游戏，出 口在你到不了的地方，那还玩得下去吗?因此，设计程序生成关卡甚至比自己手动设计关卡更困难。
我想，如果你是程序员，你大概会嘲笑这种警告似的论断吧。在开始前请下载本教程的初始项目。下载好后，解压文件在Xcode中打开项目，创建并运行。你应该看到如下画面：
图1、程序关卡生成的初始项目
初始项目包含游戏的基本构造块，即所有必要的美术、音效和音乐。注意以下几个重要的class：
Map: 创造一个基本的10×10方形，作为游戏的关卡。
MapTiles:负责2D贴图的辅助类(helper class)。稍后再解释。
DPad: 提供基本的执行法：控制玩家角色—-猫的操作杆
MyScene: 创建Sprite Kit场景和进程游戏逻辑。
在继续往下看以前请花一些时间熟悉初始项目的代码。代码中有帮助你理解的注释。另外，请用DPad试玩游戏，将猫从左下角移到出口。注意每一次关卡开始，起点和终点都会变
化。
新地图
如果你玩了这个初始项目不止一次，你应该会发现，这个游戏并不好玩。Jordan Fisher在某文章中指出，游戏关卡，特别是程序生成的关卡，必须满足以下三条标准才是成功的：
1、可行性(Feasibility)：你可能通关吗?
2、有趣的设计(Interesting design)：你想通关吗?
3、技术水平(Skill level)：是否具有良好的挑战性?
这个初始项目没有满足后两条标准：设计并不有趣，因为外周长永远不变;太容易获胜了，因为关卡一开始就能看到出口在哪里。因此，为了让这个关卡更有趣，你必须生成更好 的地下城，并让出口更难找到。
第一步是改变地图生成的方式。为此，你要删除Map class，用新的执行法代替它。
在Project Navigator中选择Map.h和Map.m，按下Delete，然后选择Move to Trash。
打开FileNewNew File…，选择iOSCocoa TouchObjective-C class，然后点击Next。命名这个class为Map(地图)，使它成为SKNode的Subclass;点击Next。确保 ProceduralLevelGeneration目标被选中，点击Create。
打开Map.h，并添加以下代码到@interface部分：
@property (nonatomic) CGSize gridSize;
@property (nonatomic, readonly) CGPoint spawnPoint;
@property (nonatomic, readonly) CGPoint exitPoint;
+ (instancetype) mapWithGridSize:(CGSize)gridSize;
- (instancetype) initWithGridSize:(CGSize)gridSize;这是MyScene显示Map class的界面。你在这里指定刷出玩家和出口的地方。创建一些初始化程序来构造指定大小的class。
在Map.m中执行这些，即添加以下代码到@implementation部分：
+ (instancetype) mapWithGridSize:(CGSize)gridSize
{
return [[self alloc] initWithGridSize:gridSize];
}
- (instancetype) initWithGridSize:(CGSize)gridSize
{
if (( self = [super init] ))
{
self.gridSize = gridSize;
_spawnPoint = CGPointZero;
_exitPoint = CGPointZero;
}
return self;
}这里，你添加一个只把玩家刷出点和退出点设置到CGPointZero的执行。这样，你就有了简单的起点—-之后再把这些做得更有趣。
创建并运行，你会看到：
Procedural-Level-Generation(from raywenderlich.com)
主角猫直接到达出口，太无聊了—-或者说实在太简单了。确实不是你所希望的、有意思的游戏，对吧?是时候添加一些地面(floor)了。Drunkard Walk算法该出场了。
Drunkard Walk算法
Drukard-Walk-Illustrated(from raywenderlich.com)
Drunkard Walk是一种随机行走(random walk)，是最简单的地下城生成算法之一。它的执行非常简单，主要有以下几步：
1、在网格上选择一个随机起点，标记为地面。
2、挑一个随机方向移动(上、下、左、右)
3、向那个方向移动并标记位置为地面，除非它已经是一个地面。
4、重复第2和第3步，直到网格上的地面数量达到要求。
很简单，是吧?基本上，这是一个循环，一直运行到地图上有足够的地面数。为了让地图生成尽量灵活，执行时，你要通过添加新特性来保持要生成的贴图数量。
打开Map.h后添加如下属性(property)：
@property (nonatomic) NSUInteger maxFloorCount;
接着，打开Map.m后添加如下方法：
- (void) generateTileGrid
{
CGPoint startPoint = CGPointMake(self.gridSize.width / 2, self.gridSize.height / 2);
NSUInteger currentFloorCount = 0;
while ( currentFloorCount < self.maxFloorCount )
{
currentFloorCount++;
}
}以上代码开始执行Drunkard Walk算法循环的第1步，但有一个重要的区别。你发现了吗?
提示：startPoint被默认为网格的中心，而不是随机位置。这么做是为了防止算法运行到边缘然后卡住。本教程第二部分会给出进一步的解释。
generateTileGrid开始时，先设置起点位置，然后进入循环，一直运行到currentFloorCount等于maxFloorCount属性确定的地面数字。
当你初始化Map对象时，你应该调用generateTileGrid，以保证你创建了这个网格。添加如下代码到initWithGridSize：在Map.m中，接在_exitPoint = CGPointZero语句之后：
[self generateTileGrid];
创建并运行，确保游戏编码正确。自上一次运行后，什么都没有变化了。猫仍然到出口，仍然没有墙体。你仍然需要写生成地面的代码，但在此之前，你必须理解MapTiles辅助类 。
注：如果你好奇为什么我选择使用C数组而不是NSMutableArray，我只能说这是个人偏好。我通常不喜欢把原始数据类型如整数放进对象里，然后再取出来使用。因为MapTiles网格 只是一个整数的集合(array)，所以我偏好Carray。
这个MapTiles class已经在你的项目中了。如果你能看一看，你马上就能理解它是如何运行的。所以请大胆跳过Generating the Floor这部分吧。
但如果你不确定它是如何运行的，那么就老老实实地按步学习吧。我会一边解释的。
首先在Project Navigator中选择MapTiles.h和MapTiles.m，按下Delete，然后选择Move to Trash。
打开FileNewFile…，选择iOSCocoa TouchObjective-C class，然后点击Next。命名class为MapTiles，使它成为NSObject的subclass，并点击Next。请确保 ProceduralLevelGeneration目标被选中，并点击Create。
为了更容易确定贴图的类型，添加如下枚举 (Enum) 到MapTiles.h的#import的声明下面：
typedef NS_ENUM(NSInteger, MapTileType)
{
MapTileTypeInvalid = -1,
MapTileTypeNone = 0,
MapTileTypeFloor = 1,
MapTileTypeWall = 2,
};如果之后你想用更多贴图类型拓展MapTiles class，你应该把那些放在MapTileType 枚举中。
注：注意你赋给各个枚举的整数值。它们不是随机挑选的。打开tiles.atlas材质图集，点击1.png文件，你会看到这是地面的材质，就像MapTileTypeFloor有值为1。这使得把2D数 组转化为贴图更容易。
打开MapTiles.h，然后添加如下属性和方法原型到@interface和@end之间：
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) CGSize gridSize;
- (instancetype) initWithGridSize:(CGSize)size;
- (MapTileType) tileTypeAt:(CGPoint)tileCoordinate;
- (void) setTileType:(MapTileType)type at:(CGPoint)tileCoordinate;
- (BOOL) isEdgeTileAt:(CGPoint)tileCoordinate;
- (BOOL) isValidTileCoordinateAt:(CGPoint)tileCoordinate;你已经添加了两个只读属性：count是网格上的贴图总数;gridSize表示网格的长和宽。之后你会发现这些属性很方便。在你执行代码时，我会解释这五种方法。
接着，打开MapTiles.m，然后添加如下类拓展到@implementation line语句之前：
@interface MapTiles ()
@property (nonatomic) NSInteger *tiles;
@end这段代码给class添加了一个私有属性tiles。这是存有关于贴图网格的信息的数组的指示器。
现在，在MapTiles.m中和@implementation语句之后执行initWithGridSize：
- (instancetype) initWithGridSize:(CGSize)size
{
if (( self = [super init] ))
{
_gridSize = size;
_count = (NSUInteger) size.width * size.height;
self.tiles = calloc(self.count, sizeof(NSInteger));
NSAssert(self.tiles, @”Could not allocate memory for tiles”);
}
return self;
}你在initWithGridSize:中初始化这两个属性。因为网格上的贴图总数等于网格的宽度乘以网格的高度，你把这个值赋给count。使用这个count，你用calloc分配内存给贴图集，保 证数组中的所有变量初始化为0，等于列举变量TileTypeEmpty。
因为ARC不会用calloc或malloc处理内在分配，任何时候你解除分配MapTiles对象时都应该释放内存。在initWithGridSize:之前和@implementation之后，添加如下dealloc方法：
- (void) dealloc
{
if ( self.tiles )
{
free(self.tiles);
self.tiles = nil;
}
}当你解除分配对象和重置tiles属性指示器以避名它指向不存在于内存中的集合时，dealloc释放内存。
除了构建和解构，MapTiles class还有一些管理贴图的辅助方法。但在你开始执行这些方法以前，你必须理解这些贴图数组在内存中是如何存在的，而不是在网格中是如何组织的 。
当你使用calloc给贴图分配内存时，它为每个数组项保留n个字节，这取决于数据类型，然后把它们按顺序放在内存的扁平结构中。
calloc组织内存中的变量的方法(from raywenderlich.com)
这个贴图结构实际上很难操作。通过一个座标对(x,y)更容易找到贴图，所以 MapTiles最好按图4所示的样子组织贴图网格。
MapTiles class组织内存中的变量的方法(from raywenderlich.com)
所幸，根据座标对(x,y)很容易计算内存中的贴图的index，因为你从gridSize属性中可以知道网格的大小。图4中的方格外的数字分别表示x- 和 y-座标。例如，(x,y)座标(1 ，2)在网格中表示数组的index 9.你使用如下公式计算结果：
index in memory = y * gridSize.width + x
知道这个以后，你可以形势执行根据网格座标对计算index的方法了。为了方便，你还要制作一个保证网格座标有效的方法。
在MapTiles.m中，添加如下新方法：
- (BOOL) isValidTileCoordinateAt:(CGPoint)tileCoordinate
{
return !( tileCoordinate.x < 0 ||
tileCoordinate.x >= self.gridSize.width ||
tileCoordinate.y < 0 ||
tileCoordinate.y >= self.gridSize.height );
}
- (NSInteger) tileIndexAt:(CGPoint)tileCoordinate
{
if ( ![self isValidTileCoordinateAt:tileCoordinate] )
{
NSLog(@”Not a valid tile coordinate at %@”, NSStringFromCGPoint(tileCoordinate));
return MapTileTypeInvalid;
}
return ((NSInteger)tileCoordinate.y * (NSInteger)self.gridSize.width + (NSInteger)tileCoordinate.x);
}isValidTileCoordinateAt: 测试给定座标对是否在网格的范围内。注意这个方法如何检查它是否在范围之外的，以及之后如何返回相反的结果，所以如果座标在范围之外，它会返 回NO在，否则就返回YES。这比检查座标是否在范围内更快，因为后者需要计算的是AND-ed而不是OR-ed。
tileIndexAt:使用上述方程式来计算座标对的index，但在此之前，它先检查座标是否有效。如果无效，它就返回MapTileTypeInvalid在，其值为-1.
有了这个公式，现在可以轻松地制作返回或设置贴图类型的方法了。所以，添加以下两个方法到MapTiles.m的initWithGridSize:之后：
- (MapTileType) tileTypeAt:(CGPoint)tileCoordinate
{
NSInteger tileArrayIndex = [self tileIndexAt:tileCoordinate];
if ( tileArrayIndex == -1 )
{
return MapTileTypeInvalid;
}
return self.tiles[tileArrayIndex];
}
- (void) setTileType:(MapTileType)type at:(CGPoint)tileCoordinate
{
NSInteger tileArrayIndex = [self tileIndexAt:tileCoordinate];
if ( tileArrayIndex == -1 )
{
return;
}
self.tiles[tileArrayIndex] = type;
}以上两个方法使用你刚刚添加的tileIndexAt: 方法计算座标对的index，然后从tiles数组中要么设置要么返回MapTileType。
最后，添加一个能确定给定座标对是否在地图边缘的方法。你之后将使用这个方法来确保你没有把任何地面放在网格的边缘，从而使压缩墙体后面的所有地面成为可能。
- (BOOL) isEdgeTileAt:(CGPoint)tileCoordinate
{
return ((NSInteger)tileCoordinate.x == 0 ||
(NSInteger)tileCoordinate.x == (NSInteger)self.gridSize.width – 1 ||
(NSInteger)tileCoordinate.y == 0 ||
(NSInteger)tileCoordinate.y == (NSInteger)self.gridSize.height – 1);
}再看图5，注意边缘贴图将是由x-为0或gridSize.width – 1的任何贴图，因为这个网格index是以0为基础的。同样地，任何y-为0的或gridSize.height – 1的也是边缘贴图。
最后，测试发现你的程序生成法效果确实不错。添加如下description的执行法，它将输出网格到控制器以排错：
- (NSString *) description
{
NSMutableString *tileMapDescription = [NSMutableString stringWithFormat:@”
