1.14 連連看游戲設(shè)計(jì)

連連看是一種很受大家歡迎的小游戲。微軟亞洲研究院的實(shí)習(xí)生們就曾經(jīng)開(kāi)發(fā)過(guò)一個(gè)類似的游戲——Microsoft Link-up。

圖1-22為Microsoft Link-up的一個(gè)截圖。如果用戶可以把兩個(gè)同樣的圖用線（連線拐的彎不能多于兩個(gè)）連到一起，那么這兩個(gè)頭像就會(huì)消掉，當(dāng)所有的頭像全部消掉的時(shí)候，游戲結(jié)束。游戲頭像有珍稀動(dòng)物、京劇臉譜等。Microsoft Link-up還支持用戶輸入的圖像庫(kù)，微軟的同事們?cè)?jīng)把新員工的漫畫頭像加到這個(gè)游戲中，讓大家在游戲之余也互相熟悉起來(lái)。

假如讓你來(lái)設(shè)計(jì)一個(gè)連連看游戲的算法，你會(huì)怎么做呢？要求說(shuō)明：

1．怎樣用簡(jiǎn)單的計(jì)算機(jī)模型來(lái)描述這個(gè)問(wèn)題？

2．怎樣判斷兩個(gè)圖形能否相消？

3．怎樣求出相同圖形之間的最短路徑（轉(zhuǎn)彎數(shù)最少，路徑經(jīng)過(guò)的格子數(shù)目最少）？

4．怎樣確定死鎖狀態(tài)，如何設(shè)計(jì)算法來(lái)解除死鎖？

分析與解法

連連看游戲的設(shè)計(jì)，最主要包含游戲局面的狀態(tài)描述，以及游戲規(guī)則的描述。而游戲規(guī)則的描述就對(duì)應(yīng)著狀態(tài)的合法轉(zhuǎn)移（在某一個(gè)狀態(tài)，有哪些操作是滿足規(guī)則的，經(jīng)過(guò)這些操作，會(huì)到達(dá)哪些狀態(tài)）。所以，自動(dòng)機(jī)模型適合用來(lái)描述游戲設(shè)計(jì)。

代碼清單1-22是一個(gè)參考的連連看游戲的偽代碼。

代碼清單1-22

    生成游戲初始局面
    Grid preClick=NULL, curClick=NULL;
    while(游戲沒(méi)有結(jié)束)
    {
        監(jiān)聽(tīng)用戶動(dòng)作
        if(用戶點(diǎn)擊格子(x, y)，且格子(x, y)為非空格子)
        {
            preClick=curClick;
            curClick.Pos=(x, y);
        }
        if(preClick !=NULL && curClick !=NULL
            && preClick.Pic==curClick.Pic
            && FindPath(preClick, curClick) !=NULL)
        {
            顯示兩個(gè)格子之間的消去路徑
            消去格子preClick, curClick;
            preClick=curClick=NULL;
        }
    }

從上面的整體框架可以看到，完成連連看游戲需要解決下面幾個(gè)問(wèn)題：

1．生成游戲初始局面。

2．每次用戶選擇兩個(gè)圖形，如果圖形滿足一定條件（兩個(gè)圖形一樣，且這兩個(gè)圖形之間存在少于3個(gè)彎的路徑），則兩個(gè)圖形都能消掉。給定具有相同圖形的任意兩個(gè)格子，我們需要尋找這兩個(gè)格子之間在轉(zhuǎn)彎最少的情況下，經(jīng)過(guò)格子數(shù)目最少的路徑。如果這個(gè)最優(yōu)路徑的轉(zhuǎn)彎數(shù)目少于3，則這兩個(gè)格子可以消去。

3．判斷游戲是否結(jié)束。如果所有圖形全部消去，游戲結(jié)束。

4．判斷死鎖，當(dāng)游戲玩家不可能再消去任意兩個(gè)圖像的時(shí)候，游戲進(jìn)入“死鎖”狀態(tài)，如圖1-23所示。該局面中已經(jīng)不存在兩個(gè)相同的圖片相連的路徑轉(zhuǎn)彎數(shù)目小于3的情況。

