【正文】 有哪些優(yōu)缺點(diǎn)，如何實(shí)現(xiàn)?？梢钥闯觯捎诓恍枰獙ν瑫r(shí)對4個方向上所有空閑格子進(jìn)行廣度優(yōu)先搜索操作，第三步的時(shí)間復(fù)雜度應(yīng)該低于書中所給出的算法。如圖214所示，在這一步我們需要把搜索方向在“向上”和“向左”兩個方向上擴(kuò)展，所獲得的路徑分別用紅色框和粉色框表示，這個動作類似于把藍(lán)色框向上和向左拉伸。首先我們用指定方法在藍(lán)色矩形內(nèi)部進(jìn)行路徑查找，但是限制只在“向右”和“向下”兩個方向上進(jìn)行操作。這兩個結(jié)構(gòu)具體的功能后面用到的時(shí)候會詳細(xì)介紹。為了加速程序運(yùn)行，這里還引入了圖215所示的兩個輔助數(shù)據(jù)結(jié)構(gòu)，其中每一個方塊中都帶有一個二進(jìn)制位，用來表示在該位置上的格子是否是空格子，0代表是空格子，1代表有圖形存在。我們可以用上面的方法分別來測試這兩條路徑上是否有障礙存在，如果沒有障礙則作為最短路徑返回，否則就要進(jìn)行第三步。第二步，查找二者之間是否存在轉(zhuǎn)彎一次的路徑。如果val=0則說明兩個圖形間存在直線路徑，否則說明二者之間不存在直線路徑。因?yàn)閮蓚€圖形同在第二列上，于是我們?nèi)D215左邊結(jié)構(gòu)的第二列變量C2（這里假設(shè)是一個8位的Byte變量），然后做val=C2amp。但如果二者在一條直線上的話，還需要判斷他們之間是否有障礙物存在。圖214首先，應(yīng)該判斷是否存在圖形1到圖形2之間的直線路徑。圖213以圖214為例，我們的目標(biāo)是找到圖形1和圖形2之間的最短路徑，我們從圖形1出發(fā)進(jìn)行查找動作。若找到則返回結(jié)果，若還未找到則說明兩個圖形之間不存在不超過3個彎的路徑。否則，記錄下所有這四個方向上的空白格子，并在每一個空白格子的其他3個方向上進(jìn)行直線搜索。具體過程如圖 213所示：目標(biāo)是要找到從左上角的圓形圖形（設(shè)為圖形1）到右下角的圓形圖形（設(shè)為圖形2）之間不超過3個彎的最短路徑。false elsetrue if( B 在S中) T中的所有元素加入到S中 將所有與e能直線連通的點(diǎn)加入到集合T中 for( S 中每個元素e ) crossNum 3 )While( B 不在S 中amp。//用于記錄當(dāng)前搜索到節(jié)點(diǎn)的最大轉(zhuǎn)角數(shù)crossNum = 0 。 //臨時(shí)存儲搜索到的點(diǎn)Set picture T 。 Match( Picture A，Picture B ){否則A,B不能相連模仿圖論中廣度優(yōu)先搜索的算法，可以寫出以轉(zhuǎn)角為基準(zhǔn)的廣度優(yōu)先搜索的偽代碼如下（實(shí)際編程實(shí)現(xiàn)這一算法時(shí)可以采取優(yōu)化措施，不一定要搜索出所有與A轉(zhuǎn)角不超過2的點(diǎn)。采用廣度優(yōu)先搜索算法可以方便的實(shí)現(xiàn)這一構(gòu)想。：這種算法參考《編程之美》這種算法的動機(jī)：若能將所有與圖片A經(jīng)過不多于2個轉(zhuǎn)角的路徑相連的圖片找出來，加入一個集合S中。為了判斷A，B能否通過2個轉(zhuǎn)角連通，則從A開始在垂直方向上下掃描，并判斷經(jīng)過的點(diǎn)能否與B點(diǎn)經(jīng)過1個轉(zhuǎn)角連通。顯然C點(diǎn)能與B點(diǎn)經(jīng)1個轉(zhuǎn)角連通，故A，B能經(jīng)2個轉(zhuǎn)角連通。水平掃描。若能找到這樣一個C點(diǎn)，那么A與B就可以經(jīng)過有兩個轉(zhuǎn)角的路徑連通 。（紅色塊為欲消除塊，黑色代表其他阻攔塊，圓圈代表折點(diǎn)）如圖22圖22c) 兩個轉(zhuǎn)角連通： 判斷圖片A與圖片B能否經(jīng)過有兩個轉(zhuǎn)角的路徑連通實(shí)質(zhì)上可以轉(zhuǎn)化為判斷能否找到一個點(diǎn)C，這個C點(diǎn)與A可以直線連通，且C與B可以通過有一個轉(zhuǎn)角的路徑連通。a) 0轉(zhuǎn)角連通（直線連通）：兩個圖片的縱坐標(biāo)或橫坐標(biāo)相等，且兩者連線間沒有其他圖案阻隔。若這樣的圖片C存在，那么A與B就可以通過一條有N個轉(zhuǎn)角的路徑相連。，算法設(shè)計(jì)合理、思路清晰，涵蓋全部情況，采用遞歸的方式便于游戲編碼的實(shí)現(xiàn)。，游戲在開始后，背景音樂就進(jìn)行播放，當(dāng)鼠標(biāo)點(diǎn)擊圖片的時(shí)候，配對的點(diǎn)擊音樂也進(jìn)行播放，用于提示。，當(dāng)玩家無思路的時(shí)候，可以通過該功能，解決玩家的困惑。其他的問題均是圍繞這兩個問題產(chǎn)生的，由此可以這兩個問題的重要性以及良好算法設(shè)計(jì)的必要性。，這是連連看中最重要和最基礎(chǔ)的部分，我們主要采用分類判別的方法，這其實(shí)是一種遞歸的算法，把復(fù)雜的問題按照層次剝離出來，每次簡化一個步驟，就是遞歸的實(shí)現(xiàn)過程，我們將連連看圖片的位置歸類，總結(jié)出3個類別，即通過0,1,2個轉(zhuǎn)角連接，0個轉(zhuǎn)角是直連的方式，是遞歸的第一步，1個轉(zhuǎn)角的形式可以轉(zhuǎn)化為兩次直連的方式判斷，2個轉(zhuǎn)角同樣可以轉(zhuǎn)化為1次1個轉(zhuǎn)角，1次0個轉(zhuǎn)角的判斷。 游戲設(shè)計(jì)需要使用的算法針對游戲中最核心的兩個問題，1連連看游戲中隨機(jī)圖片的生成且每種圖片必須為偶數(shù)個，2圖片是否相同且圖片之間路徑的判斷，我們需要使用合適的算法來解決這兩個棘手的問題。 開始、重新開始、退出開始，重新開始，退出等按鈕實(shí)現(xiàn)相應(yīng)的游戲控制。 得分記錄、難度為了提高玩家的游戲的積極性，以及為了保證游戲的完整性，游戲?qū)⒔y(tǒng)計(jì)玩家的得分情況，消除一對圖片，就會得到相應(yīng)的分?jǐn)?shù)，以數(shù)據(jù)反應(yīng)玩家的游戲完成進(jìn)展。 提示功能當(dāng)玩家陷入困境，不知道怎么消除圖片，繼續(xù)游戲時(shí)，提示按鈕可以幫助他成功消除當(dāng)前的圖片，但是提示的次數(shù)有限，用完不再生效。 背景音樂的添加只要打開游戲，游戲的背景音樂就緩緩的流露出來，滋潤心田，選擇相應(yīng)的按鈕后，還會有提示音，成功連線消除圖片后能播放消除的提示音。 游戲規(guī)則 連連看游戲規(guī)則簡單，就是在游戲界面中找到兩個相同的圖片，用不超過3根直線能夠連接起來，就可以成功消除圖片，得到分?jǐn)?shù)，獲得時(shí)間獎勵，在規(guī)定時(shí)間內(nèi)將圖片全部消除，便獲得勝利。2008年，隨著社交網(wǎng)絡(luò)的普及和開放平臺的興起，“連連看”被引入了社交網(wǎng)絡(luò)。隨著Flash應(yīng)用的流行，網(wǎng)上出現(xiàn)了多種在線Flash版本“連連看”。這其中，顧方編寫的“阿達(dá)連連看”以其精良的制作廣受好評，這也成為顧方“阿達(dá)系列軟件”的核心產(chǎn)品?！斑B連看”的發(fā)展經(jīng)歷了從桌面游戲、在線游戲、社交游戲三個過程。連連看游戲設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)目錄摘 要 IABSTRACT II目錄 11. 緒 論 1 游戲簡介 1 游戲背景 1 游戲規(guī)則 1 游戲功能 1 美觀大氣的界面 1 背景音樂的添加 1 獎勵時(shí)間的設(shè)置 1 提示功能 1 僵局的重置 1 得分記錄、難度 2 開始、重新開始、退出 2 游戲設(shè)計(jì)的主要工作 2 游戲設(shè)計(jì)需要解決的問題 2 游戲設(shè)計(jì)需要使用的算法 2 游戲設(shè)計(jì)創(chuàng)新點(diǎn) 22. 系統(tǒng)分析 4 技術(shù)可行性分析 4 算法分析 4 開發(fā)語言分析 12 開發(fā)平臺分析 14 需求分析 16 環(huán)境分析 16 16 17 173. 游戲概要設(shè)計(jì) 18 任務(wù)概述 18 目標(biāo) 18 需求概述 18 總體設(shè)計(jì) 18 處理流程 18 系統(tǒng)結(jié)構(gòu)圖 18 游戲界面模塊設(shè)計(jì) 19 圖片的隨機(jī)生成 19 圖片消除路徑判斷 19 背景音樂的模塊 214. 詳細(xì)設(shè)計(jì) 23 視圖層設(shè)計(jì) 23 界面效果圖，如圖41 23 思路 23 邏輯層設(shè)計(jì) 23 圖片偶數(shù)對存放以及隨機(jī)生成 23 圖片消除路徑判斷詳細(xì)設(shè)計(jì) 26 其他控件的設(shè)計(jì)實(shí)現(xiàn) 31 重排按鈕實(shí)現(xiàn) 31 提示按鈕實(shí)現(xiàn) 32 獎勵時(shí)間和進(jìn)度條的邏輯實(shí)現(xiàn) 34 音樂模塊實(shí)現(xiàn) 365. 游戲測試 38 軟件測試 38 軟件測試簡介 38 測試方法 38 測試步驟 38 連連看游戲系統(tǒng)測試 39 游戲系統(tǒng)性能分析 39結(jié)論 40致謝 41參考文獻(xiàn) 42外文原文 43中文翻譯 49 1. 緒 論 游戲簡介 游戲背景連連看游戲是游戲中經(jīng)典中的經(jīng)典，曾經(jīng)風(fēng)靡網(wǎng)絡(luò)，無論是單機(jī)版的還是網(wǎng)絡(luò)對戰(zhàn)的，它以簡單，容易上手，圖片新穎的特點(diǎn)獲得了大量的粉絲，它是一款經(jīng)久不衰的休閑小游戲，適合閑來無事的大眾，以供消遣。游戲“連連看”顧名思義就是找出相關(guān)聯(lián)的東西，這個連連看在網(wǎng)上基本是用在小游戲中，就是找出相同的兩樣?xùn)|西，在一定的規(guī)則之內(nèi)可以做為相關(guān)聯(lián)處理。 游戲“連連看”是源自臺灣的桌面小游戲，自從流入大陸以來風(fēng)靡一時(shí)，也吸引眾多程序員開發(fā)出多種版本的“連連看”。并于2004年，取得了國家版權(quán)局的計(jì)算機(jī)軟件著作權(quán)登記證書。如“水晶連連看”、“果蔬連連看”等，流行的“水晶連連看”以華麗界面吸引了一大批的女性玩家?！斑B連看”與個人空間相結(jié)合，被快速的傳播，成為一款熱門的社交游戲，其中以開發(fā)者Jonevey在Manyou開放平臺上推出的“寵物連連看”最為流行。 游戲功能 美觀大氣的界面本連連看游戲采用藍(lán)色背景作為主色調(diào)，界面簡潔大方，按鈕及提示框排布合理，便于玩家的操作。 獎勵時(shí)間的設(shè)置玩家成功消除一對圖片后，對應(yīng)的時(shí)間進(jìn)度條就會增加一定的獎勵時(shí)間，來鼓勵玩家消除。 僵局的重置由于游戲的圖片生成是隨機(jī)的，因此，在消除到一定階段的時(shí)候，可能會出現(xiàn)有圖片但是不滿足消除規(guī)則的情況，重排的按鈕可以實(shí)現(xiàn)圖片的重新加載，從而能夠再次消除。同時(shí)為了給游戲增加一些可變因數(shù)，玩家在成功完成一輪游戲后，難度會增加，難度增加反應(yīng)到游戲中就是縮短了一輪游戲的時(shí)間，但是圖片的數(shù)量沒有改變，這就無形中增添了游戲的可玩性。 游戲設(shè)計(jì)的主要工作 游戲設(shè)計(jì)需要解決的問題開始制作游戲時(shí)，主要要解決的問題有以下幾個方面：如何設(shè)置整個游戲的界面；如何控制連連看游戲中隨機(jī)圖片的生成且每種圖片必須為偶數(shù)個；游戲開始后，判斷鼠標(biāo)兩次點(diǎn)擊的圖片能否消去，即圖片是否相同且圖片之間路徑的判斷；如何判斷游戲是否結(jié)束以及輸贏問題等。，為了保證成對，我們可以在存放的時(shí)候按照順序成組來存放，保證組的數(shù)量是偶數(shù)就可以實(shí)現(xiàn)，但是同時(shí)又存在一個問題，圖片在哪里存放，怎么引用圖片，為了簡化圖片的存放，結(jié)合連連看的表格形式，這里我們應(yīng)用二維數(shù)組、采用轉(zhuǎn)化的原則，將圖片依次編號和二維數(shù)組對應(yīng)，數(shù)組中的數(shù)字是0表示為空白，大于0的代表對應(yīng)的圖標(biāo)編號，這樣圖標(biāo)就可以容易替換成任何的圖片或者文字，這就很好的解決了圖片的按組存放規(guī)則；接下來還需要解決一個問題就是如何將圖片的順序打亂，這就需要應(yīng)用到關(guān)鍵方法——隨機(jī)函數(shù)，通過隨機(jī)函數(shù)和對換的思路，我們可以將圖片成功的隨機(jī)排列，基本解決了隨機(jī)性的問題。這樣圖片的位置模式大致就清晰了，1,2轉(zhuǎn)角均可以用0個轉(zhuǎn)角解決，遞歸的方式簡單易行，便于理解，思路層次分明。 游戲設(shè)計(jì)創(chuàng)新點(diǎn)，當(dāng)玩家在成功消除圖片之后，會給予時(shí)間的獎勵，時(shí)間進(jìn)度條增加，增強(qiáng)了玩家消除的積極性。3,重置功能，當(dāng)游戲陷入僵局的時(shí)候，重置功能可以成功解除僵局，使游戲繼續(xù)進(jìn)行。，游戲開始以后，時(shí)間以進(jìn)度條的方式提示，相比原來數(shù)字的提示更加清晰。2. 系統(tǒng)分析 技術(shù)可行性分析 算法分析連連看程序的關(guān)鍵是判斷用戶點(diǎn)擊兩個圖案能否消除，兩張圖片消除的條件有兩個：（即用不超過三根直線連接兩張圖片）根據(jù)判斷能否通過不超過三根直線連接兩張圖片的原則，有兩種實(shí)用的算法，下面是討論方案：：這里實(shí)質(zhì)上是一種遞歸的思想，要判斷圖片A與圖片B能否通過一條有N個轉(zhuǎn)角的路徑相連，可以轉(zhuǎn)化為判斷能否找到圖片C，C與A能直線相連，且C與B能用一條有N1個轉(zhuǎn)角的路徑相連。分類法一：根據(jù)轉(zhuǎn)角數(shù)不得超過2個的規(guī)則，我們可以分為轉(zhuǎn)角數(shù)分別為0個、1個、2個這三種情況分別討論。（紅色塊為欲消除塊）如圖21圖21b) 一個轉(zhuǎn)角連通：其實(shí)相當(dāng)于兩個圖片劃出一個矩形，這兩個圖片是一對對角頂點(diǎn)，另外兩個頂點(diǎn)如果可以同時(shí)和這兩個棋子直連，那就說明可以一折連通。這樣就將問題轉(zhuǎn)化為了0個轉(zhuǎn)角和1個轉(zhuǎn)角的情況，0個轉(zhuǎn)角可以直接相連，1個轉(zhuǎn)角可以轉(zhuǎn)化為以C點(diǎn)和B點(diǎn)為對頂角的矩形中尋找另外兩個對頂角之一，看能否分別和B、C相直連。判斷是否經(jīng)兩個轉(zhuǎn)角連通的算法需要做兩個方向上的掃描：水平掃描和垂直掃描。為了判斷A，B能否通過2個轉(zhuǎn)角連通，則從A開始在水平方向上向左右掃描，并判斷經(jīng)過的點(diǎn)能否與B點(diǎn)經(jīng)過1個轉(zhuǎn)角連通。（紅色塊為欲消除塊，黑色代表其他阻攔塊，黃色c代表折點(diǎn),綠色代表折線），如圖23圖23垂直掃描。顯然C點(diǎn)能與B點(diǎn)經(jīng)1個轉(zhuǎn)角連通，故A，B能經(jīng)2個轉(zhuǎn)角連通（紅色塊為欲消除塊，黑色代表其他阻攔塊，黃色c代表折點(diǎn),綠色代表折線），如圖24圖24：也可以如下類別進(jìn)行分析連連看的消除算法：a) 兩張圖片左右相鄰，如圖25圖25b) 兩張圖片上下相鄰，如圖26圖26c) 兩張圖片在同一行，它們中間相隔且沒有其它圖片遮擋，如圖27圖27兩張圖片在同一行，它們中間相隔且有其它圖片遮擋，但是它們存在不超過2個轉(zhuǎn)彎的路徑，如圖28圖28d) 兩張圖片在同一列，它們中間相隔且沒有其它圖片遮擋，如圖29圖29兩張圖片在同一列，它們中間相隔且有其它圖片遮擋，但是它們存在不超過2個轉(zhuǎn)彎的路徑，如圖210圖210e) 兩張圖片相鄰，但是它們存在不超過2個轉(zhuǎn)彎的路徑，如圖211圖211f) 兩張圖片不相鄰，但是它們存在不超過2個轉(zhuǎn)彎的路徑，如圖212圖212總結(jié)：分類法一和分類法二均涵蓋了連連看圖片全部位置情況，可以實(shí)現(xiàn)準(zhǔn)確實(shí)現(xiàn)連連看的消除功能，但是分類二的細(xì)節(jié)太多，顆粒度太小，分類一的分支清晰明確，顆粒度合適，因此在這里我選擇了分類法一。那么判斷B與A能否相連只需判斷B是否存在于集合S中即可。算法的思路如下： (1)定義空集S與T，將A加入集合S (2)找出所有與A能直接相連的點(diǎn)，將其加入集合S (3)找出與集合S中的點(diǎn)能直接相連的點(diǎn)，加入集合T，然后將T中所有元素加入到集合S中，清空集合T (4)找出與集合S