引

前段時間做了一道題香府，要求實現(xiàn)漢諾塔游戲的自動解題動畫：

image.png

漢諾塔游戲應(yīng)該都了解規(guī)則：

1致开、將盤子全部移動到塔C
2甲雅、每次只能移動一個圓盤解孙；
3、大盤不能疊在小盤上面抛人。

要求由用戶輸入盤子的數(shù)量弛姜，繪制盤子和塔，點擊開始后自動解題妖枚，并以動畫移動盤子的形式演示廷臼。

覺得還挺有意思的，而且在做的過程中也踩了一些坑，用了一些技巧和優(yōu)化荠商，因此記錄下來寂恬。

效果：

20170518105404247.gif

漢諾塔解法

這道題中漢諾塔的解法本身并不是難點。

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。

綜上所述腋腮，除了一個盤子的情況直接移動雀彼，其余都需要借助其他盤子的幫助，復(fù)雜情況雖然不一樣即寡，但是過程是遞歸不斷重復(fù)的徊哑。

遞歸代碼如下：

// 確定提交
- (void)submit {
    if ([self.numberField.text isEqualToString:@""]) {
        NSLog(@"未輸入內(nèi)容");
        UIAlertController *alertController = [UIAlertController alertControllerWithTitle:@"提示" message:@"您還未輸入層數(shù)!" 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);
}

三層盤子時：

image.png

四層盤子時：

image.png

可見算法是正確的莺丑，接下來就是實現(xiàn)繪制和動畫的問題。

繪制塔和盤子

解決了算法的問題墩蔓，下一步我們要繪制圖形了梢莽。

這里為了方便我決定全部用UIView來做，比如塔就是一橫一豎兩個UIView奸披，每個盤子都是一個UIView昏名。

為了方便給盤子編號，創(chuàng)建一個繼承自UIView的盤子類阵面，加上編號屬性：

#pragma mark - Disk Model
// 自定義的盤子模型轻局，在UIView基礎(chǔ)上加上編號屬性
@interface OXDiskModel : UIView
@property NSInteger index;
@end

@implementation OXDiskModel

@end

因為這個代碼很短洪鸭，沒必要新開一個文件，直接在繪制圖形的ViewController.m文件中加上這個代碼就可以實現(xiàn)了仑扑。

對于塔览爵，一開始我直接在界面上繪制三個塔的6條線，很簡單镇饮，但是在涉及到動畫的時候蜓竹，需要頻繁用到每個塔的位置以及塔上已有的盤子數(shù)量才能確定盤子移動到的位置，這就很麻煩储藐，而且不穩(wěn)定梅肤，代碼很復(fù)雜。

后來我改成把塔也抽象出來成一個塔類邑茄，在其類中繪制兩條線，并且加上塔名稱以及塔上盤子數(shù)量的屬性俊啼，這樣就可以直接調(diào)用了肺缕，在遞歸算法中，我們可以直接傳遞三個塔對象授帕，可以很方便地計算同木，減少了大量的代碼，代碼結(jié)構(gòu)也更加清晰跛十。

塔的繪制代碼和屬性就不寫出來了彤路，有單獨的類文件，可以直接在工程中看芥映，這里直說思想洲尊，對于一些適合抽離出來的對象，我們應(yīng)該盡可能抽象成對應(yīng)的類奈偏，將它的操作坞嘀、行為、屬性等放在類中寫惊来，可以極大地簡化代碼丽涩、使代碼結(jié)構(gòu)更清晰。

這樣裁蚁，我們就可以根據(jù)屏幕大小算出每個塔合適的大小矢渊，然后去創(chuàng)建三個塔對象，添加到界面上就好了枉证。

// 三座塔
- (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];
    }
}

然后根據(jù)輸入的盤子層數(shù)矮男，動態(tài)算出每個盤子合適的高度以及每個盤子的寬度（從大到小）刽严，放在第一個塔上：

// 初始放置盤子
- (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];
    }
}

動畫解題

在繪制過程中我們充分利用了面向?qū)ο缶幊痰乃枷搿昂灵，F(xiàn)在來到最后一個問題避凝，把算法和動畫結(jié)合起來。

算法還是那個算法眨补，在之前的算法中管削，我們傳遞的參數(shù)只是簡單的字符串來代替三個塔，盤子也只是用盤子編號來代替撑螺，這里我們就要用我們的塔對象和盤子對象來作為真正的參數(shù)傳遞了含思。

對于塔，我們直接傳遞塔對象甘晤；對于盤子含潘，我們傳參還是傳盤子編號，但是我們用一個數(shù)組記錄所有盤子线婚，然后循環(huán)找到當前要移動的對應(yīng)編號的盤子遏弱。

盤子的移動動畫我們使用簡單的UIView動畫就可以實現(xiàn)了，關(guān)于UIView基礎(chǔ)動畫可以看這篇文章：傳送門：iOS基礎(chǔ)動畫教程塞弊。