在死鎖的情況下，我們也可以暫時(shí)不終止游戲，而是隨機(jī)打亂局面，打破“死鎖”局面。

首先思考問(wèn)題：怎樣判斷兩個(gè)圖形能否相消？在前面的分析中，我們已經(jīng)知道，兩個(gè)圖形能夠相消的充分必要條件是這兩個(gè)圖形相同，且它們之間存在轉(zhuǎn)彎數(shù)目小于3的路徑。因此，需要解決的主要問(wèn)題是，怎樣求出相同圖形之間的最短路徑。首先需要保證最短路徑的轉(zhuǎn)彎數(shù)目最少。在轉(zhuǎn)彎數(shù)目最少的情況下，經(jīng)過(guò)的格子數(shù)目也要盡可能地少。

在經(jīng)典的最短路徑問(wèn)題中，需要求出經(jīng)過(guò)格子數(shù)目最少的路徑。而這里，為了保證轉(zhuǎn)彎數(shù)目最少，需要把最短路徑問(wèn)題的目標(biāo)函數(shù)修改為從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的轉(zhuǎn)彎次數(shù)。雖然目標(biāo)函數(shù)修改了，但算法的框架仍然可以保持不變。廣度優(yōu)先搜索是解決經(jīng)典最短路徑問(wèn)題的一個(gè)思路。我們看看在新的目標(biāo)函數(shù)（轉(zhuǎn)彎數(shù)目最少）下，如何用廣度優(yōu)先搜索來(lái)解決圖形A（x1, y1）和圖形B（x2, y2）之間的最短路徑問(wèn)題。

首先把圖形A（x1, y1）壓入隊(duì)列。

然后擴(kuò)展圖形A（x1, y1）可以直線到達(dá)的格子（即圖形A（x1, y1）可以通過(guò)轉(zhuǎn)彎數(shù)目為0的路徑（直線）到達(dá)這些格子）。假設(shè)這些格子為集合S0, S0=Find（x1, y1）。如果圖形B（x2, y2）在集合S0中，則結(jié)束搜索，圖形A和B可以用直線連接。

否則，對(duì)于所有S0集合中的空格子（沒(méi)有圖形），分別找到它們可以直線到達(dá)的格子。假設(shè)這個(gè)集合為S1。S1={Find（p）|p ∈S0}。S1包含了S0，令S1'=S1-S0，則S1’中的格子和圖形A（x1, y1）可以通過(guò)轉(zhuǎn)彎數(shù)目為1的路徑連起來(lái)。如果圖形B（x2, y2）在S1’中，則圖形A和B可以用轉(zhuǎn)彎數(shù)目為1的路徑連接，結(jié)束搜索。

否則，繼續(xù)對(duì)所有S1’集合中的空格子（沒(méi)有圖形），分別找出它們可以直線到達(dá)的格子，假設(shè)這個(gè)集合為S2, S2=Find{ Find（p）|p ∈S1'}。S2包含了S0和S1，令S2'=S2-S0-S1=S2-S0-S1'。集合S2’是圖形A（x1, y1）可以通過(guò)轉(zhuǎn)彎數(shù)目為2的路徑到達(dá)的格子。如果圖形B（x2, y2）在集合S2’中，則圖形A和B可以用轉(zhuǎn)彎數(shù)目為2的路徑連接，否則圖形A和B不能通過(guò)轉(zhuǎn)彎小于3的路徑連接。

在擴(kuò)展的過(guò)程中，只要記下每個(gè)格子是從哪個(gè)格子連過(guò)來(lái)的（也就是轉(zhuǎn)彎的位置），最后圖形A和B之間的路徑就可以繪制出來(lái)。

在上面的廣度優(yōu)先搜索過(guò)程中，有兩步操作：S1'=S1-S0和S2'=S2-S0-S1。它們可以通過(guò)記錄從圖形A（x1, y1）到該格子（x, y）的轉(zhuǎn)彎數(shù)目來(lái)實(shí)現(xiàn)。開(kāi)始，將所有格子（x, y）和格子A（x1, y1）之間路徑的最少轉(zhuǎn)彎數(shù)目MinCrossing（x, y）初始化為無(wú)窮大。然后，令MinCrossing（A）=MinCrossing（x1, y1）=0，格子A到自身當(dāng)然不需要任何轉(zhuǎn)彎。第一步擴(kuò)展之后，所有S0集合中的格子的MinCrossing值為0。在S0集合繼續(xù)擴(kuò)展得到的S1集合中，格子X和格子A之間至少有轉(zhuǎn)彎為1的路徑，如果格子X本身已經(jīng)在S0中，那么，MinCrossing（X）=0。這時(shí)，我們保留轉(zhuǎn)彎數(shù)目少的路徑，也就是MinCrossing（X）=MinValue（MinCrossing（X）, 1）=0。這個(gè)過(guò)程，就實(shí)現(xiàn)了上面?zhèn)未a中的S1'=S1-S0。S2'=S2-S0-S1的擴(kuò)展過(guò)程也類似。

