作者Kim Pedersen

一个增加游戏重玩价值的办法是，允许游戏以程序的方式产生自己的内容——也叫作添加程序生成内容。

在本教程中，我将告诉大家如何使用一种叫作“Drunkard Walk”的算法制作类似地下城的关卡以及用可重复利用的、用于控制关卡生成的Map class。

本教程使用Sprite Kit，它是与iOS 7一起推出的框架工具。你还要用到Xcode 5。如果你对Sprite Kit不太熟悉，我建议你先学习一下网上的相关教程吧。对于已经掌握Sprite Kit的读者，那就没有什么可担心的了。你可以轻易地用Cocos2d将本教程中出现的代码重写出来。

准备工作

在开始以前，我们先澄清一个概念：不要把程序性和随机性混为一谈。随机性意味着你无法控制生成什么内容，而游戏开发是不会出现这种情况的。

甚至在程序生成的关卡中，你的玩家也应该能够到达出口。玩像《屋顶狂奔》那样的“无尽奔跑”游戏时，如果遇到建筑之间的间隙跳不过，那还有意思吗？或者玩平台游戏，出 口在你到不了的地方，那还玩得下去吗？因此，设计程序生成关卡甚至比自己手动设计关卡更困难。

我想，如果你是程序员，你大概会嘲笑这种警告似的论断吧。在开始前请下载本教程的初始项目。下载好后，解压文件在Xcode中打开项目，创建并运行。你应该看到如下画面：

初始项目包含游戏的基本构造块，即所有必要的美术、音效和音乐。注意以下几个重要的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。

打开File\New\New File…，选择iOS\Cocoa Touch\Objective-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的执行。这样，你就有了简单的起点—-之后再把这些做得更有趣。

创建并运行，你会看到：

主角猫直接到达出口，太无聊了—-或者说实在太简单了。确实不是你所希望的、有意思的游戏，对吧？是时候添加一些地面（floor）了。Drunkard Walk算法该出场了。

Drunkard Walk算法

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。

打开File\New\File…，选择iOS\Cocoa Touch\Objective-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个字节，这取决于数据类型，然后把它们按顺序放在内存的扁平结构中。

这个贴图结构实际上很难操作。通过一个座标对（x,y）更容易找到贴图，所以 MapTiles最好按图4所示的样子组织贴图网格。

所幸，根据座标对（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:@"<%@ = %p | \n",
[self class], self];

for ( NSInteger y = ((NSInteger)self.gridSize.height – 1); y >= 0; y– )
{
[tileMapDescription appendString:[NSString stringWithFormat:@"[%i]“, y]];

for ( NSInteger x = 0; x < (NSInteger)self.gridSize.width; x++ )
{
[tileMapDescription appendString:[NSString stringWithFormat:@"%i",
[self tileTypeAt:CGPointMake(x, y)]]];
}
[tileMapDescription appendString:@"\n"];
}
return [tileMapDescription stringByAppendingString:@">"];
}

这个方法只是循环网格以产生用字符串表示的贴图。

那要使用非常多的文本和代码，但你所做的将使程序关卡生成更加容易，因为你现在可以从关卡首开生中提取网格。现在，可以添加一些地面了。

生成地面

你将使用上述的Drunkard Walk算法将地面放在地图上。在Map.m，你已经执行了这个算法的一部分，所以它现在找到一个随机的起点（第1步），且循环了足够的次数（第4步）。 现在你必须执行第2步和第3步，才能在你所制作的循环中生成真正的地面贴图。

为了使Map class更灵活，你可以添加一个专门的方法来生成程序性地图。如果你之后需要生成这个地图，那么做会非常方便。

打开Map.h然后添加以下方法声明到界面：

- (void) generate;

在Map.m，添加如下语句到文件开头：

#import “MapTiles.h”

添加如下代码到@implementation语句的右上方。

@interface Map ()
@property (nonatomic) MapTiles *tiles;
@end

class拓展有一个专有的属性，即MapTiles对象的指示器。你将使用这个对象以便更容易处理地图生成的网格。你要保持它的专有性，因为不能从Map class外部改变MapTiles对象 。

接着，执行Map.m中的generate方法：

- (void) generate
{
self.tiles = [[MapTiles alloc] initWithGridSize:self.gridSize];
[self generateTileGrid];
}

第一个方法分配和初始化MapTiles对象，然后通过调用generateTileGrid生成一个新的贴图网格。

在Map.m，打开initWithGridSize:然后删除以下语句：

[self generateTileGrid];

你删除这一句是因为当你创建Map对象时，地图生成不再立即发生了。

这时候就要添加这段代码以生成地下城的地面。你还记得Drunkard Walk算法的其他步骤吗？你选择随机方向，然后把地面放在新的座标上。

第一步是添加一个方便的方法，以便提供介于两个值之间的随机数字。添加如下方法到Map.m：

- (NSInteger) randomNumberBetweenMin:(NSInteger)min andMax:(NSInteger)max
{
return min + arc4random() % (max – min);
}

你将使用这个方法来返回介于（等于）最小值和最大值之间的随机数字：

回到generateTileGrid，用如下代码替换它的内容：

CGPoint startPoint = CGPointMake(self.tiles.gridSize.width / 2, self.tiles.gridSize.height / 2);
// 1
[self.tiles setTileType:MapTileTypeFloor at:startPoint];
NSUInteger currentFloorCount = 1;
// 2
CGPoint currentPosition = startPoint;
while ( currentFloorCount < self.maxFloorCount )
{
// 3
NSInteger direction = [self randomNumberBetweenMin:1 andMax:4];
CGPoint newPosition;
// 4
switch ( direction )
{
case 1: // Up
newPosition = CGPointMake(currentPosition.x, currentPosition.y – 1);
break;
case 2: // Down
newPosition = CGPointMake(currentPosition.x, currentPosition.y + 1);
break;
case 3: // Left
newPosition = CGPointMake(currentPosition.x – 1, currentPosition.y);
break;
case 4: // Right
newPosition = CGPointMake(currentPosition.x + 1, currentPosition.y);
break;
}
//5
if([self.tiles isValidTileCoordinateAt:newPosition] &&
![self.tiles isEdgeTileAt:newPosition] &&
[self.tiles tileTypeAt:newPosition] == MapTileTypeNone)
{
currentPosition = newPosition;
[self.tiles setTileType:MapTileTypeFloor at:currentPosition];
currentFloorCount++;
}
}
// 6
_exitPoint = currentPosition;
// 7
NSLog(@”%@”, [self.tiles description]);

以上代码的作用是：

1、标记贴图座标在网格上的startPoint作为一个地面贴图，进而用count为1初始化currentFloorCount.

2、currentPosition是网格上的当前位置。这段代码初始化startPoint座标，这就是Drunkard Walk算法开始的地方。

3、这里，这段代码选择介于1到4之间的随机数字，提供了移动方向（1=上，2=下，3=左，4=右）。

4、根据上一步选择的随机数字，代码计算网格上的新位置。

5、如果新计算到的位置是有效的、非边缘且不包含贴图，那就在这个部分添加一个地面贴图，然后给currentFloorCount加1.

6、这里，代码设置最后一个贴图为出口点。这是地图的目标。

7、最后，代码打印生成的贴图网格到控制器。

创建并运行。这个游戏没有明显的变化，但无法把贴图网格写入到控制器中。为什么呢？

提示：在MyScene初始化时，你没有调用Map class的generate。因此，你制作了map对象，但其实没有生成贴图。

要解决这个问题，先打开MyScene.m，找到initWithSize:，用如下语句替换self.map = [[Map alloc] init]：

self.map = [[Map alloc] initWithGridSize:CGSizeMake(48, 48)];
self.map.maxFloorCount = 64;
[self.map generate];

上述代码生成一个网格大小为48*48贴图的新地图，理想的最大地面计数为64。你设置好maxFloorCount属性后，你就得到了这个地图。

再次创建并运行。你应该看到与如下图片类似但可能不完全相同（因为是随机的）的结果：

太好了！你已经生成一个程序关卡了。可以把你的杰作放在更大的屏幕上看看了。

把贴图网格转化为贴图

在控制器中测绘你的关卡是一个代码排错的好办法，但不能给玩家产生太好的印象。下一步是把网格转化为真正的贴图。

初始项目已经有包含这种贴图的纹理图集了。为了把这些图集加载到内存中，你要给Map.m的class拓展添加专门属性以及表示贴图大小的属性：

@property (nonatomic) SKTextureAtlas *tileAtlas;
@property (nonatomic) CGFloat tileSize;

在initWithGridSize:中初始化这两个属性，在设置_exitPoint:的值之后：

self.tileAtlas = [SKTextureAtlas atlasNamed:@"tiles"];

NSArray *textureNames = [self.tileAtlas textureNames];
SKTexture *tileTexture = [self.tileAtlas textureNamed:(NSString *)[textureNames firstObject]];
self.tileSize = tileTexture.size.width；

载入纹理图集后，以上代码将从图集中读取这个纹理名称。它使用图集中的第一个来加载纹理，然后存储纹理的宽度作为tileSize。这段代码假设图集中的纹理是正方形的，且大 小都相同。

注：使用纹理图集可以减少渲染地图的必要绘制调用次数。每一次调用都增加系统的负担，因为Sprite Kit必须执行额外的进程来给各次绘制调用设置GPU。通过使用单一的纹理图 集，整个地图可能只需要一次调用就绘制完成。确切的次数取决于几个因素，但在这个应用中，那些都不必考虑。

仍然在Map.m中，添加以下方法：

- (void) generateTiles
{
// 1
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
for ( NSInteger x = 0; x < self.tiles.gridSize.width; x++ )
{
// 2
CGPoint tileCoordinate = CGPointMake(x, y);
// 3
MapTileType tileType = [self.tiles tileTypeAt:tileCoordinate];
// 4
if ( tileType != MapTileTypeNone )
{
// 5
SKTexture *tileTexture = [self.tileAtlas textureNamed:[NSString stringWithFormat:@"%i", tileType]];
SKSpriteNode *tile = [SKSpriteNode spriteNodeWithTexture:tileTexture];
// 6
tile.position = tileCoordinate;
// 7
[self addChild:tile];
}
}
}
}

