錢麗丹

摘 要： 以數(shù)獨(dú)游戲?yàn)榍腥朦c(diǎn)研究IOS平臺(tái)下的游戲開發(fā)技術(shù)。介紹了數(shù)獨(dú)游戲的起源與游戲規(guī)則，對(duì)系統(tǒng)進(jìn)行功能模塊劃分，介紹了系統(tǒng)使用到的關(guān)鍵技術(shù)如Cocos2D游戲框架、舞蹈鏈算法等，給出了系統(tǒng)運(yùn)行界面。該游戲可以在任何IOS移動(dòng)終端上運(yùn)行，界面美觀，性能穩(wěn)定。

關(guān)鍵詞： IOS； 數(shù)獨(dú)游戲； Cocos2D游戲框架； 舞蹈鏈算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）04-58-03

Development of Sudoku game for IOS

Qian Lidan

（Department of Information & Technology， ZheJiang Economic & Trade Polytechnic， Hangzhou， Zhejiang 310018， China）

Abstract： Taking Sudoku game as an entry point， the game development technology on IOS platform is studied. The origin and the play rules of the game are introduced in this paper， the system function module is divided and some key technologies such as Cocos2D， Dancing Links algorithm etc. are introduced， and the system operation interface are given. The game can be run on any IOS mobile terminal， with beautiful interface and stable performance.

Key words： IOS； Sudoku game； Cocos2D game framework； Dancing Links algorithm

0 引言

伴隨著智能手機(jī)普及和4G網(wǎng)絡(luò)的發(fā)展，中國的手機(jī)游戲市場得到了迅猛發(fā)展，尤其近四年以來發(fā)展更為迅速。在2011年整個(gè)中國手機(jī)游戲手場收入不過62.4億元，但是在2015年則達(dá)到了416億[1]。2014年手機(jī)游戲銷售收入首次超越網(wǎng)頁游戲，手機(jī)游戲成為了網(wǎng)絡(luò)游戲的主力軍。

IOS作為主流的開發(fā)平臺(tái)，與Android相比，IOS平臺(tái)硬件統(tǒng)一，這使得程序開發(fā)人員需要考慮的兼容性問題變得相對(duì)容易，維護(hù)及修復(fù)成本也較低。IOS游戲開發(fā)收入是Android游戲開發(fā)收入的6倍，IOS已經(jīng)成為了手機(jī)游戲開發(fā)的首選平臺(tái)。本文以數(shù)獨(dú)游戲?yàn)榍腥朦c(diǎn)，研究IOS平臺(tái)下的游戲開發(fā)技術(shù)。

1 數(shù)獨(dú)游戲分析與設(shè)計(jì)

1.1 游戲介紹

數(shù)獨(dú)[2]最早起源于18世紀(jì)初瑞士數(shù)學(xué)家歐拉等人研究的拉丁方陣，經(jīng)歷了一系列的演變，從早期的“拉丁方塊”、“數(shù)字拼圖”到現(xiàn)在的“數(shù)獨(dú)”，游戲規(guī)則逐步確定。正式的數(shù)獨(dú)游戲最早出現(xiàn)在20世紀(jì)70年代的美國，后來逐漸被介紹到日本、英國、中國等，在全球范圍內(nèi)確立了謎題領(lǐng)域的世界地位。

數(shù)獨(dú)盤面是個(gè)九宮，每一宮又分為九個(gè)小格，在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字，使1-9每個(gè)數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次。這游戲全面考驗(yàn)玩家觀察能力和推理能力，雖然玩法簡單，但數(shù)字排列方式卻千變?nèi)f化，使得數(shù)獨(dú)成為了訓(xùn)練頭腦的絕佳方式。

1.2 系統(tǒng)功能模塊劃分

游戲共分為8個(gè)功能模塊：游戲主體模塊、解題器模塊、謎題自動(dòng)生成器模塊、關(guān)卡編輯器模塊、游戲菜單模塊、關(guān)于游戲模塊、背景音效模塊和游戲分享模塊。系統(tǒng)功能模塊劃分如圖1所示。

[數(shù)獨(dú)游戲][謎題自動(dòng)生成器][游戲主體][解題器][關(guān)于游戲][關(guān)卡編輯器][游戲菜單][游戲分享][背景音效]

圖1 系統(tǒng)功能模塊

