連連看游戲搜索算法的研究與改進

李麗惠，莊楊波

?

連連看游戲搜索算法的研究與改進

李麗惠，莊楊波

（漳州職業(yè)技術(shù)學(xué)院計算機工程系，福建漳州363000）

近幾年，連連看游戲作為一個家喻戶曉的大眾化游戲，被廣大玩家喜歡和接受，作為一款益智類的游戲，連連看更是一個百玩不厭的經(jīng)典。對目前所常見的連連看游戲進行算法的研究與改進，使其在響應(yīng)速度更快，更需要玩家采用更合適的策略以便得到更好的游戲成績。重點是對地圖繪制、連通消除、關(guān)卡設(shè)置、勝利目標(biāo)等涉及到的相關(guān)算法進行了研究和討論。

廣度優(yōu)先；算法；隨機調(diào)度

1 引言

“連連看”游戲是一種流行廣泛的單機版游戲，游戲規(guī)則是：在初始化的一定數(shù)量的圖片中，選擇圖案相同的兩張依次點擊，若兩張圖片的位置滿足一定的條件，則會被自動消除[1]。在規(guī)定的時間內(nèi)給出的所有圖片均被消除，則當(dāng)前關(guān)卡結(jié)束，進入下一關(guān)，還在普通連連看的基礎(chǔ)上增加了兩個游戲策略：（1）如果將“障礙物”圖標(biāo)全部消除，則本關(guān)勝利。（2）當(dāng)兩個圖標(biāo)的連線碰到“炸彈”時，則游戲中的此種圖標(biāo)全部消除。本文主要是對“連連看”游戲算法進行了研究與改進，希望該研究使新版本的游戲得到更廣泛的喜歡和應(yīng)用。

2 算法分析

基本的游戲流程如圖1。

圖1 “連連看”游戲流程

對照流程圖，涉及的主要算法有：

2.1 地圖初始化

整個游戲區(qū)域主體部分可以看作是一張二維表格，使用二維數(shù)組Map[i][j]進行表示。游戲過程中，用戶可以手動設(shè)置所需要的地圖，根據(jù)保存在文件夾下的配置文件，用0和1分別表示地圖中是否顯示圖片（0和1的設(shè)置數(shù)量應(yīng)該均設(shè)為偶數(shù)），如果當(dāng)前位置是1，則顯示圖片；如果是0，則不顯示圖片。圖片的顯示應(yīng)該是隨機并且成對出現(xiàn)，采用另一個二維數(shù)組IsFace[i][j]進行表示，初始值IsFace[i][j]均為0，表示尚未放置圖片（如下圖2所示，該地圖為隔空放置圖片，其中◎表示障礙物，※表示炸彈）。

（1）先處理“障礙物”圖標(biāo)的位置，隨機產(chǎn)生一個i，j，若Map[i][j]=1且IsFace[i][j]=0，放置“障礙物”圖標(biāo)，并修改IsFace[i][j]的值，直到24個“障礙物”圖標(biāo)全部放置完畢。

（2）遍歷整個Map[i][j], 若Map[i1][j1]=1且IsFace[i1][j1]=0，則隨機從圖庫中挑一個圖片，并且隨機在另一個尚未放置圖片的位置i2,j2處放置相同的圖片, 放置好后修改兩處的IsFace值為1。

（3）遍歷整個Map[i][j], 若Map[i][j]=0且IsFace[i][j]=0，則隨機找到一個i3, j3, 若IsFace[i3][j3]=0，則放置不多于15個“炸彈”圖標(biāo)。此處的IsFace[i][j]在每次進行消除一組對象之后都會重新置為1，刷新“炸彈”布局圖。

Ⅲ◎Ⅳ ⅤⅥⅠⅠ ⅫⅢⅨ※ Ⅱ◎◎ ◎※Ⅺ◎ ⅫXI※Ⅱ◎

2.2 “炸彈”規(guī)則

“炸彈”不同于圖片及“障礙物”，不可單獨點擊連接（不可點擊），也不會影響圖片及“障礙物”的連接判定。滿足消除規(guī)則的前提下，若其連接線有“炸彈”，則把地圖上所有該類圖片，全部消除。

2.3 判斷消除

要判斷兩張圖片是否能被消除，要分3種情況來考慮，若其中一種情況達成的話，則消除圖片，否則此次操作無效。

（1）兩張圖片處于同一行或者同一列，并且其直線連接線之間，不含其它圖標(biāo)及“障礙物”（可以包含“炸彈”），此位置關(guān)系稱為“0折型”，如圖2第二行的兩個“I”圖標(biāo)所示。

（2）兩張圖片不處于同一行或者同一列，則以這兩張圖片作為矩形的對角點，沿著矩形從起點到終點就有兩種方式，如果某一方式“沿途”不含其它圖標(biāo)及“障礙物”（可以包含“炸彈”），此位置關(guān)系稱為“一折型”，如圖2第四行第一列和第六行第五列的兩個“II”圖標(biāo)所示。

（3）兩張圖片需要通過三條線（三條連接線之間，不含其它圖標(biāo)及障礙物，卻可以包含“炸彈”）才能連接，此位置關(guān)系稱為“兩折型”，如圖2第一行第二列和第三行第五列“III”圖標(biāo)所示。

2.3.1 廣度優(yōu)先搜索