generateTiles转化内部贴图网格为真正的贴图：

1、两个for循环，一个是x的，一个是y的，循环计算网格内的各个贴图。

2、转化当前x-和y-值作为网格内的贴图的位置的CGPoint结构。

3、这里，这段代码确定网格内的这个位置的贴图类型。

4、如果贴图类型不是空白贴图，则代码继续产生贴图。

5、根据贴图类型，代码从纹理图集中分别载入贴图纹理，并赋给SKSpriteNode对象。记住，贴图类型（整数）与纹理的文件名称是一致的。

6、代码设置贴图的位置为贴图座标。

7、然后汧加制作好的贴图结点作为map对象的子项。这么做是为了通过将贴图分类到它们所归属的地图中来保证正确的滚动。

最后，添加以下语句到Map.m中，在[self generateTileGrid]:之后，以确保网格转化为贴图：

[self generateTiles];

创建并运行—-但结果不是我们所期望的。这个游戏没有正确地放置贴图，如下图所示：

原因很简单：当设置贴图位置时，当前代码设置贴图的位置为内部网格的位置，而不是屏幕座标的相对位置。

你需要一个新的方法将网格座标转化为屏幕座标，添加以下代码到Map.m：

- (CGPoint) convertMapCoordinateToWorldCoordinate:(CGPoint)mapCoordinate
{
return CGPointMake(mapCoordinate.x * self.tileSize, (self.tiles.gridSize.height – mapCoordinate.y) * self.tileSize);
}

将网格（地图）座标乘上贴图大小，你就计算出水平位置了。垂直位置更复杂一些。记住，Sprite Kit中的座标 (0,0)表示左下角。在贴图网格中， (0,0)表示左上角（见图2）。 因此，为了正确显示贴图位置，你必须转化它的垂直座标植。方法就是用网格的总高度减去贴图在网格中的y值，然后乘上贴图大小。

打开generateTiles，将设置tile.position的语句修改成：

tile.position = [self convertMapCoordinateToWorldCoordinate:CGPointMake(tileCoordinate.x, tileCoordinate.y)];

另外，将generateTileGrid中设置_exitPoint的语句修改成：

_exitPoint = [self convertMapCoordinateToWorldCoordinate:currentPosition];

创建并运行—-咦？贴图去哪里了？

贴图仍然在的—-只是跑到可见区域之外了。通过修改玩家的刷出位置可以解决这个问题。你将使用一个简单但有效的策略，即将刷出位置设置为generateTileGrid中的startPoint 。

打开generateTileGrid，添加如下语句到这个方法的最开头处：

_spawnPoint = [self convertMapCoordinateToWorldCoordinate:startPoint];

刷出点是一对屏幕座标，也就是玩家在关卡开始时出现的位置。因此，你要根据网格座标计算游戏世界的座标。

创建并运行，让猫在这个程序生成的世界里走一走。你可能会发现出口？

试玩一下不同的网格大小和最大数量的地面贴图，看看它如何影响地图生成。

现在有一个明显的问题是，猫可以偏离路径。我们都知道猫走偏是什么情况，对吧？所以，是时候添加墙体了。

添加墙体

打开Map.m，添加如下方法：

- (void) generateWalls
{
// 1
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
for ( NSInteger x = 0; x < self.tiles.gridSize.width; x++ )
{
CGPoint tileCoordinate = CGPointMake(x, y);

// 2
if ( [self.tiles tileTypeAt:tileCoordinate] == MapTileTypeFloor )
{
for ( NSInteger neighbourY = -1; neighbourY < 2; neighbourY++ )
{
for ( NSInteger neighbourX = -1; neighbourX < 2; neighbourX++ )
{
if ( !(neighbourX == 0 && neighbourY == 0) )
{
CGPoint coordinate = CGPointMake(x + neighbourX, y + neighbourY);

// 3
if ( [self.tiles tileTypeAt:coordinate] == MapTileTypeNone )
{
[self.tiles setTileType:MapTileTypeWall at:coordinate];
}
}
}
}
}
}
}
}

1、generateWalls使用的策略是，第一次循环通过网格上的各个贴图。

2、如此循环直到发现地面贴图（MapTileTypeFloor）。

3、然后检查周围的贴图，并标记这些为墙体（MapTileTypeWall），如果没有贴图在那里的话（MapTileTypeNone）。

这个内部for循环可能乍一看有些奇怪。看看各个围绕着贴图(x,y)的贴图。如图10所示，看看你需要的贴图与原来的index相比，如何少1，等于和多1。这两个for循环的结果是， 从1开始，循环直到+1.添加这些整数中的一个到for循环中原来的index中，你会找到各个周边贴图。

如果你检查的贴图是网格的边缘，怎么办？在这种情况下，检查会失败，因为index是无效的，对吧？

是的，但幸运的是，这种情况可以通过MapTiles class的tileTypeAt:缓和。如果一个无效的座标被发送到tileTypeAt:，这个方法会返回MapTileTypeInvalid值。想一想 generateWalls的//3之后的语句，注意，如果返回的贴图类型是MapTileTypeNone，它只将贴图变成墙体贴图。为了生成这种墙体贴图，回到Map.m的generate，然后添加如下语句 到[self generateTileGrid]后面和[self generateTiles]之前：

[self generateWalls];

创建并运行。你现在应该看到墙体贴图围绕着地面贴图。试移动一下猫—-注意有什么奇怪的地方吗？

如果可以直接穿过它的话，墙体就没有意义了。解决这个问题的办法有很多，本教程要介绍的是使用Sprite Kit内置的物理引擎。

程序碰撞：理论

将墙体贴图变成碰撞对象的方法有很多。最直接的一种是给各个墙体贴图添加physicsBody，但那并不是最高效的办法。Steffen Itterheim介绍了另一种方法，即使用“Moore Neighborhood algorithm”，但那个本身就是另一篇教程了。

相反地，你将执行一种相当简单的方法，即把各个墙体部分组合成一整个碰撞对象。如下图所示：

这个方法使用以下逻辑将地图上的所有贴图都迭代了一次：

1、从（0，0）开始，迭代贴图网格直到找到墙体贴图。

2、当找到墙体贴图，标记这个贴图网格位置。这是碰撞墙体的起点。

3、移动到网格的下一个贴图。如果这也是一个墙体贴图，那么就在这个碰撞墙体的贴图数量上加1。

4、继续第3步，直到找到非墙体贴图或这一排的尽头。

5、当到达非墙体贴图或这一排的尽头，从起点用这个碰撞墙体的贴图数量的大小制作一个碰撞墙体。

6、再次迭代，回到第2步，重复直到将网格上的所有墙体贴图变成碰撞墙体。

注：上述方法非常基础，还可以进一步优化。例如，你既可以在水平上也可以在垂直上迭代地图。水平迭代地图将省略所有一个贴图大小的碰撞墙体。然后当垂直迭代地图时你将 挑出这些贴图，进一步减少碰撞对象的数量，这总是一件好事。

可以将理论运用于实践了。

程序碰撞：实践

看看MyScene.m 中的initWithSize:激活物理引擎的代码已经在初始项目中了。因为Ray在《给新手看的Sprite Kit教程》中已经对设置物理引擎解释得很清楚了，我在这里就只介 绍它在程序生成关卡的条件下是如何设置的。

当代码产生玩家对象的physicsBody时，它通过添加CollisionTypeWall么collisionBitMask，使它与墙体碰撞。这样，物理引擎就会自动将玩家对象从墙体对象弹开。

然而，当你用generateWalls生成墙体时，你不是把它们做成物理对象—-只是简单的SKSpriteNode。所以，当你创建和运行游戏时，玩家不会与墙体碰撞。

你要通过添加辅助方法来简化墙体碰撞对象的生成。打开Map.m并添加如下代码：

/ Add at the top of the file together with the other #import statements
#import “MyScene.h”

// Add with other methods
- (void) addCollisionWallAtPosition:(CGPoint)position withSize:(CGSize)size
{
SKNode *wall = [SKNode node];

wall.position = CGPointMake(position.x + size.width * 0.5f – 0.5f * self.tileSize,
position.y – size.height * 0.5f + 0.5f * self.tileSize);
wall.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:size];
wall.physicsBody.dynamic = NO;
wall.physicsBody.categoryBitMask = CollisionTypeWall;
wall.physicsBody.contactTestBitMask = 0;
wall.physicsBody.collisionBitMask = CollisionTypePlayer;

[self addChild:wall];
}