在系統(tǒng)模塊劃分中，游戲主體模塊、解題器模塊、謎題自動(dòng)生成器模塊、關(guān)卡編輯器模塊這四個(gè)模塊的設(shè)計(jì)相當(dāng)重要。游戲主體模塊用于實(shí)現(xiàn)游戲界面的生成，接收用戶的輸入，并根據(jù)用戶輸入，通過調(diào)用解題器模塊，判斷用戶輸入的正誤；解題器模塊采用了無論在時(shí)間效率還是空間效率都有著明顯優(yōu)勢的舞蹈鏈算法實(shí)現(xiàn)；謎題自動(dòng)生成器模塊是為了使游戲更加生動(dòng)有趣，系統(tǒng)已經(jīng)內(nèi)置四個(gè)等級(jí)（初試身手、漸入佳境、龍?zhí)痘⒀?、巔峰時(shí)刻）共800套謎題，對(duì)于希望自定義游戲內(nèi)容的用戶，可以通過謎題自動(dòng)生成器模塊建立自己的謎題庫；關(guān)卡編輯器模塊使得用戶在完成低級(jí)別的謎題后，才可以繼續(xù)挑戰(zhàn)更高等級(jí)的謎題，關(guān)卡編輯器是基于HTML和javascript寫的網(wǎng)頁版工具；游戲菜單模塊在主菜單里提供了一系列常用的按鈕，方便用戶選擇相應(yīng)的功能；關(guān)于游戲模塊為用戶提供了游戲說明，幫助用戶快速掌握游戲使用方法；為了在解題時(shí)增加樂趣，用戶可以選擇開啟游戲背景音效模塊；游戲分享模塊用于通過短信或郵件的方式向其他用戶分享該款游戲。

2 系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)

系統(tǒng)采用多種技術(shù)實(shí)現(xiàn)數(shù)獨(dú)游戲的各個(gè)功能模塊。其中，開發(fā)硬件環(huán)境為MacBook Pro，測試環(huán)境為iphone simulator，開發(fā)的軟件環(huán)境為Mac OS 10.11+Xcode 7.1+ Cocos2D-iphone，編程語言采用Objective-C，數(shù)據(jù)庫采用SQLite。在解題方面，采用了舞蹈鏈算法，解題效率極高。

2.1 Objective-C

系統(tǒng)開發(fā)采用Objective-C。Objective-C[3]是非常實(shí)用的編程語言，它是一個(gè)用C寫成的很小的運(yùn)行庫，是一種擴(kuò)充了C的面向?qū)ο蟮木幊陶Z言。Objective-C可以在支持GCC的系統(tǒng)上編譯并運(yùn)行。利用Objective-C可以編寫如IOS操作系統(tǒng)、IOS應(yīng)用程序等一系列程序。

Objective-C不支持多重繼承，且不支持運(yùn)算符重載。Objective-C使用動(dòng)態(tài)運(yùn)行時(shí)類型（dynamicaly typed），所有的方法都是函數(shù)調(diào)用（包括系統(tǒng)調(diào)用），它的類庫比C++更容易操作，Objective-C在運(yùn)行時(shí)可以允許根據(jù)字符串名字來訪問方法和類，還可以動(dòng)態(tài)連接和添加類。

2.2 Cocos 2D開發(fā)框架

Cocos2D[4]是用于構(gòu)建iPhone游戲的開源框架，是基于iPhone核心SDK之上架構(gòu)而成，用于構(gòu)建2D游戲、演示程序和其他圖形界面交互應(yīng)用等。它可以讓程序員在創(chuàng)建自己的iPhone游戲時(shí)節(jié)省很多時(shí)間。它具有很多功能，比如sprite（精靈）扶持、非?？岬膱D形效果、動(dòng)畫效果、物理庫、音頻引擎等。

Cocos2D也擁有幾個(gè)主要版本，包括Cocos2D-

iPhone、Cocos2D-X。在系統(tǒng)開發(fā)過程中采用Cocos2D-iPhone版本的框架。雖然Cocos2D-X是一個(gè)跨平臺(tái)的框架，開發(fā)的應(yīng)用程序可以適用于不同的平臺(tái)，但是在實(shí)際開發(fā)過程中，需要處理很多與平臺(tái)相關(guān)的問題，而Cocos2D-iPhone版本僅針對(duì)IOS平臺(tái)，以O(shè)bjective-C為編程語言，和蘋果的硬件系統(tǒng)結(jié)合非常好，因此它是開發(fā)IOS游戲的不二選擇。

2.3 Xcode開發(fā)工具

Xcode[5]是運(yùn)行在操作系統(tǒng)Mac OS X上的集成開發(fā)工具（IDE），由蘋果公司開發(fā)。Xcode是開發(fā)Mac OS X和iOS應(yīng)用程序的最快捷的方式。Xcode具有統(tǒng)一的用戶界面設(shè)計(jì)，編碼、測試、調(diào)試都在一個(gè)簡單的窗口內(nèi)完成。

Xcode支持多種開發(fā)語言，如C、C++、Objective-C、Java、Python等，Xcode由蘋果公司開發(fā)，是一款免費(fèi)的開發(fā)工具，與Mac OS X一起發(fā)行，可以在蘋果公司官方的網(wǎng)站下載，目前最新版本是Xcode 7.1。