在算法中，“0折型”和“一折型”采用的是較為簡單的判斷操作，排除掉這兩種情況后，剩下的均采用廣度優(yōu)先搜索算法進行判斷是否可消除。廣度優(yōu)先搜索算法，本質(zhì)是一種建立搜索樹然后剪枝的策略，它實現(xiàn)的是對整張圖進行徹底的搜索，直到找到結(jié)果為止。它對圖形采用層次結(jié)構(gòu)進行遍歷，先是根節(jié)點，然后是第二層子節(jié)點，依此進行下去，將每個節(jié)點放到一個隊列中，按照“先進先出”的順序，每次從隊列中探出“首元素”，遍歷后的點放入CloseArr數(shù)組(存放已經(jīng)訪問過的節(jié)點)，還未遍歷的點放入OpenArr數(shù)組（存放即將訪問的節(jié)點），當(dāng)OpenArr數(shù)組到最后一個點時，則整個遍歷完全。即尋找到從左上角的圖片A到右下角的圖片B之間不超過三折的最短路徑。算法的思想是：首先在A的位置向四個方向（下，右，上，左）進行直線查找，如果在某一方向上找到圖形B，則搜索結(jié)束，否則記錄下所有這四個方向上的空格（沒有圖片的位置）位置，并在每一個空格的其他三個方向上進行進一步的直線搜索，如果仍未找到B，則再次記錄下查找過程中沿途記錄下來的空格（除了已經(jīng)記錄的空格），并繼續(xù)在三個方向上進行搜索，依次遞歸搜索下去。若找到則返回并且消除，否則說明這兩張圖片之間不能進行消除。

2.3.2 消除判斷的實現(xiàn)

按照上面定義的消除策略，可以對三種情況分別使用三個函數(shù)來進行數(shù)據(jù)的查找。

設(shè)定“0折型”的函數(shù)是bool GetLine（GetLine(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode），循環(huán)查找同行或者同列中空白位置，直到目標(biāo)圖形所在的行或者列，一旦發(fā)現(xiàn)有一條直通線，則返回為真，否則返回為假。

設(shè)定“一折型”的函數(shù)是bool GetOneCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，取兩個圖片中較小的行號、列號和較大的行號、列號，構(gòu)成一個矩形，進行判斷。如果從圖片A出發(fā)，經(jīng)過一個拐彎能夠直通到圖片B，那么記錄下拐點的信息及A、B點的位置信息，并且函數(shù)返回為真，否則返回為假。

設(shè)定“兩折型”的函數(shù)為bool GetTwoCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，這個函數(shù)需要從四個方向進行逐一查找,每查找到一個新空格時，即調(diào)用“一折型”的函數(shù)bool GetOneCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，判斷當(dāng)前新空格是否可以與目標(biāo)圖形形成一個通路，如果該函數(shù)返回的是為真，則從圖形A和圖形B構(gòu)成的通路就是“兩折型”，如果該函數(shù)返回為假，則從下一個空格繼續(xù)進行查找，直到全部遍歷，遍歷完后如果沒有找到通路，則“兩折型”函數(shù)返回為假。

炸彈消除的實現(xiàn)可以設(shè)定函數(shù)CollectBombsAndFaces()，當(dāng)兩個方格可以連接時，搜集連線所經(jīng)過的炸彈的所有索引號和必須消除的所有方格的索引號，并將它們保存至數(shù)組bombIndexes和faceIndexes中[3]。一旦碰到所登記的炸彈，則圖片對應(yīng)的相同索引號的圖片均被消除掉。

2.4 特殊情況的處理

每消除兩張圖片后，程序就會檢測一次當(dāng)前棋盤上是否還存在滿足消除條件的圖片，若沒有則稱為死鎖[2]。若發(fā)生死鎖，則調(diào)用前面的隨機算法對當(dāng)前棋盤上的圖片重新排列一次，直到死鎖解除。

3 結(jié) 論

本文考慮了單機版的連連看游戲的算法研究與改進，并增加了“炸彈”和“障礙物”圖片以增加游戲的策略性，能夠讓玩家在玩的同時綜合考慮策略的應(yīng)用技巧，更具有一定的趣味性，可以同時應(yīng)用在手機版和電腦板的連連看游戲上。不足之處是尚未深入考慮網(wǎng)絡(luò)版的連連看采用雙方對戰(zhàn)的形式，當(dāng)一方消除一組圖片時則對方相應(yīng)的增加一定量的“障礙物”，讓游戲更具有一定的趣味性和挑戰(zhàn)性。

[1]仇賓. 基于Java的“連連看”游戲[J]. 電腦編程技巧與維護, 2013(11): 72-77.

[2]趙海國，屈洋. 連連看游戲的設(shè)計及其實現(xiàn)[J]. 湖南理工學(xué)院學(xué)報, 2015(3): 39-42.

[3]畢文斌，孫明亮. C# Windows游戲設(shè)計[M]. 北京: 清華大學(xué)出版社, 2014.

（責(zé)任編輯：馬圳煒）

Research and improvement of Lianliankan Game search algorithm

LI Li-hui, ZHUANG Yang-bo

(Computer Department of Zhangzhou Institute of Technology, Zhangzhou 363000, China)

Lianliankan game as a popular game known to every family this years, love and acceptance by the majority of game player, as a puzzle game, Lianliankan is a play for the classic. This paper is mainly on the current common game for the study and improvement of the algorithm to make it faster in response, but also requires the player to use a more appropriate strategy in order to get better results of the game. Focus is on map drawing, connectivity, the level set, the victory of the target and other related algorithms are studied and discussed.

breadth first; algorithm; random scheduling

1673-1417（2016）04-0017-04

10.13908/j.cnki.issn1673-1417.2016.04.0004

TP317.4

A

2016－09－15

李麗惠(1982—)，女，福建漳州人，高級工程師，碩士，研究方向：軟件開發(fā)與應(yīng)用。