这个方法生成并添加SKNode到具有合适的位置和大小的地图。然后给按这个node的大小给它生成一个不可移动的physicsbody，并保证当玩家与这个node碰撞时，这个物理引擎执行 碰撞。

可以执行碰撞墙体生成了。添加如下方法：

- (void) generateCollisionWalls
{
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
CGFloat startPointForWall = 0;
CGFloat wallLength = 0;
for ( NSInteger x = 0; x <= self.tiles.gridSize.width; x++ )
{
CGPoint tileCoordinate = CGPointMake(x, y);
// 1
if ( [self.tiles tileTypeAt:tileCoordinate] == MapTileTypeWall )
{
if ( startPointForWall == 0 && wallLength == 0 )
{
startPointForWall = x;
}
wallLength += 1;
}
// 2
else if ( wallLength > 0 )
{
CGPoint wallOrigin = CGPointMake(startPointForWall, y);
CGSize wallSize = CGSizeMake(wallLength * self.tileSize, self.tileSize);
[self addCollisionWallAtPosition:[self convertMapCoordinateToWorldCoordinate:wallOrigin]
withSize:wallSize];
startPointForWall = 0;
wallLength = 0;
}
}
}
}

这里，你执行之前描述的6个步骤：

1、你迭代各排，直到找到墙体贴图。你给碰撞墙体设置起点（贴图座标对），然后给wallLength加1。移动到下一个贴图，如果它也是墙体贴图，就重复这些步骤。

2、如果下一个贴图不是墙体贴图，那么就计算墙体的大小乘上贴图的大小，将这个起点转化为游戏世界的座标。通过经过起点和大小（像素），你使用你刚才添加的 addCollisionWallAtPosition:withSize:辅助方法生成了一个碰撞墙体。

回到Map.m的generate，添加如下代码语句到[self generateTiles]之后，确保当它生成贴图地图时，游戏生成碰撞墙体：

self generateCollisionWalls];

创建并运行。现在猫困在围墙内了。唯一的出路就是找到出口？

然后呢？

你已经学会生成程序关卡的基本方法。在本教程的第二部分，你将进一步拓展这个地图生成代码—-添加房间。为了使地图生成更加可控制，你还要学习如何添加一些会影响这个过 程的属性。

FloorMaker类

你也许注意到了第一部分的关卡生成就像一条漫长且蜿蜒的走廊。很明显这不是一个有趣的关卡设计，让寻找出口变得不再具有挑战性。

会得出这样的结果并不让人惊讶。毕竟你所执行的算法是基于任意方向移动一个砖块，并不断重复，从而连接到之前放置好的砖块上。尽管这有可能生成宽广的空间领域，但是我 们却不能频繁地使用这一方法去创造地牢式的地图。

现在你将修改算法从而让它能够同时随机游走。基本上，它将会将所有喝醉的人丢出酒吧并命令他们回家。

地图生成需要追踪同一时间被创造出来的不同路径。你将使用一个名为FloorMaker的类面向每个路径执行这一点。

来到File\New\New File…，选择iOS\Cocoa Touch\Objective-C class模版并点击Next。将类命名为FloorMaker，将其设置为NSObject的子类并点击Next。确保选中 ProceduralLevelGeneration，然后点击Create。

打开FloorMaker.h并在@interface和@end间添加如下代码：

@property (nonatomic) CGPoint currentPosition;
@property (nonatomic) NSUInteger direction;

- (instancetype) initWithCurrentPosition:(CGPoint)currentPosition andDirection:(NSUInteger)direction;

现在打开FloorMaker.m并执行初始化器方法：

- (instancetype) initWithCurrentPosition:(CGPoint)currentPosition andDirection:(NSUInteger)direction
{
if (( self = [super init] ))
{
self.currentPosition = currentPosition;
self.direction = direction;
}
return self;
}

FloorMarker非常简单。它带有2个属性去追踪当前的位置和方向，初始化器允许你在创造类的实体时设置这些属性。

当FloorMarker类得到有效设置时，你可以继续在地图生成中使用它。

运行FloorMaker

第一步便是将FloorMaker输入Map.m中。在现有的#import预处理机指令后添加如下代码：

#import “FloorMaker.h”

你将重构generateTileGrid去同时使用多个FloorMaker对象，但你将在不同阶段中执行它。首先做出如下修改，从而让它可以使用一个单一FloorMaker。

在generateTileGrid中将：

CGPoint currentPosition = startPoint;

换成：

FloorMaker* floorMaker = [[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0];

你不再需要在局部变量中储存当前位置，因为每个FloorMaker将储存它自己的当前位置。所以你可以删除currentPosition，并添加名为floorMaker的变量，在startPoint进行初始 化。

既然你已经删除了currentPosition，你便可以用floorMaker.currentPosition取代每个currentPosition的使用。不要担心，Xcode将提供误差帮助你找到它们。

接下来将下一行：

NSInteger direction = [self randomNumberBetweenMin:1 andMax:4];

换成：

floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];

正如你将局部变量currentPosition换成floorMaker.currentPosition一样，在此你也是基于同样的原因将局部变量direction换成了floorMaker.direction。

创建并运行，应用应该会像之前那样运行。

现在你将改变Map去支持使用多个FloorMaker。在Map.m添加如下属性到Map类扩展中：

@property (nonatomic) NSMutableArray *floorMakers;

floorMakers数组持有所有积极FloorMaker的参照内容。

然后回到generateTileGrid中做出如下改变去使用floorMaker数组而不是FloorMaker对象。

将如下行：

NSUInteger currentFloorCount = 1;
FloorMaker* floorMaker = [[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0];

换成：

__block NSUInteger currentFloorCount = 1;
self.floorMakers = [NSMutableArray array];
[self.floorMakers addObject:[[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0]];

你添加__block类型说明到currentFloorCount声明，如此你便可以在Objective-C组块中修改它的值，你将快速完成这点。你需要移除局部floorMaker变量并基于可变数组（包含一 个FloorMaker对象）去初始化Map的floorMakers。之后你将添加更多FloorMaker到这个数组中。

在generateTileGrid中修改while循环的内容：

while ( currentFloorCount < self.maxFloorCount ) {
[self.floorMakers enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
FloorMaker *floorMaker = (FloorMaker *)obj;

{
//...
// original contents of the while loop HERE
//...
}
}];
}

这改变了方法所以它能在floorMaker数组中的对象上进行迭代，并面向每个对象执行Drunkard Walk。最终你将拥有一个以上的FloorMaker运行，但是你只能拥有一个出口点。为了 确保游戏创造的最后一个楼层成为出口，将设置_exitPoint的行从当前位置移动到currentFloorCount++; 之后。这是在游戏创造了所有楼层后对_exitPoint的分配，最后的砖块创 造变成了出口点。

再次创建并运行，我们可以注意到形式似乎并未发生改变。

顾及多条路径

尽管地图生成可行，它却仍只能运行一个FloorMaker实体，所以关卡仍与你在第一部分教程中所看到的内容非常相似。因为FloorMaker理念是拥有许多实体，所以你现在需要改变 generateTileGrid方法而允许更多FloorMaker的生成。

回到generateTileGrid，在组块最后，即闭括号和括号前添加如下代码：

if ( [self randomNumberBetweenMin:0 andMax:100] <= 50 )
{
FloorMaker *newFloorMaker = [[FloorMaker alloc] initWithCurrentPosition:floorMaker.currentPosition andDirection:[self randomNumberBetweenMin:1 andMax:4]];

[self.floorMakers addObject:newFloorMaker];
}

这一代码为能在FloorMaker的每一步创造一个新的FloorMaker提供了50%的机会。我们可以注意到代码创造了一个newFloorMaker，带有等同于当前FloorMaker的当前位置的位置， 但却是基于随机方向。

再次创建并运行。是否注意到一些奇怪的地方？

这里存在两个问题。首先，现在的算法生成了更宽广的空间，而不只是一条漫长的走廊。你将在之后做出一些改变去影响它创造的地图类型，所以你可以暂且忽视这一问题。

第二个问题很容易被忽视，但是如果你生成了一些地图并计算楼层，你便会发现自己的应用不再涉及maxFloorCount值。它将在maxFloorCout和maxFloorCount+floorMakers数量-1 间创造一些楼层数。这是因为如果你在generateTileGrid中的while循环于floorMaker迭代前创造了足够多的墙，它便会进行检查。

举个例子来说吧，如果你拥有砖块的当前值为62，最大值为64以及10个FloorMaker，你将通过检查进入while循环，但之后当你进行floorMaker迭代时便会创造10个以上的额外楼层 。

为了解决这点，在generateTileGrid（游戏邦注：即验证newPosition先添加一个楼层类型）中找到如下if检查：

if([self.tiles isValidTileCoordinateAt:newPosition] &&
![self.tiles isEdgeTileAt:newPosition] &&
[self.tiles tileTypeAt:newPosition] == MapTileTypeNone)

添加一个额外的检查去验证currentFloorCount，如下：

if([self.tiles isValidTileCoordinateAt:newPosition] &&
![self.tiles isEdgeTileAt:newPosition] &&
[self.tiles tileTypeAt:newPosition] == MapTileTypeNone &&
currentFloorCount < self.maxFloorCount)

现在当你运行时，你将获得准确的maxFloorCount.楼层。去计算看看吧！

当你靠近一个真正的程序生成关卡时，你会发现仍存在一些缺陷。你唯一能控制的只是关卡的大小。这真的足够吗？如果你能决定关卡带有更开放的空间或者带有更长且狭窄的走 廊不是更好？亲爱的，这都是关于属性啊！

调整地图生成

为了让地图类更多面，你将添加一些属性去影响关卡生成。

打开Map.h并添加如下属性：

@property (nonatomic) NSUInteger turnResistance;
@property (nonatomic) NSUInteger floorMakerSpawnProbability;
@property (nonatomic) NSUInteger maxFloorMakerCount;

这三个属性将通过控制FloorMaker的表现而直接影响地图生成：

turnResistance决定FloorMaker转弯的难度。将其设置为100会生成一条长而直的路径，而0则会生成迂回曲折的路径。

floorMakerSpawnProbability既能控制创造另一个FloorMaker的概率，也能生成砖块网格。设为100的值将确保游戏在每次迭代创造一个FloorMaker，而0则会导致没有额外的 FloorMaker会超越最初的那个。

maxFloorMaker是FloorMaker的最大数值，会在某一时刻被激活。

为了使用这些属性，你需要在代码中执行它们。首先确保将属性初始化为一个默认值。打开Map.m并添加如下代码到initWithGridSize：（在self.gridSize=gridSize之后）：

self.maxFloorCount = 110;
self.turnResistance = 20;
self.floorMakerSpawnProbability = 25;
self.maxFloorMakerCount = 5;

到Map.m的generateTileGrid中找到如下行：

floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];

