寫在前面
上一篇文章我寫了一個簡單的iOS 拼圖游戲（童年的記憶——拼圖游戲）器虾，現(xiàn)在我要讓這個游戲聰明起來，幫助你來完成拼圖是目。寫這篇文章的時候正好在看《最強大腦》，節(jié)目里的第一個PK就是復(fù)原這種拼圖（非圖而是數(shù)字，數(shù)字華容道）窿春，節(jié)目營造了非常緊張的氣氛佣耐，其實這種拼圖復(fù)原算是比較簡單的政勃。
不再前戲，直接進(jìn)入正題：游戲源碼點這里（拼圖游戲）晰赞，您可以從這份源碼中g(shù)et到的技術(shù)點：
游戲效果：> 設(shè)置代理類為控制器瘦身
> A*算法（含借助完全二叉樹實現(xiàn)優(yōu)先隊列）
> GCD信號量控制數(shù)組遍歷流量
> 定時器+GCD信號量實現(xiàn)數(shù)組遍歷的暫停稼病、繼續(xù)
基本思路
那么怎樣讓原本屌絲氣質(zhì)的游戲具備人工智能（AI），自動還原拼圖掖鱼，從此華麗變身高大上呢然走？
- 方案一：
我們很容易想到的方法，按打亂的順序逆序還原戏挡。此方案的打亂順序即將原本有序的圖片按照游戲規(guī)則移動數(shù)次芍瑞，從而實現(xiàn)打亂效果。但是我想你們已經(jīng)發(fā)現(xiàn)了一個問題褐墅，我所設(shè)計的游戲打亂后空位設(shè)置在右下角拆檬，我們還需要想辦法將空位移動到右下角的目標(biāo)位置。 - 方案二：
不關(guān)心打亂的過程妥凳，依次將編號0竟贯、1、2... 回歸到正確位置逝钥，逐漸縮小亂序圖區(qū)域屑那。不過往往最后兩行的幾塊需要稍微調(diào)整下策略。 - 方案三：
不關(guān)心打亂的過程艘款，從打亂后的狀態(tài)開始持际，根據(jù)一定約束條件，對下一步的多種可能性進(jìn)行搜索判斷哗咆，逐步演進(jìn)蜘欲，從而找出復(fù)原步驟。我選用的是A*搜索算法晌柬。
方案解讀
* 方案一
方案一實現(xiàn)起來較為簡單姥份，假定我們現(xiàn)在已經(jīng)將有序的（處于復(fù)原態(tài)）拼圖移動了數(shù)次，也就是拼圖打亂了（如下圖左）年碘。接下來將空位移動到右下角澈歉。
顯然，移動的策略有很多種盛泡，我們只需要一種闷祥，比如這樣：空位先逐步橫向移動到最右側(cè)，再逐步縱向移動到最下側(cè)。你看凯砍，可以啦箱硕。（上圖右邊）
算法分解：
1。求出當(dāng)前空位所在行悟衩、列剧罩。
2。當(dāng)前空位與其右側(cè)格子換位座泳。
3惠昔。重復(fù)1、2挑势，直到空位位于最右側(cè)（最大列）镇防。
4。當(dāng)前空位與其下側(cè)格子換位潮饱。
5来氧。重復(fù)1、4香拉，直到空位位于最下側(cè)（最大行）啦扬。
如此，我們已經(jīng)完成了打亂步驟凫碌。當(dāng)然扑毡，我們移動的每一步都需要記錄在案，以便按照記錄逆步驟進(jìn)行還原盛险。注：我提供的游戲源碼中并沒有包含該方案（方案一）的代碼實現(xiàn)瞄摊，感興趣的讀者可以自行實現(xiàn)。
* 方案二
對于方案二枉层，寫這篇文章的時候才臨時考慮加入這個方案泉褐〈托矗基本思路上文中其實已經(jīng)闡明鸟蜡，暫不展開討論。
* 方案三
對于方案三挺邀，容易聯(lián)想到嘗試每種步驟可能性揉忘，最終選出可以復(fù)原的步驟鏈。
上圖即表示每一個狀態(tài)衍生出的可能路徑端铛，排除了重復(fù)的狀態(tài)泣矛。對于這種暴力搜索算法，性能是較低的（關(guān)于搜索算法禾蚕，我此前的文章有介紹過最短路徑的兩個經(jīng)典算法 點我）您朽。拼圖為4階方陣時，拼圖狀態(tài)數(shù)(4*4)! = 20922789888000，廣搜算法已基本不能搜出結(jié)果哗总，直到爆內(nèi)存几颜。拼圖為5階方陣時，狀態(tài)數(shù)(5*5)! = 1.551121004333098e25讯屈，10的25次方蛋哭。先別著急，我們可以選擇性能較高的A*算法為拼圖游戲助力涮母。
- A*算法簡介：
A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法谆趾，也是解決許多搜索問題的有效算法。它并不是搜索每一種可能的狀態(tài)叛本，而是有選擇地啟發(fā)式搜索沪蓬，每一次在多個狀態(tài)中選擇可能最接近目標(biāo)狀態(tài)的一個。依此層層搜索来候，顯然相比暴力搜索怜跑，少走了很多的彎路。
本文并不打算深入描述該算法技術(shù)細(xì)節(jié)吠勘。推薦閱讀A*算法詳解性芬。
對于該游戲，對每一個狀態(tài)到目標(biāo)狀態(tài)的“距離”進(jìn)行估算剧防，將每一個方塊偏離它正確位置的距離進(jìn)行累加植锉，取偏離值最小者擇優(yōu)錄取。圖示說明：
當(dāng)前狀態(tài)估價（本例中也就是曼哈頓距離）計算方式：
4距離它正確的位置也就是上圖中7的位置：橫向1+縱向1=2峭拘；
1距離它正確的位置0俊庇；
3距離它正確的位置也就是上圖中2的位置：橫向2+縱向1=3；
2距離它正確的位置也就是上圖中3的位置：橫向2+縱向1=3鸡挠；
7距離它正確的位置也就是上圖中5的位置：橫向0+縱向1=1辉饱；
0距離它正確的位置也就是上圖中4的位置：橫向2+縱向1=3；
6距離它正確的位置0拣展；
我們給予空格位特權(quán)彭沼，不對它考核。
5距離它正確的位置也就是上圖中0的位置：橫向0+縱向1=1备埃；
然后將上述距離值累加姓惑。
當(dāng)然實際還可以在這個基礎(chǔ)上對估價進(jìn)行調(diào)整，比如乘以一定系數(shù)按脚。
性能優(yōu)化（TODO）
暫時想到了以下優(yōu)化方向：
- 當(dāng)前源碼每次UICollectionView數(shù)據(jù)源刷新時于毙，為全局刷新方式，實際除了重置游戲辅搬，每次都只是2個格子在變化唯沮。可以修改為局部刷新。
- 當(dāng)前源碼為搜索完成后再進(jìn)行拼圖復(fù)原介蛉。需要耗費一定的時間夯缺。嘗試邊搜索邊拼圖的方式（邊“生產(chǎn)”邊“消費”）。
- 根據(jù)方格數(shù)的多少（難易程度）靈活調(diào)整A*算法的估價甘耿，意在優(yōu)化游戲還原步數(shù)踊兜。
鳴謝
鑒于A* 算法是個通用的算法，筆者就不重復(fù)造輪子了佳恬。本文配套源碼中直接套用了《拼圖游戲和它的AI算法》作者封裝的A*算法捏境，在此對原作者表示感謝。
