模仿QQ連連看【思路、java源碼】 - 中國WEB開發者網絡 (http://www.webasp.net) -- 技術教程 (http://www.webasp.net/article/) --- 模仿QQ連連看【思路、java源碼】 (http://www.webasp.net/article/18/17971.htm) |
| -- 作者：未知 -- 發佈日期： 2005-04-26 |
| 目 錄
一 連連看的要求 二 任意兩點能否連通 三 地圖無解提示 四 連接提示功能 五 道具問題 六 地圖問題 一、連連看的要求 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的連連看，很想自己也寫一個，故有此文。 |
| webasp.net |