将其变成如下if声明：

if ( floorMaker.direction == 0 || [self randomNumberBetweenMin:0 andMax:100] <= self.turnResistance ){
floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];
}

这一小小的改变能够保证游戏只会改变FloorMaker的方向，而前提是FloorMaker没有固定的方向或当turnResistance概率被超越时。就像之前所解释的，turnResistence的值更高 ，FloorMaker改变方向的概率也就更高。

接下来将下面一行内容：

if ( [self randomNumberBetweenMin:0 andMax:100] <= 50 )

改为：

if ( [self randomNumberBetweenMin:0 andMax:100] <= self.floorMakerSpawnProbability &&
self.floorMakers.count < self.maxFloorMakerCount )

现在，比起只有50%创造一个全新FloorMaker的机会，你可以调整概率去创造一个全新FloorMaker（如果现有FloorMaker的数值少于最大值）—-就像maxFloorMakerCount所定义的 那样。

打开MyScene.m并在self.map.maxFloorCount = 64后添加如下内容：

self.map.maxFloorMakerCount = 3;
self.map.floorMakerSpawnProbability = 20;
self.map.turnResistance = 30;

创建并运行

在继续之前，尝试着为这些属性和maxFloorCount设置不同值，以熟悉它们是如何影响关卡生成。

当你完成这一步，改变MyScene.m中的值，如下：

self.map.maxFloorCount = 110;
self.map.turnResistance = 20;
self.map.floorMakerSpawnProbability = 25;
self.map.maxFloorMakerCount = 5;

调整空间大小

到目前为止，FloorMaker每次只能放置一个楼层，但是这里所使用的方法能像第一步那样轻松地放置一些楼层，从而在生成地图上留出更多开放领域。

为了保持关卡生成的灵活性，你需要在Map.h文件上添加一些属性：

@property (nonatomic) NSUInteger roomProbability;
@property (nonatomic) CGSize roomMinSize;
@property (nonatomic) CGSize roomMaxSize;

然后在Map.m中的initWithGridSize：将这些属性初始化为默认值，即在设置maxFloorMakerCount行之后：

self.roomProbability = 20;
self.roomMinSize = CGSizeMake(2, 2);
self.roomMaxSize = CGSizeMake(6, 6);

基于默认值，20%的游戏时间将生成（2，2）砖块和（6，6）砖块大小的空间。

仍然在Map.m中插入如下方法：

- (NSUInteger) generateRoomAt:(CGPoint)position withSize:(CGSize)size
{
NSUInteger numberOfFloorsGenerated = 0;
for ( NSUInteger y = 0; y < size.height; y++)
{
for ( NSUInteger x = 0; x < size.width; x++ )
{
CGPoint tilePosition = CGPointMake(position.x + x, position.y + y);

if ( [self.tiles tileTypeAt:tilePosition] == MapTileTypeInvalid )
{
continue;
}

if ( ![self.tiles isEdgeTileAt:tilePosition] )
{
if ( [self.tiles tileTypeAt:tilePosition] == MapTileTypeNone )
{
[self.tiles setTileType:MapTileTypeFloor at:tilePosition];

numberOfFloorsGenerated++;
}
}
}
}
return numberOfFloorsGenerated;
}

在带有通过大小的通过位置上，该方法在左上角添加了一个空间，并传回一个代表被创造出来的砖块的数值。如果空间与任何现有的楼层重叠，那么重叠数便不会包含于方法所传 回的数值中。

为了开始生成空间，来到Map.m中的generateTileGrid，在currentFloorCount++后插入如下内容：

if ( [self randomNumberBetweenMin:0 andMax:100] <= self.roomProbability )
{
NSUInteger roomSizeX = [self randomNumberBetweenMin:self.roomMinSize.width
andMax:self.roomMaxSize.width];
NSUInteger roomSizeY = [self randomNumberBetweenMin:self.roomMinSize.height
andMax:self.roomMaxSize.height];

currentFloorCount += [self generateRoomAt:floorMaker.currentPosition
withSize:CGSizeMake(roomSizeX, roomSizeY)];
}

这在FloorMaker的当前位置上生成了一个新的空间，并且空间大小是介于最小和最大数值间，即只要满足创造一个空间（而非砖块）的概率便可。

为了测试这些属性，前往MyScene.m并通过在initWithSize的[self generate]前面插入如下代码而设置Map类的属性：

self.map.roomProbability = 20;
self.map.roomMinSize = CGSizeMake(2, 2);
self.map.roomMaxSize = CGSizeMake(6, 6);

创建并运行各种不同的值去明确它们是如何影响地图生成。

这时候，我们可能创造更多maxFloorCount楼层，因为空间创造逻辑并不能通过内部检查去确保所添加的砖块不会超越极限。

你已经创造了一个多面地图生成类，即每次当你发送生成信息到Map类的实体时便会出现一个新的关卡。通过改变这一属性，如果你想要一个大的开放空间或狭窄走廊，你便可以对 此进行直接控制。

相关拓展阅读：篇目1，篇目2（本文由游戏邦编译，转载请注明来源，或咨询微信zhengjintiao）

Procedural Level Generation in Games Tutorial: Part 1

by Kim Pedersen

If you’re new here, you may want to subscribe to my RSS feed or follow me on Twitter. Thanks for visiting!

Learn how to procedurally generate levels in games!

Note from Ray: This is a brand new Sprite Kit tutorial released as part of the iOS 7 Feast. Enjoy!

Most games you play have carefully designed levels that always remain the same. Experienced players know exactly what happens at any given time, when to jump and what button to press. While this is not necessarily a bad thing, it does to some extent reduce the game’s lifespan with a given player. Why play the same level over and over again?

One way to increase your game’s replay value is to allow the game to generate its content programmatically – also known as adding procedurally generated content.

In this tutorial, you will learn to create tiled dungeon-like levels using an algorithm called the Drunkard Walk. You will also create a reusable Map class with several properties for controlling a level’s generation.

This tutorial uses Sprite Kit, a framework introduced with iOS 7. You will also need Xcode 5. If you are not already familiar with Sprite Kit, I recommend you read the Sprite Kit Tutorial for Beginners on this site. For readers who are not yet ready to switch to Sprite Kit, fear not. You can easily rewrite the code in this tutorial to use Cocos2d.

Getting Started

Before getting started, let’s clear up one possible misconception: procedural should not be cnfused with random. Random means that you have little control over what happens, which should not be the case in game development.

Even in procedurally generated levels, your player should be able to reach the exit. What would be the fun of playing an endless runner like Canabalt if you got to a gap between buildings that would be impossible to jump? Or playing a platformer where the exit is in a place you cannot reach? In this sense, it might be even harder to design a procedurally generated level than to carefully craft your level in Tiled.

I assume, being the bad-ass coder that you are, that you scoff at such cautionary statements. To get started, download the starter project for this tutorial. Once downloaded, unzip the file and open the project in Xcode, and build and run. You should now see a screen similar to this:

Procedural Level Generation Starter Project

The starter project contains the basic building blocks of the game, including all necessary artwork, sound effects and music. Take note of the following important classes:

Map: Creates a basic 10×10 square that functions as the level for the game.

MapTiles: A helper class that manages a 2D grid of tiles. I will explain this class later in the tutorial.

DPad: Provides a basic implementation of a joystick to control the player’s character, a cat.

MyScene: Sets up the Sprite Kit scene and processes game logic.

Spend a few moments getting familiar with the code in the starter project before moving on. There are comments to help you understand how the code works. Also, try playing the game by using the DPad at the bottom-left corner to move the cat to the exit. Notice how the start and exit points change every time the level begins.

The Beginnings of a New Map

If you played the starter game more than once, you probably discovered that the game isn’t very fun. As Jordan Fisher writes in GamaSutra, game levels, especially procedurally generated ones, need to nail these three criteria to be successful:
Feasibility: Can you beat the level?

Interesting design: Do you want to beat it?

Skill level: Is it a good challenge?