經(jīng)過(guò)上面的分析，我們知道，每一個(gè)格子X（x, y），都有一個(gè)狀態(tài)值MinCrossing（X）。它記錄下了該格子和起始格子A之間的最優(yōu)路徑的轉(zhuǎn)彎數(shù)目。廣度優(yōu)先搜索，就是每次優(yōu)先擴(kuò)展?fàn)顟B(tài)值最少的格子。如果要保證在轉(zhuǎn)彎數(shù)目最少的情況下，還要保持路徑長(zhǎng)度盡可能地短，則需要對(duì)每一個(gè)格子X保存兩個(gè)狀態(tài)值MinCrossing（X）和MinDistance（X）。從格子X擴(kuò)展到格子Y的過(guò)程，可以用下面的偽代碼實(shí)現(xiàn)。

    if((MinCrossing(X)+1<MinCrossing(Y))
        || ((MinCrossing(X)+1==MinCrossing(Y)
            && (MinDistance(X)+Dist(X, Y)<MinDistance(Y)))
    {
        MinCrossing(Y)=MinCrossing(X)+1;
        MinDistance(Y)=MinDistance(X)+Dist(X, Y);
    }

也就是說(shuō)，如果發(fā)現(xiàn)從格子X過(guò)來(lái)的路徑改進(jìn)了轉(zhuǎn)彎數(shù)目或者路徑的長(zhǎng)度，則更新格子Y。

“死鎖”問(wèn)題本質(zhì)上還是判斷兩個(gè)格子是否可以消去的問(wèn)題。最直接的方法就是，對(duì)于游戲中尚未消去的格子，都兩兩計(jì)算一下它們是否可以消去。此外，從上面的廣度優(yōu)先搜索可以看出，我們每次都是擴(kuò)展出起始格子A（x1, y1）能夠到達(dá)的格子。也就是說(shuō)，對(duì)于每一個(gè)格子，可以調(diào)用一次上面的擴(kuò)展過(guò)程，得到所有可以到達(dá)的格子，如果這些格子中有任意一個(gè)格子的圖形跟起始格子一致，則它們可以消去，目前游戲還不是“死鎖”狀態(tài)。

擴(kuò)展問(wèn)題

1．在連連看游戲設(shè)計(jì)中，是否可以通過(guò)維護(hù)任意兩個(gè)格子之間的最短路徑來(lái)實(shí)現(xiàn)快速搜索？在每一次消去兩個(gè)格子之后，更新我們需要維護(hù)的數(shù)據(jù)（任意兩個(gè)格子之間的最短路徑）。這樣的思路有哪些優(yōu)缺點(diǎn)，如何實(shí)現(xiàn)呢？

2．在圍棋或象棋游戲中，經(jīng)過(guò)若干步操作之后，可能出現(xiàn)一個(gè)曾經(jīng)出現(xiàn)過(guò)的狀態(tài)（例如，圍棋中的打劫）。如何在圍棋、象棋游戲設(shè)計(jì)中檢測(cè)這個(gè)狀態(tài)呢？