2.4 舞蹈鏈算法

舞蹈鏈算法[6]（Dancing Links）的發(fā)明者是Don Knuth，利用該算法可以使很多搜索問題得到優(yōu)化，舞蹈鏈算法不僅可以解決精確覆蓋問題，還可用于重復(fù)覆蓋問題。Dancing Links用的數(shù)據(jù)結(jié)構(gòu)是交叉十字循環(huán)雙向鏈，Dancing Links中每個(gè)元素有六個(gè)分量，分別為：Left指向左邊的元素、Right指向右邊的元素、Up指向上邊的元素、Down指向下邊的元素、Col指向列標(biāo)元素、Row指示當(dāng)前元素所在的行。

利用舞蹈鏈算法求解數(shù)獨(dú)問題需要下列四個(gè)步驟：①把數(shù)獨(dú)問題轉(zhuǎn)換為精確覆蓋問題；②設(shè)計(jì)出數(shù)據(jù)矩陣；③用舞蹈鏈算法求解該精確覆蓋問題；④把該精確覆蓋問題的解轉(zhuǎn)換為數(shù)獨(dú)的解。

與此相對(duì)應(yīng)，也可以利用暴力破解法解決數(shù)獨(dú)問題，暴力破解法基本思想是：根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完畢。通過測算，舞蹈鏈算法無論在時(shí)間效率還是空間效率方面都優(yōu)于暴力破解法，因此它是最適合用于解決數(shù)獨(dú)問題的算法。

3 系統(tǒng)運(yùn)行界面

本應(yīng)用安裝完成后，包括了開始游戲、謎題生成器、快速解題器、背景音效開啟、排行榜與成就、關(guān)于游戲、游戲分享、獲取更多游戲共八部分系統(tǒng)界面，其主界面如圖2所示。當(dāng)點(diǎn)擊開始游戲后進(jìn)入到游戲難度等級(jí)選擇界面，難度等級(jí)共劃分成四類（初試身手、漸入佳境、龍?zhí)痘⒀?、巔峰時(shí)刻），用戶從最低難度等級(jí)的謎題開始。每一類難度等級(jí)有200題，系統(tǒng)共內(nèi)置800個(gè)謎題，每題下方顯示答題時(shí)長，謎題關(guān)卡界面如圖3所示，對(duì)于尚未完成的謎題則顯示為灰色。選擇一個(gè)謎題進(jìn)入游戲界面，游戲界面如圖4所示，游戲界面以咖啡色為主色調(diào)，包含了9行9列共81個(gè)格子，大部分區(qū)域已經(jīng)填寫好數(shù)字，用戶只需選擇空白區(qū)域，并填入合適的數(shù)字即可，用戶也可以利用右上角的重置按鈕，將游戲恢復(fù)到原始狀態(tài)。用戶的狀態(tài)數(shù)據(jù)保存在本地?cái)?shù)據(jù)庫SQLite中。

4 結(jié)束語

數(shù)獨(dú)游戲看似簡單，但由于數(shù)字排列可以做到千變?nèi)f化，因此成了考驗(yàn)玩家耐心與邏輯推理能力的一款益智類游戲，深受大眾喜愛。該游戲基于IOS平臺(tái)，可以運(yùn)行在任意的IOS移動(dòng)終端上，其界面美觀，性能穩(wěn)定。隨著智能手機(jī)的普及以及4G時(shí)代的全面開啟，這一類益智游戲?qū)⒕哂懈蟮氖袌隹臻g。

參考文獻(xiàn)（References）：

[1] 天極網(wǎng).2015手游市場報(bào)告：中國成全球最大市場[EB/OL].

http：//gameonline.yesky.com/482/95650482.shtml，2015.9.

[2] 王陽，褚治廣.基于Android 平臺(tái)的數(shù)獨(dú)游戲設(shè)計(jì)[J].遼寧工

業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013.8.

[3] 楊正洪，鄭齊心等.IOS編程揭秘——Objective-C程序設(shè)計(jì)

入門[M].清華大學(xué)出版社，2013.

[4] 劉杰逾.基于IOS平臺(tái)的一款游戲設(shè)計(jì)與實(shí)現(xiàn)[D]. 電子科技

大學(xué)，2012.5.

[5] 林冀，范俊等.Objective-C程序設(shè)計(jì)（第四版）[M].電子工業(yè)

出版社，2012.

[6] 萬倉一黍博客園.算法實(shí)踐——舞蹈鏈（Dancing Links）算法

求解數(shù)獨(dú)[EB/OL].http：//www.cnblogs.com/grenet/p/3163550.html，2013.7.