Your current level fails two of these three criteria: The design is not very interesting, as the outer perimeter never changes, and it is too easy to win, as you can always see where the exit is when the level starts. Hence, to make the level more fun, you need to generate a better dungeon and make the exit harder to find.

The first step is to change the way you generate the map. To do so, you’ll delete the Map class and replace it with a new implementation.

Select Map.h and Map.m in the Project Navigator, press Delete and then select Move to Trash.

Next go to File\New\New File…, choose the iOS\Cocoa Touch\Objective-C class and click Next. Name the class Map, make it a Subclass of SKNode and click Next. Make sure the ProceduralLevelGeneration target is selected and click Create.Open Map.h and add the following code to the @interface section:

@property (nonatomic) CGSize gridSize;
@property (nonatomic, readonly) CGPoint spawnPoint;
@property (nonatomic, readonly) CGPoint exitPoint;

+ (instancetype) mapWithGridSize:(CGSize)gridSize;
- (instancetype) initWithGridSize:(CGSize)gridSize;

This is the interface that MyScene expects for the Map class. You specify here where to spawn the player and exit, and create some initializers to construct the class given a certain size.

Implement these in Map.m by adding this code to the @implementation section:
+ (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;
}

Here you add a stub implementation that simply sets the player spawn and exit points to CGPointZero. This will allow you to have a simple starting point – you’ll fill these out to be more interesting later.Build and run, and you should see the following:

Gone are the borders of the map and the feline hero gets sucked right into the exit, making the game unplayable – or really, really easy if you are a glass-half-full kind of person. Not really the a-maze-ing (pun intended) game you were hoping for, right? Well, time to put down some floors. Enter the Drunkard Walk algorithm.

The Drunkard Walk Algorithm

The Drunkard Walk algorithm is a kind of random walk and one of the simplest dungeon generation algorithms around. In its simplest implementation, the Drunkard Walk algorithm works as follows:

The principle of the Drunkard Walk algorithm.

Choose a random start position in a grid and mark it as a floor.

Pick a random direction to move (Up, Down, Left or Right).

Move in that direction and mark the position as a floor, unless it already is a floor.

Repeat steps 2 and 3 until a desired number of floors have been placed in the grid.

Nice and simple, eh? Basically, it is a loop that runs until a desired number of floors have been placed in the map. To allow the map generation to be as flexible as possible, you will start implementing the algorithm by adding a new property to hold the number of tiles to generate.

Open Map.h and add the following property:

@property (nonatomic) NSUInteger maxFloorCount;
Next, open Map.m and add the following method:
- (void) generateTileGrid
{
CGPoint startPoint = CGPointMake(self.gridSize.width / 2, self.gridSize.height / 2);

NSUInteger currentFloorCount = 0;

while ( currentFloorCount < self.maxFloorCount )
{
currentFloorCount++;
}
}

The above code begins to implement step 1 in the basic Drunkard Walk algorithm loop, but there is one significant difference. Can you spot it?

Solution Inside: Solution Show

generateTileGrid begins by setting a start position and then enters a loop that runs until the currentFloorCount is equal to the desired number of floors defined by the maxFloorCount property.When you initialize a Map object, you should invoke generateTileGrid to ensure that you create the grid. So, add the following code to initWithGridSize: in Map.m, after the _exitPoint = CGPointZero
line:
[self generateTileGrid];

Build and run to make sure the game compiles as expected. Nothing has changed since the last run. The cat is still sucked into the exit and there are still no walls. You still need to write the code to generate the floor, but before you do that, you need to understand the MapTiles helper class.

Managing the Tile Grid

The MapTiles class is essentially a wrapper for a dynamic C array that will manage a 2D grid for the Map class.

Note: If you’re wondering why I choose to use a C array instead of an NSMutableArray, it comes down to personal preference. I generally do not like boxing primitive data types like integers into objects and then unboxing them again to use them, and since the MapTiles grid is just an array of integers, I prefer a C array.

The MapTiles class is already in your project. If you’ve taken a glance through and feel you understand how it works well, feel free to skip ahead to the next section, Generating the Floor.

But if you’re unsure about how it works, keep reading to learn how to recreate it step-by-step, and I’ll explain how it works along the way.

To start, select MapTiles.h and MapTiles.m in the Project Navigator, press Delete and then select Move to Trash.

Go to File\New\File…, choose the iOS\Cocoa Touch\Objective-C class and click Next. Name the class MapTiles, make it a subclass of NSObject and click Next. Be sure the ProceduralLevelGenerationtarget is selected and click Create.

In order to make it easy to identify the type of tile, add this enum below the #import statement in MapTiles.h:
typedef NS_ENUM(NSInteger, MapTileType)
{
MapTileTypeInvalid = -1,
MapTileTypeNone = 0,
MapTileTypeFloor = 1,
MapTileTypeWall = 2,
};

If later on you want to extend the MapTiles class with further tile types, you should put those in this MapTileType enum.
Note: Notice the integer values you assign to each of the enums. They weren’t picked at random. Look in the tiles.atlas texture atlas and click the 1.png file, and you will see that it is the texture for the floor just as MapTileTypeFloor has a value of 1. This makes it easy to convert the 2D grid array into tiles later on.

Open MapTiles.h and add the following properties and method prototypes between @interface and @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;

You’ve added two read-only properties: count provides the total number of tiles in the grid and gridSize holds the width and height of the grid in tiles. You’ll find these properties handy later on. I’ll explain the five methods as you implement the code.

Next, open MapTiles.m and add the following class extension right above the @implementation line:
@interface MapTiles ()
@property (nonatomic) NSInteger *tiles;
@end

This code adds a private property tiles to the class. This is a pointer to the array that holds information about the tile grid.
Now implement initWithGridSize: in MapTiles.m after the @implementation line:

- (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;
}

You initialize the two properties in initWithGridSize:. Since the total number of tiles in the grid is equal to the width of the grid multiplied by the grid height, you assign this value to thecount property. Using this count, you allocate the memory for the tiles array with calloc, which ensures all variables in the array are initialized to 0, equivalent to the enumerated variableTileTypeEmpty.

As ARC will not manage memory allocated using calloc or malloc, you should release the memory whenever you deallocate the MapTiles object. Before initWithGridSize: but after @implementation, add the dealloc method:

- (void) dealloc
{
if ( self.tiles )
{
free(self.tiles);
self.tiles = nil;
}
}

dealloc frees the memory when you deallocate an object and resets the tiles property pointer to avoid it pointing to an array that no longer exists in memory.

Apart from the construction and deconstruction, the MapTiles class also has a few helper methods for managing tiles. But before you start implementing these methods, you need to understand how the tiles array exists in memory versus how it is organized in a grid.

Figure 1: How calloc organizes the variables in memory. Each number is the index of the variable in memory.

When you allocate memory for the tiles using calloc, it reserves n bytes for each array item, depending on the data type, and puts them end-to-end in a flat structure in memory (see figure 1).

This organization of tiles is hard to work with in practice. It is much easier to find a tile by using an (x,y) pair of coordinates, as illustrated in Figure 2, so that is how the MapTiles class should organize the tile grid.

Figure 2: How the MapTiles class organizes the variables in memory.

Thankfully, it is very easy to calculate the index of a tile in memory from an (x,y) pair of coordinates since you know the size of the grid from the gridSize property. The numbers outside the square in Figure 2 illustrate the x- and y-coordinates, respectively. For example, the (x,y) coordinates (1,2) in the grid will be index 9 of the array. You calculate this using the formula:index in memory = y * gridSize.width + x

With this knowledge, you can start implementing a method that will calculate an index from a pair of grid coordinates. For convenience, you will also create a method to ensure the grid coordinates are valid.
In MapTiles.m, add the following new methods:

- (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: tests if a given pair of coordinates is within the bounds of the grid. Notice how the method checks to see if it is outside of the bounds and then returns the opposite result, so if the coordinates are outside the bounds, it returns NO, and if they are not outside of the bounds, it returns YES. This is faster than checking if the coordinates are within the bounds, which would require the conditions to be AND-ed together instead of OR- ed.

tileIndexAt: uses the equation discussed above to calculate an index from a pair of coordinates, but before doing this, it tests if the coordinates are valid. If not, it returns MapTileTypeInvalid, which has a value of -1.

With the math in place, it is now possible to easily create the methods to return or set the tile type. So, add the following two methods after initWithGridSize: in MapTiles.m:

- (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;
}

The two methods calculate the index from the pair of coordinates passed using the tileIndexAt: method you just added and then either set or return the MapTileType from the tiles array.

Last but not least, add a method to determine if a given pair of tile coordinates is at the edge of the map. You’ll later use this method to ensure you do not place any floors at the edge of the grid, thereby making it impossible to encapsulate all floors behind walls.

- (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);
}

Referring to Figure 2 above, notice that border tiles would be any tile with an x-coordinate of 0 or gridSize.width – 1, since the grid indices are zero- based. Equally, an y-coordinate of 0 or gridSize.height – 1 would be a border tile.

Finally, when testing it’s nice to be able to see what your procedural generation is actually generating. Add the following implementation of description, which will output the grid to the console for easy debugging:

- (NSString *) description
{
NSMutableString *tileMapDescription = [NSMutableString stringWithFormat:@"<%@ = %p | \n",
[self class], self];

for ( NSInteger y = ((NSInteger)self.gridSize.height – 1); y >= 0; y– )
{
[tileMapDescription appendString:[NSString stringWithFormat:@"[%i]“, y]];

for ( NSInteger x = 0; x < (NSInteger)self.gridSize.width; x++ )
{
[tileMapDescription appendString:[NSString stringWithFormat:@"%i",
[self tileTypeAt:CGPointMake(x, y)]]];
}
[tileMapDescription appendString:@"\n"];
}
return [tileMapDescription stringByAppendingString:@">"];
}

This method simply loops through the grid to create a string representation of the tiles.

That was a lot of text and code to take in, but what you’ve built will make the procedural level generation much easier, since you can now abstract the grid handling from the level generation. Now it’s time to lay down some ground.

Generating the Floor

You’re going to place ground or floor tiles procedurally in the map using the Drunkard Walk algorithm discussed above. In Map.m, you already implemented part of the algorithm so that it finds a random start position (step 1) and loops a desired number of times (step 4). Now you need to implement steps 2 and 3 to generate the actual floor tiles within the loop you created.

To make the Map class a bit more flexible, you’ll start by adding a dedicated method to generate a procedural map. This will also be handy if you later need to regenerate the map.

Open Map.h and add the following method declaration to the interface:

- (void) generate;
In Map.m, add the following import to the top of the file:
#import “MapTiles.h”
Add the following code right above the @implementation line:
@interface Map ()
@property (nonatomic) MapTiles *tiles;
@end

The class extension holds one private property, which is a pointer to a MapTiles object. You’ll use this object for easy grid handling in the map generation. You’re keeping it private since you don’t want to change the MapTiles object from outside the Map class.

Next, implement the generate method in Map.m:

- (void) generate
{
self.tiles = [[MapTiles alloc] initWithGridSize:self.gridSize];
[self generateTileGrid];
}

First the method allocates and initializes a MapTiles object, then it generates a new tile grid by calling generateTileGrid.
In Map.m, go to initWithGridSize: and delete this line:

[self generateTileGrid];

You deleted that line because map generation should no longer occur immediately when you create a Map object.

It’s time to add the code to generate the floor of the dungeon. Do you remember the remaining steps of the Drunkard Walk algorithm? You choose a random direction and then place a floor at the new coordinates.

The first step is to add a convenience method to provide a random number between two values. Add the following method in Map.m:- (NSInteger) randomNumberBetweenMin:(NSInteger)min andMax:(NSInteger)max
{
return min + arc4random() % (max – min);
}
You’ll use this method to return a random number between min and max, both inclusive.

Return to generateTileGrid and replace its contents with the following:

CGPoint startPoint = CGPointMake(self.tiles.gridSize.width / 2, self.tiles.gridSize.height / 2);
// 1
[self.tiles setTileType:MapTileTypeFloor at:startPoint];
NSUInteger currentFloorCount = 1;
// 2
CGPoint currentPosition = startPoint;
while ( currentFloorCount < self.maxFloorCount )
{
// 3
NSInteger direction = [self randomNumberBetweenMin:1 andMax:4];
CGPoint newPosition;
// 4
switch ( direction )
{
case 1: // Up
newPosition = CGPointMake(currentPosition.x, currentPosition.y – 1);
break;
case 2: // Down
newPosition = CGPointMake(currentPosition.x, currentPosition.y + 1);
break;
case 3: // Left
newPosition = CGPointMake(currentPosition.x – 1, currentPosition.y);
break;
case 4: // Right
newPosition = CGPointMake(currentPosition.x + 1, currentPosition.y);
break;
}
//5
if([self.tiles isValidTileCoordinateAt:newPosition] &&
![self.tiles isEdgeTileAt:newPosition] &&
[self.tiles tileTypeAt:newPosition] == MapTileTypeNone)
{
currentPosition = newPosition;
[self.tiles setTileType:MapTileTypeFloor at:currentPosition];
currentFloorCount++;
}
}
// 6
_exitPoint = currentPosition;
// 7

NSLog(@”%@”, [self.tiles description]);

This is what the code is doing:

It marks the tile at coordinates startPoint in the grid as a floor tile and therefore initializes currentFloorCount with a count of 1.

currentPosition is the current position in the grid. The code initializes it to the startPoint coordinates where the Drunkard Walk algorithm will start.

Here the code chooses a random number between 1 and 4, providing a direction to move (1 = UP, 2 = DOWN, 3 = LEFT, 4 = RIGHT).Based on the random number chosen in the above step, the code calculates a new position in the grid.

If the newly calculated position is valid and not an edge, and does not already contain a tile, this part adds a floor tile at that position and increments currentFloorCount by 1.

Here the code sets the last tile placed to the exit point. This is the goal of the map.

Lastly, the code prints the generated tile grid to the console.

Build and run. The game runs with no visible changes, but it fails to write the tile grid to the console. Why is that?

Solution Inside: Solution Show

To fix this, go to MyScene.m and in initWithSize:, replace the line self.map = [[Map alloc] init] with the following:
self.map = [[Map alloc] initWithGridSize:CGSizeMake(48, 48)];

self.map.maxFloorCount = 64;

[self.map generate];

This generates a new map with a grid size of 48 by 48 tiles and a desired maximum floor count of 64. Once you set the maxFloorCount property, you generate the map.

Build and run again, and you should see an output that resembles something similar to, but probably not exactly like (remember, it’s random), the following:

HOORAY!! You have generated a procedural level. Pat yourself on the back and get ready to show your masterpiece on the big – or small – screen.

Converting a Tile Grid into Tiles

Plotting your level in the console is a good way to debug your code but a poor way to impress your player. The next step is to convert the grid into actual tiles.

The starter project already includes a texture atlas containing the tiles. To load the atlas into memory, add a private property to the class extension of Map.m, as well as a property to hold the size of a tile:

@property (nonatomic) SKTextureAtlas *tileAtlas;

@property (nonatomic) CGFloat tileSize;

Initialize these two properties in initWithGridSize:, just after setting the value of _exitPoint:

self.tileAtlas = [SKTextureAtlas atlasNamed:@"tiles"];

NSArray *textureNames = [self.tileAtlas textureNames];

SKTexture *tileTexture = [self.tileAtlas textureNamed:(NSString *)[textureNames firstObject]];
self.tileSize = tileTexture.size.width;

After loading the texture atlas, the above code reads the texture names from the atlas. It uses the first name in the array to load a texture and stores that texture’s width as tileSize. This code assumes textures in the atlas are squares (same width and height) and are all of the same size.

Note: Using a texture atlas reduces the number of draw calls necessary to render the map. Every draw call adds overhead to the system because Sprite Kit has to perform extra processing to set up the GPU for each one. By using a single texture atlas, the entire map may be drawn in as few as a single draw call. The exact number will depend on several things, but in this app, those won’t come into play. To learn more, check out Chapter 25 in iOS Games by Tutorials,
Performance: Texture Atlases.Still inside Map.m, add the following method:

- (void) generateTiles
{
// 1
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
for ( NSInteger x = 0; x < self.tiles.gridSize.width; x++ )
{
// 2
CGPoint tileCoordinate = CGPointMake(x, y);
// 3
MapTileType tileType = [self.tiles tileTypeAt:tileCoordinate];
// 4
if ( tileType != MapTileTypeNone )
{
// 5
SKTexture *tileTexture = [self.tileAtlas textureNamed:[NSString stringWithFormat:@"%i", tileType]];
SKSpriteNode *tile = [SKSpriteNode spriteNodeWithTexture:tileTexture];
// 6
tile.position = tileCoordinate;
// 7
[self addChild:tile];
}
}
}
}

generateTiles converts the internal tile grid into actual tiles by:

Two for loops, one for x and one for y, iterate through each tile in the grid.

This converts the current x- and y-values into a CGPoint structure for the position of the tile within the grid.

Here the code determines the type of tile at this position within the grid.

If the tile type is not an empty tile, then the code proceeds with creating the tile.

Based on the tile type, the code loads the respective tile texture from the texture atlas and assigns it to a SKSpriteNode object. Remember that the tile type (integer) is the same as the file name of the texture, as explained earlier.
The code sets the position of the tile to the tile coordinate.

Then it adds the created tile node as a child of the map object. This is done to ensure proper scrolling by grouping the tiles to the map where they belong.

Finally, make sure the grid is actually turned into tiles by inserting the following line into the generate method in Map.m, after [self generateTileGrid]:

[self generateTiles];

Build and run — but the result is not as expected. The game incorrectly places the tiles in a big pile, as illustrated here:

The reason is straightforward: When positioning the tile, the current code sets the tile’s position to the position within the internal grid and not relative to screen coordinates.

You need a new method to convert grid coordinates into screen coordinates, so add the following to Map.m:

- (CGPoint) convertMapCoordinateToWorldCoordinate:(CGPoint)mapCoordinate
{
return CGPointMake(mapCoordinate.x * self.tileSize, (self.tiles.gridSize.height – mapCoordinate.y) * self.tileSize);
}

By multiplying the grid (map) coordinate by the tile size, you calculate the horizontal position. The vertical position is slightly more complicated. Remember that the coordinates (0,0) in Sprite Kit represent the bottom-left corner. In the tile grid, the position of (0,0) is the top-left corner (see Figure 2 above). Hence, in order to correctly position the tile, you need to invert its vertical placement. You do this by subtracting the y-position of the tile in the grid by the total height of the grid and multiplying it by the tile size.

Revisit generateTiles and change the line that sets tile.position to the following:

tile.position = [self convertMapCoordinateToWorldCoordinate:CGPointMake(tileCoordinate.x, tileCoordinate.y)];

Also, change the line that sets _exitPoint in generateTileGrid to the following:

_exitPoint = [self convertMapCoordinateToWorldCoordinate:currentPosition];

Build and run – oh no, where did the tiles go?

Well, they are still there – they’re just outside the visible area. You can easily fix this by changing the player’s spawn position. You will apply a simple yet effective strategy where you set the spawn point to the position of the startPoint in generateTileGrid.

Go to generateTileGrid and add the following line at the very bottom of the method:

_spawnPoint = [self convertMapCoordinateToWorldCoordinate:startPoint];

The spawn point is the pair of screen coordinates where the game should place the player at the beginning of the level. Hence, you calculate the world coordinates from the grid coordinates.

Build and run, and take the cat for a walk around the procedural world. Maybe you will even find the exit?

Try playing around with different grid sizes and max number of floor tiles to see how it affects the map generation.
One obvious issue now is that the cat can stray from the path. And we all know what happens when cats stray, right? All the songbirds of the world shiver. So, time to put up some walls.

Adding Walls

Open Map.m and add the following method:
- (void) generateWalls
{
// 1
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
for ( NSInteger x = 0; x < self.tiles.gridSize.width; x++ )
{
CGPoint tileCoordinate = CGPointMake(x, y);

// 2
if ( [self.tiles tileTypeAt:tileCoordinate] == MapTileTypeFloor )
{
for ( NSInteger neighbourY = -1; neighbourY < 2; neighbourY++ )
{
for ( NSInteger neighbourX = -1; neighbourX < 2; neighbourX++ )
{
if ( !(neighbourX == 0 && neighbourY == 0) )
{
CGPoint coordinate = CGPointMake(x + neighbourX, y + neighbourY);

// 3
if ( [self.tiles tileTypeAt:coordinate] == MapTileTypeNone )
{
[self.tiles setTileType:MapTileTypeWall at:coordinate];
}
}
}
}
}
}
}
}