在動畫block中漱逸，我們?nèi)ジ淖儽P子的center，也就是中心點的Y坐標游沿，來達到移動的目的饰抒，如何計算出要移動到哪呢？從參數(shù)中我們可以知道要移動到哪個塔诀黍，根據(jù)塔的屬性可以知道塔上現(xiàn)在有多少個盤子袋坑，那么就可以根據(jù)塔的坐標、塔上盤子的數(shù)量眯勾、每個盤子的高度來計算出這個盤子要移動到哪個坐標了枣宫。

UIView動畫有一個completion block，用來在動畫完成后執(zhí)行一些操作吃环，上面我們要用到塔上的盤子數(shù)量镶柱，那在移動完后我們一定也要更新每座塔的數(shù)量，移走的塔數(shù)量減一模叙，移到的塔數(shù)量加一歇拆。

這里就可以體現(xiàn)把塔作為對象的好處了， 試想一下不這么做范咨，我們?nèi)绻烂孔淖鴺艘约懊孔系谋P子數(shù)量故觅，一定要用數(shù)組去記錄，而且傳參時我們只能像最開始一樣傳遞塔名字符串渠啊，那還得根據(jù)這個字符串來判斷改變數(shù)組中的第幾個元素的塔數(shù)量输吏，獲取哪個塔坐標，這都增加了很多代碼量替蛉。但是有了塔對象贯溅，我們可以直接作為參數(shù)傳遞拄氯，也可以直接獲取盤子數(shù)量去修改，太方便了它浅。

// 開始
- (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) {// 動畫完成
                    // 更新塔上的盤子數(shù)量
                    fromTower.diskNumber--;
                    toTower.diskNumber++;
                }
            }];
        }
    }
}

這里有一個有意思的點可以看一下移動算法中后面三個塔參數(shù)前面是沒有文字的姐霍，只有一個冒號鄙麦，OC支持定義方法時參數(shù)前不需要一定要有文字，只不過為了方便理解都會加一個參數(shù)說明镊折。

到此胯府，是不是問題都解決了？不是的恨胚，如果你直接這么寫骂因，運行后會發(fā)現(xiàn)所有動畫都一起移動到塔C，根本沒有過程赃泡！這是為什么侣签？

因為算法運行得很快，而動畫需要時間急迂，這就導致還沒開始動畫，所有的算法都計算完了蹦肴，最后只會把所有盤子一起移動到塔C僚碎，因為那就是算法最后算出來的目標位置。

這時我想到的第一個方法是用dispatch_semaphore_t來做為信號量阴幌，控制算法等待動畫完畢后再進行勺阐，用法說明可以看這篇文章：傳送門：iOS之利用GCD信號量控制并發(fā)網(wǎng)絡(luò)請求，比如像下面這樣：

// 移動過程
- (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) {// 動畫完成
                    // 更新塔上的盤子數(shù)量
                    fromTower.diskNumber--;
                    toTower.diskNumber++;
                    dispatch_semaphore_signal(sema);// 增加信號量矛双，結(jié)束等待
                }
            }];
            break;
        }
    }
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);// 信號量若沒增加渊抽，則一直等待，直到動畫完成
}

運行后會發(fā)現(xiàn)動畫干脆都不動了议忽，為什么懒闷？因為動畫在主線程，信號量等待也在主線程栈幸，那就造成了“信號量等待信號才能繼續(xù)往下進行<-->動畫在主線程中被信號量卡主等待愤估，無法進行，但是進行完了才能給出信號量”的循環(huán)等待速址。

這怎么解決玩焰？其實看上面的解釋就能夠想到辦法了，把算法放到分線程去跑芍锚，動畫放在主線程昔园！這樣信號量等待是讓分線程等待蔓榄，不會影響主線程，這樣就不會阻塞默刚，同時可以實現(xiàn)算法等待動畫完畢后再進行的效果甥郑，完美：

// 開始移動
- (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的盤子數(shù)量
                            fromTower.diskNumber--;
                            
                            // 改變toTower的盤子數(shù)量
                            toTower.diskNumber++;
                            
                            dispatch_semaphore_signal(sema);// 增加信號量壹若，結(jié)束等待
                        }
                    }
                }];
            });
            
            
            break;
        }
    }
    
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);// 信號量若沒增加，則一直等待皂冰，直到動畫完成
}

這時候再運行就可以完美實現(xiàn)效果了:

20170518105404247.gif

結(jié)

為了解決阻塞的問題店展，還嘗試過延遲執(zhí)行、動畫隊列等方法秃流，但都不如這個方法簡單有效赂蕴。

在做這個的過程中，用到了很多小技巧舶胀，也多次優(yōu)化了代碼概说，對于我自己來說代碼越來越賞心悅目，實在是一次很好的學習訓練的經(jīng)驗嚣伐。

而且看著自己做的漢諾塔游戲自動動畫解題很有意思不是嘛糖赔！

示例工程：https://github.com/Cloudox/OXHanoiDemo

查看作者首頁