作者：Kim Pedersen

注：这是作为iOS 7 Feast组成部分的全新Sprite Kit教程。本篇文章是该系列教程的第二部分也是最后一部分，即教授你如何使用Drunkard Walk算法去执行程序生成关卡。

在上篇教程中，你已经创造了基本的关卡生成，并学会如何使用Sprite Kit的嵌入式物理引擎去设置碰撞检测，从而让玩家不能穿越墙壁。

而在今天的下篇教程中，你将延伸算法在更开放的空间中生成更多地牢式关卡，顾及多条路径的同时创造并包含属性让自己更好地控制关卡生成过程。

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类的实体时便会出现一个新的关卡。通过改变这一属性，如果你想要一个大的开放空间或狭窄走廊，你便可以对此进行直接控制。

接下来该做什么？

本文是这系列教程中所有代码的最后部分。

Drunkard Walk算法真的是一种强大又简单的程序生成方法，即你可以通过轻松的扩展去生成自己想要创造的各种地牢变量。但这只是众多程序生成算法中的一种，而其它的所有算法也都有自己的优势和劣势。

（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

Procedural Level Generation in Games Tutorial: Part 2

By Kim Pedersen

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 values
Before 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!(source:raywenderlich)