Figure 3: How to identify surrounding tiles in a grid.

The strategy applied by generateWalls is to first loop through each tile of the grid.
It does this until it identifies a floor tile (MapTileTypeFloor).

It then checks the surrounding tiles and marks these as walls (MapTileTypeWall) if no tile is placed there already (MapTileTypeNone).

The inner for loops (after //2) might seem a bit strange at first. It looks at each tile that surrounds the tile at coordinate (x,y). Take a peek at Figure 3 and see how the tiles you want are one less, equal to, and one more than the original index. The two for loop gives just that, starting at -1 and looping through to +1. Adding one of these integers to the original index inside the for loop, you find each neighbor.

What if the tile you’re checking is at the border of the grid? In that case, this check would fail, as the index would be invalid, correct?

Yes, but luckily this situation is mitigated by the tileTypeAt: method on the MapTiles class. If an invalid coordinate is sent to tileTypeAt:, the method will return a MapTileTypeInvalid value.Consider the line after //3 in generateWalls and notice it only changes the tile to a wall tile if the returned tile type is MapTileTypeNone.

To generate the wall tiles, go back to generate in Map.m and add the following line of code after [self generateTileGrid] and before [self generateTiles]:
[self generateWalls];

Build and run. You should now see wall tiles surrounding the floor tiles. Try moving the cat around – notice anything strange?

Walls are kind of pointless if you can walk right through them. There are several ways to fix this problem, one of which is described in the Collisions and Collectables: How To Make a Tile-Based Game with Cocos2D 2.X, Part 2 tutorial on this site. In this tutorial you will do it a bit differently by using the build-in physics engine in Sprite Kit. Everyone likes new tech, after all.

Procedural Collision Handling: Theory

There are many ways you could turn wall tiles into collision objects. The most obvious is to add a physicsBody to each wall tile, but that is not the most efficient solution. Another way, as described by Steffen Itterheim, is to use the Moore Neighborhood algorithm, but that is a tutorial in its own right.

Instead, you will implement a fairly simple method where connected wall segments are combined into a single collision object. Figure 4 illustrates this method.

Figure 4: Using a very simple method, the walls are turned into batched collision wall objects.

The method will iterate over all tiles in the map using the following logic:

Starting at (0,0), iterate the tile grid until you find a wall tile.

When you find a wall tile, mark the tile grid position. This is the starting point for the collision wall.

Move to the next tile in the grid. If this is also a wall tile, then increase the number of tiles in the collision wall by 1.

Continue step 3 until you reach a non-wall tile or the end of the row.

When you reach a non-tile or the end of the row, create a collision wall from the starting point with a size of the number of tiles in the collision wall.

Start the iteration again, go back to step 2 and repeat until you’ve turned all wall tiles in the grid into collision walls.

Note: The method described here is very basic and could be optimized further. For instance, you could iterate the map both horizontally and vertically. Iterating the map horizontally would omit all collision walls that are the size of one tile. You would then pick these up when iterating the map vertically, further decreasing the number of collision objects, which is always a good thing.

It’s time to put theory into practice.

Procedural Collision Handling: Practice

Look at initWithSize: in MyScene.m and see that the code to activate the physics engine is already in the starter project. Since Ray did an excellent job explaining how to set up the physics engine in the Sprite Kit for Beginners tutorial, I’ll only explain it here in the context of procedural level generation.

When the code creates the physicsBody of the player object, it sets it to collide with walls by adding the ollisionTypeWall to the collisionBitMask. That way, the physics engine will automatically bounce the player off any wall objects.

However, when you created the walls in generateWalls, you didn’t create them as physics objects – only as simple SKSpriteNodes. Hence, when you build and run the game the player will not collide with the walls.

You’re going to simplify wall collision object creation by adding a helper method. Open Map.m and add the following code:

// Add at the top of the file together with the other #import statements
#import “MyScene.h”

// Add with other methods
- (void) addCollisionWallAtPosition:(CGPoint)position withSize:(CGSize)size
{
SKNode *wall = [SKNode node];

wall.position = CGPointMake(position.x + size.width * 0.5f – 0.5f * self.tileSize,
position.y – size.height * 0.5f + 0.5f * self.tileSize);
wall.physicsBody = [SKPhysicsBody bodyWithRectangleOfSize:size];
wall.physicsBody.dynamic = NO;
wall.physicsBody.categoryBitMask = CollisionTypeWall;
wall.physicsBody.contactTestBitMask = 0;
wall.physicsBody.collisionBitMask = CollisionTypePlayer;

[self addChild:wall];
}

This method creates and adds an SKNode to the map with the passed position and size. It then creates a non-moveable physics body for the node the size of the node, and ensures that the physics engine performs collision handling when the player collides with the node.

It’s time to implement the collision wall generation. Add the following method:

- (void) generateCollisionWalls
{
for ( NSInteger y = 0; y < self.tiles.gridSize.height; y++ )
{
CGFloat startPointForWall = 0;
CGFloat wallLength = 0;
for ( NSInteger x = 0; x <= self.tiles.gridSize.width; x++ )
{
CGPoint tileCoordinate = CGPointMake(x, y);
// 1
if ( [self.tiles tileTypeAt:tileCoordinate] == MapTileTypeWall )
{
if ( startPointForWall == 0 && wallLength == 0 )
{
startPointForWall = x;
}
wallLength += 1;
}
// 2
else if ( wallLength > 0 )
{
CGPoint wallOrigin = CGPointMake(startPointForWall, y);
CGSize wallSize = CGSizeMake(wallLength * self.tileSize, self.tileSize);
[self addCollisionWallAtPosition:[self convertMapCoordinateToWorldCoordinate:wallOrigin]
withSize:wallSize];
startPointForWall = 0;
wallLength = 0;
}
}
}
}

Here you perform the six steps described earlier.

You iterate through each row until you find a wall tile. You set a starting point (tile coordinate pair) for the collision wall and then increase the
wallLength by one. Then you move to the next tile. If this is also a wall tile, you repeat these steps.

If the next tile is not a wall tile, you calculate the size of the wall in points by multiplying the tile size, and you convert the starting point into world coordinates. By passing the starting point (as world coordinates in pixels) and size (in pixels), you generate a collision wall using the addCollisionWallAtPosition:withSize: helper method you added above.

Go to generate in Map.m and add the following line of code after [self generateTiles] to ensure the game generates collision walls when it generates a tile map:
[self generateCollisionWalls];

Build and run. Now the cat is stuck within the walls. The only way out is to find the exit – or is it?

Where to Go from Here?

You’ve earned a basic understanding of how to generate procedural levels in your game. Here is the full source code for the first part of the tutorial.

In the second part of this tutorial, you will extend the map generation code even further by adding rooms. You’ll also make map generation more controllable by adding several properties that will influence the process.If you have any comments or suggestions related to this tutorial, please join the forum discussion below

Note from Ray: This is a brand new Sprite Kit tutorial released as part of the iOS 7 Feast. Enjoy!

This is the second and final part of the tutorial that teaches you how to implement procedurally generated levels using the Drunkard Walk algorithm.

In the first part of the tutorial, you created the basic level generation and learned how to use Sprite Kit’s build-in physics engine to set up collision detection so the player cannot walk through walls.

Now in Part 2, you’re going to extend your algorithm to generate a more dungeon-like level with more open spaces, allow for the simultaneous creation of multiple paths and include properties to put you in better control of the level generation process.

You will continue where you left off in the first part, so grab the completed project from Part 1 if you do not have it already.

Get ready to level up again!

The FloorMaker Class
You might have noticed that the levels generated in Part 1 tend to be long, winding corridors. This is obviously not a very interesting level design and makes finding the exit less than a challenge.

That you get long corridors is not surprising. After all, the algorithm you’ve implemented moves one tile in a random direction and then does that again, thereby connecting it to the previous tile positioned. While there is a chance this might generate wide room-like areas, it isn’t likely to do so often enough to create maps that look like dungeons.

Now you’ll modify the algorithm so that it performs several random walks simultaneously. Basically, it will be like throwing all the drunken people out of the bar and asking them to go home.

The map generation needs to track different paths being created at the same time. You’ll do this using an instance of a class named FloorMaker for each path.

Go to File\New\New File…, choose the iOS\Cocoa Touch\Objective-C class template and click Next. Name the class FloorMaker, make it a subclass of NSObject and click Next. Be sure the ProceduralLevelGeneration target is selected and then click Create.

Open FloorMaker.h and add the following code between @interface and @end:

Now open FloorMaker.m and implement the initializer method:

FloorMaker is fairly simple. It has two properties to keep track of the current position and direction, and an initializer that allows you to set these properties when you create an instance of the class.

With the FloorMaker class in place, you can move on to using it in the map generation.

Running the FloorMaker
The first step is to import FloorMaker into Map.m. Add the following code after the existing #import pre-processor directives:

You’ll refactor generateTileGrid to use multiple FloorMaker objects simultaneously, but you’ll do so in stages. First, make the following modifications so that it uses a single FloorMaker.

Inside generateTileGrid, replace this line:

With this one:

You no longer need to store the current position in a local variable, because each FloorMaker will store its own current position. So you delete the currentPosition and add a variable named floorMaker, initialized at startPoint.

Now that you’ve deleted currentPosition, replace each use of currentPosition with floorMaker.currentPosition. Don’t worry, Xcode will give you errors to help you find them. ;]

