目 錄
一 連連看的要求
二 任意兩點能否連通
三 地圖無解提示
四 連接提示功能
五 道具問題
六 地圖問題
一、連連看的要求
1：要連接的兩點上的圖形是相同的。
2：兩點間存在一條沒有「障礙」的並且折點不超過兩個的路線。
那麼分析一下可以看到，一般分為三種情況
【圖例說明】
假設以一個2維數組來表示一張連連看的地圖，數組中
元素值為0的代表遊戲界面中的空格子，值大於0的代表遊戲
中的各種連接對像（1代表星星、2代表企鵝之類）
情況一：要連接的兩點在同一條直線上
0 0 0 0 0 0
0 2 0 0 0 2 * ------ *
0 0 0 0 0 0
情況二：經過一個折點相連（+號代表折點）
0 0 0 0 0 0
0 2 0 0 0 + * ------ +
0 + 0 0 0 2 + ------ *
（兩條路都可連通）
情況三：經過兩個折點相連（針對企鵝來說，即數字2）
0 + 0 0 0 + 0 0 0 0 0 0
0 2 0 1 0 2 0 2 0 1 0 2
0 0 0 0 0 0 或者 0 + 0 0 0 +
由於有1這個障礙，所以需要兩個折點才能連通
二、任意兩點能否連通
尋路算法是整個遊戲的核心算法。網上實現的版本也很多，這裡
的方法是我比較容易理解的一個方法^o^ ，還希望大家能提出寶
貴的批評意見和建議，謝謝了。
思路如下：
1 一條直線上兩點能否相連是好判斷的（一個簡單的循環判斷即可）
2 對於上面圖例的情況二，折點的坐標是固定的，即折點要麼是
[連點1的坐標x，連點2的坐標y]要麼是[連點1的坐標y，連點2的坐標x]
y
|
|
| * ------ +
| + ------ *
---------------- x
所以，我們只需判斷連點1到折點能否連通，連點2到折點能否連通即可
得知連點1和連點2能否連通。並且由於折點與兩個連點分別是在同一條
直線上，所以可以由第一步輕鬆判斷得出結論。
3 將情況三轉化為情況二，（這一步是該算法中最影響性能和需要改進的地方）
怎麼轉化？
0 + 0 0 0 +
0 2 0 1 0 2
0 0 0 0 0 0 （情況三）
將和其中一個連點在同一條直線上的折點當作該連點，那麼情況三就轉化為
了情況二
0 2 0 0 0 +
0 * 0 1 0 2 （星號為原先的連點）
0 0 0 0 0 0 （轉化後的情況三，最左上的折點已經被替換）
現在兩個連接對像2之間的情形，已經變為情況二了。
4 由上可知，尋找這個被替換的折點就成了關鍵。因為其坐標不固定，所以只
好遞歸一個一個尋找了。尋找這個點需要做很多的優化（偶也沒想到多少）
2 0 0 0 0 + 0 * 0 + 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 2 0 0 0 * 0 + 0 0
0 0 0 1 2 * 0 2 1 0 0 0 0 2 1 2 0 0
上面三個圖，+號是折點，*號就是需要被替換的折點
假設A、B兩點是同一個圖形，來思考一下下面的路線
0 0 0 0 0 0
0 0 1 0 B 0
0 0 0 0 0 0
0 A AA 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
如果我們的算法從向右開始尋找，順時針方向旋轉，那麼A點先向右移動1格
到達AA的位置，這時測試AA與B是否能連通（按情況二處理）,結果不能，因
為折點出都有「障礙」（兩個1），然後A點在移動，到達AAA處
0 0 0 0 0 0
0 0 1 0 B 0
0 0 0 0 0 0
0 A AA AAA 1 0
0 0 0 0 0 0
0 0 0 0 0 0
在AAA處，再次與B點測試連通的時候（按情況二處理），結果是可以，所以
A點可以與B點連通，路線為
+ *
|
* －－－+
在增加一個障礙
0 0 0 0 0 0
0 0 1 1 B 0
0 0 0 0 0 0
0 A AA AAA 1 0
0 0 0 0 0 0
0 0 0 0 0 0
這次，當尋找到AAA位置時，結果為不能連通。在向右，由於有障礙，所以向
右這條路，宣告失敗，遞歸返回到原點，換一個方向從A點向下在開始判斷
0 0 0 0 0 0
0 0 1 1 B 0
0 0 0 0 0 0
0 A 0 0 1 0
0 AA 0 0 0 0
0 AAA 0 0 0 0 (向下仍不能連通)
向左，一樣。最後向上
0 0 0 0 0 0
0 0 1 1 B 0
0 AA 0 0 0 0
0 A 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0 (AA點與B點符合情況二，可以連通)
路線為
*
|
-----------
|
*
最壞的情況，以QQ 11*19 的大小來計算， 共需移動28次，情況2共
循環不超過500次
0 0 0 0 0 0
0 0 1 1 B 0
0 0 0 1 1 1
0 A 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
三、地圖無解提示
因為連接對象的位置是固定的（用重列道具後位置也是固定的），我
們以n個字符串（字符串1維數組） 來記錄這些位置信息（n==遊戲中出現
的物體種類數），一個字符串記錄一種，格式型如：
10208110507151218
第一位1，表示物體的類別（是企鵝？是星星？）
後面16位每4位一組，表示屬於這個類別的一個對象的位置
信息，0208 表示 數組中的坐標 Array[2][8],即星星這個
類別中，有一個星星在遊戲中的坐標是[2][8]。
這樣，我們就在同一類別中，尋找該類別中現存的任意組合能否連通。
即該類中的一個對像能否和該類別中其它對像連通。
只要找到一個，即有解。如果查找完所有的，那麼就提示無解。
當我們消去一對連接對像時，在相應的字符串中刪除掉這兩個連接對
象的位置信息（對應位置字符串變為－1），比如0208變為-1-1。
四、連接提示功能
根據上面的位置信息數組，按類別依次即時計算該連接對像能否和該
類中其它連接對像相連。比如讀取數組的第一個元素，在提取這個字符串
中第一個連接對象的信息，比如1-1-11105-1-11218這個字符串， 提取出
11，5這個位置信息，用它來連接12，18看能否連通。
五、道具問題
1，鏡子
依然根據位置信息字符串數組，提取每個對象的位置，然後用該連
接對象的坐標x-（遊戲寬度-1）取絕對值。
0 0 0 0 0 0 0 0
* 0 0 0 0 0 0 * 0 - 3 ＝ -3
0 * 0 0 0 0 * 0 1 - 3 ＝ -2
0 0 0 0 0 0 0 0
－－－－－ －－－－－
0 1 2 3 0 1 2 3
2，重列
假設我們在某局遊戲中共出現了15種連接對象，每種4個，用1代表星星
2代表企鵝...... ，那麼我們仍定義一個字符串444444444444444 一共
15個4，該字符串的每一位對應一個連接對象，比如第一位對應星星在
遊戲中還有多少個（4個），第二位代表企鵝在遊戲中還有多少個......
當我們銷掉某個圖片的時候，也對這個字符串對應的位置-2，而將這個
字符串的每一位的數字相加，就是目前遊戲剩下的圖片數（QQ提示）。
當其他遊戲者對自己使用增加障礙道具時，相應位置+2即可。
現在遊戲中連接對象的位置知道（位置信息數組），數量知道（定義的
字符串），根據位置隨機出現一個連接對象，如果該連接對像在前面定
義的字符串中仍有數值（不為0），我們在以另一個字符串來記錄這個變
化（與前面功能結構完全相同），如果新字符串上的相應數值與原字符串
上的相應數值相等了，則不在出現這種類型了（重列的類型數量和以前一
樣），掃瞄完所有的位置，從而實現了重列。（新舊字符串應相等，因為
只是改變某個連接對象的位置，而數量沒有改變）
3，什麼時候出現道具？
我感覺好像QQ的道具出現的比較公平（你出現，別人也有），這裡就乾脆
這麼定義吧：在某個時機（銷了某個數量後，或者接連快速的銷了多少對）
那麼就隨機出現某種道具。
六、地圖問題
用這樣一個數組代表我們想定制的排列形狀
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
數組中為0的就是遊戲中的空格，為1的代表某種連接對象，這樣我們就可以訂製任意的形狀了。
根據這個數組，如果某個點的值不為0，則隨機生成一個連接對象，並在前面的種類詳細數量
字符串中的對應位置+1（QQ是每種4個），當這個位置（種類）的值為4時，就不再增加了。
喜歡玩QQ的連連看，很想自己也寫一個，故有此文。
|
|
當前位置：開發者網絡 >> 技術教程 >> JSP教程 >> 資料/其它 >> 內容
