IDC资讯中心
项目介绍：
引
前段时间做了一道题，要求实现汉诺塔游戏的自动解题动画：
汉诺塔游戏应该都了解规则：
1、将盘子全部移动到塔C
2、每次只能移动一个圆盘；
3、大盘不能叠在小盘上面。
要求由用户输入盘子的数量，绘制盘子和塔，点击开始后自动解题，并以动画移动盘子的形式演示。
觉得还挺有意思的，而且在做的过程中也踩了一些坑，用了一些技巧和优化，因此记录下来。
效果：
汉诺塔解法
这道题中汉诺塔的解法本身并不是难点。
1、如果只有一个盘子，那就直接从A移动到C；
2、如果有两个盘子，那就要先把小盘子移动到B，然后大盘子移动到C，再把小盘子移动到C；
3、如果有三个盘子，那就要先把上面两个盘子移动到B（借助C的辅助），然后把底下的大盘子移动到C，然后把B上的两个盘子借助A移动到C；
……
4、如果有n个盘子，那就要先把上面n-1个盘子移动到B（借助C的辅助），然后把底下的大盘子移动到C，然后把B上的n-1盘子借助A移动到C。
综上所述，除了一个盘子的情况直接移动，其余都需要借助其他盘子的帮助，复杂情况虽然不一样，但是过程是递归不断重复的。
递归代码如下：
// 确定提交
- (void)submit {
if ([self.numberField.text isEqualToString:@""]) {
NSLog(@"未输入内容");
UIAlertController *alertController = [UIAlertController alertControllerWithTitle:@"提示" message:@"您还未输入层数!" preferredStyle:UIAlertControllerStyleAlert];
UIAlertAction *okAction = [UIAlertAction actionWithTitle:@"确定" style:UIAlertActionStyleDefault handler:^(UIAlertAction *action) {
}];
[alertController addAction:okAction];
[self presentViewController:alertController animated:YES completion:nil];
} else {
self.diskNumber = [self.numberField.text integerValue];
self.moveCount = 0;
[self hanoiWithDisk:self.diskNumber towers:@"A" :@"B" :@"C"];
NSLog(@">>移动了%ld次", self.moveCount);
}
}
// 移动算法
- (void)hanoiWithDisk:(NSInteger)diskNumber towers:(NSString *)towerA :(NSString *)towerB :(NSString *)towerC {
if (diskNumber == 1) {// 只有一个盘子则直接从A塔移动到C塔
[self move:1 from:towerA to:towerC];
} else {
[self hanoiWithDisk:diskNumber-1 towers:towerA :towerC :towerB];// 递归把A塔上编号1~diskNumber-1的盘子移动到B塔，C塔辅助
[self move:diskNumber from:towerA to:towerC];// 把A塔上编号为diskNumber的盘子移动到C塔
[self hanoiWithDisk:diskNumber-1 towers:towerB :towerA :towerC];// 递归把B塔上编号1~diskNumber-1的盘子移动到C塔，A塔辅助
}
}
// 移动过程
- (void)move:(NSInteger)diskIndex from:(NSString *)fromTower to:(NSString *)toTower {
NSLog(@"第%ld次移动：把%ld号盘从%@移动到%@", ++self.moveCount, diskIndex, fromTower, toTower);
}三层盘子时：
四层盘子时：
可见算法是正确的，接下来就是实现绘制和动画的问题。
绘制塔和盘子
解决了算法的问题，下一步我们要绘制图形了。
这里为了方便我决定全部用UIView来做，比如塔就是一横一竖两个UIView，每个盘子都是一个UIView。
为了方便给盘子编号，创建一个继承自UIView的盘子类，加上编号属性：
#pragma mark - Disk Model
// 自定义的盘子模型，在UIView基础上加上编号属性
@interface OXDiskModel : UIView
@property NSInteger index;
@end
@implementation OXDiskModel
@end因为这个代码很短，没必要新开一个文件，直接在绘制图形的ViewController.m文件中加上这个代码就可以实现了。
对于塔，一开始我直接在界面上绘制三个塔的6条线，很简单，但是在涉及到动画的时候，需要频繁用到每个塔的位置以及塔上已有的盘子数量才能确定盘子移动到的位置，这就很麻烦，而且不稳定，代码很复杂。
后来我改成把塔也抽象出来成一个塔类，在其类中绘制两条线，并且加上塔名称以及塔上盘子数量的属性，这样就可以直接调用了，在递归算法中，我们可以直接传递三个塔对象，可以很方便地计算，减少了大量的代码，代码结构也更加清晰。
塔的绘制代码和属性就不写出来了，有单独的类文件，可以直接在工程中看，这里直说思想，对于一些适合抽离出来的对象，我们应该尽可能抽象成对应的类，将它的操作、行为、属性等放在类中写，可以极大地简化代码、使代码结构更清晰。
这样，我们就可以根据屏幕大小算出每个塔合适的大小，然后去创建三个塔对象，添加到界面上就好了。
// 三座塔
- (void)initThreeTower {
// 添加三座塔
NSInteger height = (SCREENHEIGHT - 150)/3 - 30;
for (int i = 0; i < 3; i++) {
OXTowerView *tower = [[OXTowerView alloc] initWithFrame:CGRectMake((SCREENWIDTH-250)/2, 130 + (height+30)*i, 250, height+5)];
tower.diskNumber = 0;
[self.view addSubview:tower];
[self.towerArray addObject:tower];
// 塔号
UILabel *towerLabel = [[UILabel alloc] initWithFrame:CGRectMake(12, tower.frame.origin.y + height + 5, SCREENWIDTH-24, 15)];
switch (i) {
case 0:
towerLabel.text = @"A";
tower.towerId = @"A";
tower.diskNumber = self.diskNumber;// 一开始盘子都在塔A上
break;
case 1:
towerLabel.text = @"B";
tower.towerId = @"B";
break;
case 2:
towerLabel.text = @"C";
tower.towerId = @"C";
break;
default:
break;
}
towerLabel.textColor = [UIColor darkGrayColor];
towerLabel.textAlignment = NSTextAlignmentCenter;
towerLabel.font = [UIFont systemFontOfSize:14];
[self.view addSubview:towerLabel];
}
}然后根据输入的盘子层数，动态算出每个盘子合适的高度以及每个盘子的宽度（从大到小），放在第一个塔上：
// 初始放置盘子
- (void)initWithDiskPut {
NSInteger towerHeight = (SCREENHEIGHT - 150)/3 - 40;
NSInteger diskHeight = towerHeight / self.diskNumber;// 盘子高度
// 依次放置盘子
for (int i = 0; i < self.diskNumber; i++) {
NSInteger diskWeight = 230 - 30*i;// 盘子宽度
// 自定义的盘子模型类
OXDiskModel *disk = [[OXDiskModel alloc] initWithFrame:CGRectMake((SCREENWIDTH-diskWeight)/2, 140 + diskHeight*(self.diskNumber-i-1), diskWeight, diskHeight)];
disk.backgroundColor = [UIColor yellowColor];
disk.layer.borderColor = [[UIColor darkGrayColor] CGColor];
disk.layer.borderWidth = 1;
disk.index = self.diskNumber - i;
[self.view addSubview:disk];
[self.diskArray addObject:disk];
}
}动画解题
在绘制过程中我们充分利用了面向对象编程的思想。现在来到最后一个问题，把算法和动画结合起来。
算法还是那个算法，在之前的算法中，我们传递的参数只是简单的字符串来代替三个塔，盘子也只是用盘子编号来代替，这里我们就要用我们的塔对象和盘子对象来作为真正的参数传递了。
对于塔，我们直接传递塔对象；对于盘子，我们传参还是传盘子编号，但是我们用一个数组记录所有盘子，然后循环找到当前要移动的对应编号的盘子。
盘子的移动动画我们使用简单的UIView动画就可以实现了，关于UIView基础动画可以看这篇文章：传送门：iOS基础动画教程。
在动画block中，我们去改变盘子的center，也就是中心点的Y坐标，来达到移动的目的，如何计算出要移动到哪呢？从参数中我们可以知道要移动到哪个塔，根据塔的属性可以知道塔上现在有多少个盘子，那么就可以根据塔的坐标、塔上盘子的数量、每个盘子的高度来计算出这个盘子要移动到哪个坐标了。
UIView动画有一个completion block，用来在动画完成后执行一些操作，上面我们要用到塔上的盘子数量，那在移动完后我们一定也要更新每座塔的数量，移走的塔数量减一，移到的塔数量加一。
这里就可以体现把塔作为对象的好处了， 试想一下不这么做，我们如果要知道每座塔的坐标以及每座塔上的盘子数量，一定要用数组去记录，而且传参时我们只能像最开始一样传递塔名字符串，那还得根据这个字符串来判断改变数组中的第几个元素的塔数量，获取哪个塔坐标，这都增加了很多代码量。但是有了塔对象，我们可以直接作为参数传递，也可以直接获取盘子数量去修改，太方便了。
// 开始
- (void)start {
self.moveCount = 0;
[self hanoiWithDisk:self.diskNumber towers:@"A" :@"B" :@"C"];
NSLog(@">>移动了%ld次", self.moveCount);
}
// 移动算法
- (void)hanoiWithDisk:(NSInteger)diskNumber towers:(OXTowerView *)towerA :(OXTowerView *)towerB :(OXTowerView *)towerC {
if (diskNumber == 1) {// 只有一个盘子则直接从A塔移动到C塔
[self move:1 from:towerA to:towerC];
} else {
[self hanoiWithDisk:diskNumber-1 towers:towerA :towerC :towerB];// 递归把A塔上编号1~diskNumber-1的盘子移动到B塔，C塔辅助
[self move:diskNumber from:towerA to:towerC];// 把A塔上编号为diskNumber的盘子移动到C塔
[self hanoiWithDisk:diskNumber-1 towers:towerB :towerA :towerC];// 递归把B塔上编号1~diskNumber-1的盘子移动到C塔，A塔辅助
}
}
// 移动过程
- (void)move:(NSInteger)diskIndex from:(OXTowerView *)fromTower to:(OXTowerView *)toTower {
NSLog(@"第%ld次移动：把%ld号盘从%@移动到%@", ++self.moveCount, diskIndex, fromTower, toTower);
for (OXDiskModel *disk in self.diskArray) {
if (disk.index == diskIndex) {
[UIView animateWithDuration:1.0 animations:^{
// 计算改变盘子位置
} completion:^(BOOL finished) {
if (finished) {// 动画完成
// 更新塔上的盘子数量
fromTower.diskNumber--;
toTower.diskNumber++;
}
}];
}
}
}这里有一个有意思的点可以看一下移动算法中后面三个塔参数前面是没有文字的，只有一个冒号，OC支持定义方法时参数前不需要一定要有文字，只不过为了方便理解都会加一个参数说明。
到此，是不是问题都解决了？不是的，如果你直接这么写，运行后会发现所有动画都一起移动到塔C，根本没有过程！这是为什么？
因为算法运行得很快，而动画需要时间，这就导致还没开始动画，所有的算法都计算完了，最后只会把所有盘子一起移动到塔C，因为那就是算法最后算出来的目标位置。
这时我想到的第一个方法是用dispatch_semaphore_t来做为信号量，控制算法等待动画完毕后再进行，用法说明可以看这篇文章：传送门：iOS之利用GCD信号量控制并发网络请求，比如像下面这样：
// 移动过程
- (void)move:(NSInteger)diskIndex from:(OXTowerView *)fromTower to:(OXTowerView *)toTower {
dispatch_semaphore_t sema = dispatch_semaphore_create(0);// 初始化信号量为0
NSLog(@"第%ld次移动：把%ld号盘从%@移动到%@", ++self.moveCount, diskIndex, fromTower, toTower);
for (OXDiskModel *disk in self.diskArray) {
if (disk.index == diskIndex) {
[UIView animateWithDuration:1.0 animations:^{
// 计算改变盘子位置
} completion:^(BOOL finished) {
if (finished) {// 动画完成
// 更新塔上的盘子数量
fromTower.diskNumber--;
toTower.diskNumber++;
dispatch_semaphore_signal(sema);// 增加信号量，结束等待
}
}];
break;
}
}
dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);// 信号量若没增加，则一直等待，直到动画完成
}运行后会发现动画干脆都不动了，为什么？因为动画在主线程，信号量等待也在主线程，那就造成了“信号量等待信号才能继续往下进行<–>动画在主线程中被信号量卡主等待，无法进行，但是进行完了才能给出信号量”的循环等待。
这怎么解决？其实看上面的解释就能够想到办法了，把算法放到分线程去跑，动画放在主线程！这样信号量等待是让分线程等待，不会影响主线程，这样就不会阻塞，同时可以实现算法等待动画完毕后再进行的效果，完美：
// 开始移动
- (void)beginMove {
self.moveCount = 0;
WeakSelf
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{// 到分线程去处理算法
StrongSelf
if (strongSelf) {
[strongSelf hanoiWithDisk:strongSelf.diskNumber towers:[strongSelf.towerArray objectAtIndex:0] :[strongSelf.towerArray objectAtIndex:1] :[strongSelf.towerArray objectAtIndex:2]];
}
});
// NSLog(@">>移动了%ld次", self.moveCount);
}
// 移动算法
- (void)hanoiWithDisk:(NSInteger)diskNumber towers:(OXTowerView *)towerA :(OXTowerView *)towerB :(OXTowerView *)towerC {
if (diskNumber == 1) {// 只有一个盘子则直接从A塔移动到C塔
[self move:1 from:towerA to:towerC];
} else {
[self hanoiWithDisk:diskNumber-1 towers:towerA :towerC :towerB];// 递归把A塔上编号1~diskNumber-1的盘子移动到B塔，C塔辅助
[self move:diskNumber from:towerA to:towerC];// 把A塔上编号为diskNumber的盘子移动到C塔
[self hanoiWithDisk:diskNumber-1 towers:towerB :towerA :towerC];// 递归把B塔上编号1~diskNumber-1的盘子移动到C塔，A塔辅助
}
}
// 移动过程
- (void)move:(NSInteger)diskIndex from:(OXTowerView *)fromTower to:(OXTowerView *)toTower {
dispatch_semaphore_t sema = dispatch_semaphore_create(0);// 初始化信号量为0
NSLog(@"第%ld次移动：把%ld号盘从塔%@移动到塔%@", ++self.moveCount, diskIndex, fromTower.towerId, toTower.towerId);
for (OXDiskModel *disk in self.diskArray) {
if (disk.index == diskIndex) {
WeakSelf
dispatch_async(dispatch_get_main_queue(), ^{// 切回主线程进行移动动画
[UIView animateWithDuration:1.0 animations:^{
StrongSelf
if (strongSelf) {
// 改变盘子的位置
CGPoint diskCenter = disk.center;
NSInteger towerY = 10 + toTower.frame.origin.y;
NSInteger towerHeight = toTower.frame.size.height-15;
NSInteger diskHeight = towerHeight / strongSelf.diskNumber;// 每个盘子高度
NSInteger hasDiskHieght = diskHeight * toTower.diskNumber;// 已放置了的盘子高度
diskCenter.y = towerY + (towerHeight - hasDiskHieght) - diskHeight/2;
disk.center = diskCenter;
}
} completion:^(BOOL finished) {
if (finished) {// 动画完成
StrongSelf
if (strongSelf) {
// 改变fromTower的盘子数量
fromTower.diskNumber--;
// 改变toTower的盘子数量
toTower.diskNumber++;
dispatch_semaphore_signal(sema);// 增加信号量，结束等待
}
}
}];
});
break;
}
}
dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);// 信号量若没增加，则一直等待，直到动画完成
}这时候再运行就可以完美实现效果了:
结
为了解决阻塞的问题，还尝试过延迟执行、动画队列等方法，但都不如这个方法简单有效。
在做这个的过程中，用到了很多小技巧，也多次优化了代码，对于我自己来说代码越来越赏心悦目，实在是一次很好的学习训练的经验。
而且看着自己做的汉诺塔游戏自动动画解题很有意思不是嘛！
示例工程：https://github.com/Cloudox/OXHanoiDemo