Next, replace this line:

With this one:

Just as you replaced the local variable currentPosition with floorMaker.currentPosition, here you replace the local variable direction with floorMaker.direction, and for the same reason.

Finally, modify the switch check to use floorMaker.direction instead of the local variable direction.

Build and run, and the app should run exactly as it did before.

Now you’ll change Map to support using multiple FloorMakers. Add the following property to the Map class extension in Map.m:

The floorMakers array holds a reference to all active FloorMakers.

Then go back to generateTileGrid and make the following changes to use the floorMakers array instead of a local FloorMaker object.

Replace the following lines:

With these:

You add the __block type specifier to the currentFloorCount declaration so that you can modify its value from within an Objective-C block, which you’ll be doing shortly. You remove the local floorMaker variable and instead initialize the Map‘s floorMakers property with a mutable array containing a single FloorMaker object. Later, you’ll be adding more FloorMakers to this array.

Modify the contents of the while loop in generateTileGrid as follows:

This changes the method so that it iterates over the objects in the floorMakers array and performs the Drunkard Walk for each one.

Eventually you’ll have more than one FloorMaker running, but you can only have one exit point. In order to ensure that the last floor tile the game creates becomes the exit, move the line that sets _exitPoint from where it is now to immediately after the currentFloorCount++; line. This simply assigns the _exitPoint after the game creates all the floor tiles, and the final tile created becomes the exit point.

Once again, build and run, and note that things seem unchanged.

Allowing for Multiple Paths

While the map generation works, it is still only running one instance of the FloorMaker at any given time, so the levels that are produced are very similar to what you got in Part 1 of the tutorial. Since the idea of the FloorMaker is to have many of them, you’re now going to change the generateTileGrid method slightly to allow generation of more FloorMakers.

Back in generateTileGrid, add the following code at the end of the block, just before the closing brace and bracket }]:

This code adds a 50% chance that a new FloorMaker will be created at each step of a FloorMaker. Notice that the code creates newFloorMaker with a position equal to the current position of the current FloorMaker, but with a random direction.Build and run again. Notice anything odd?

There are two issues here. First, the algorithm now generates much wider rooms, rather than long corridors. You’ll make some changes later to influence the types of maps it creates, so ignore this issue for now.

The second problem is easy to miss, but if you generate a few maps and count the floor tiles, you’ll find your app no longer respects the maxFloorCount value. It will actually produce some number of floor tiles between maxFloorCount and maxFloorCount + the number of floorMakers – 1. That’s because the while loop in generateTileGrid checks to see if the you’ve created enough walls before it iterates over floorMakers.

For example, if you had a current value of 62 tiles, a max of 64 and 10 FloorMakers, you would pass the check to enter the while loop, but then you’d produce up to 10 additional floor tiles when you iterated over floorMakers.

To fix this, find the following if check in generateTileGrid that validates newPosition prior to adding a floor type:

And add an additional check to validate currentFloorCount, like this:

Now when you run, you’ll get exactly maxFloorCount floor tiles. Go ahead and count them!

While you are getting close to having a true procedurally generated level, there is still one major disadvantage: The only thing you are able to control is how big you want the level to be. Is that really enough? Wouldn’t it be great if you could control if you wanted a level with big open spaces or a level with long narrow corridors? I bet it would! It’s all about the properties, baby.

Fine-Tuning Map Generation

To make the Map class more versatile, you’re going to add a few properties that will impact the level generation.

Open Map.h and adding the following properties:

These three properties will have a direct impact on the map generation by controlling how a FloorMaker behaves:

turnResistance determines how hard it is for the FloorMaker to make a turn. Setting this to 100 will generate one long, straight path whereas 0 will generate paths with lots of twists and turns.

floorMakerSpawnProbability controls the probability of creating another FloorMaker while generating the tile grid. A value of 100 will ensure the game creates a FloorMaker at each iteration, whereas 0 will result in no additional FloorMakers beyond the initial one.

maxFloorMakerCount is the max number of FloorMakers that can be active at one time.

For these properties to be of any use, you need to implement them in the code. First make sure the properties are properly initialized to a default value. Open Map.m and add the following code to initWithGridSize: just after self.gridSize = gridSize:

Go to generateTileGrid in Map.m and find the following line:

And turn it into the following if statement:

This small change ensures that the game only changes the direction of a FloorMaker if the FloorMaker has no set direction or when the turnResistance probability has been exceeded. As explained above, the higher the value of turnResistance, the higher the probability of the FloorMaker changing direction.

Next, change the line:

…to this:

Now, instead of a hard-coded 50% chance of creating a new FloorMaker, you can adjust the probability to make it more or less likely to create a new FloorMaker if the number of existing FloorMakers is less than the maximum allowed, as defined by maxFloorMakerCount.

Map generated with a maxFloorCount = 110, maxFloorMakerCount = 5, floorMakerSpawnProbability = 25 and turnResistance = 20. Experiment and see what sort of levels you get.

Open MyScene.m and add the following lines after the line self.map.maxFloorCount = 64:

Build and run.

Procedural Levels, tweaked valuesBefore moving on, experiment with setting different values for these properties as well as the maxFloorCount to become familiar with how they affect level generation.

When you’re finished, change the values in MyScene.m to look like these:

———————

Fine-Tuning Room Size

So far, a FloorMaker only places one floor at a time, but the method applied here can just as easily place several floor tiles in one step, allowing for more open areas within the generated map.

To remain flexible with the level generation, first add a few properties to the Map.h file:

Then initialize these properties with a default value in initWithGridSize: in Map.m, right after the line that sets maxFloorMakerCount:

By default, 20% of the time the game will generate a room with a size between (2,2) tiles and (6,6) tiles.

Still in Map.m, insert the following method:

This method adds a room with its top-left corner at the passed position with the passed size and returns a value representing the number of tiles created. If the room overlaps any existing floor tiles, then that overlap is not counted in the number returned by the method.

To start generating rooms, go to generateTileGrid in Map.m and insert the following lines just after currentFloorCount++:

This generates a new room at the current position of the FloorMaker with a room size that is between the minimum and maximum, so long as the probability of creating a room instead of a tile has been met.

To experiment with these new properties, go to MyScene.m and set the properties of the Map class by inserting the following code right before [self generate] in initWithSize::

Build and run with various different values to see how they affect the map generation.

At this point, it’s once again possible to create more than maxFloorCount floor tiles, because the room creation logic does not check internally to make sure the added tiles for the room doesn’t exceed the limit.

You’ve created a versatile map generation class that whips out a new level every time you send a generate message to an instance of the Map class. By changing its properties, you can directly control if you want big open spaces or tight narrow corridors.

Where to Go from Here?Here’s the final project with all of the code from the tutorial.

The Drunkard Walk algorithm is an extremely powerful yet simple procedural generation method that you can easily extend to produce any variation of dungeon you might like. But it is just one of many procedural generation algorithms out there and all of them have their strengths and weaknesses.

One great method for creating cave levels is cellular automata, which has infinite customization possibilities.

Another great method to learn is Binary Space Partitioning (BSP), which creates some wicked-looking grid-like dungeon levels.

Let me know if you enjoyed this series and would like to see more in this series on procedural level generation. Also, if you have any comments or suggestions related to this tutorial, please join the forum discussion below!