Java實現連連看算法
連連看是個經典的小遊戲,規則是:兩圖案相同的方塊在2折以內的線連接下可以消除。裡面的算法還是非常有趣,今天來研究一下。
初始化棋盤
假設有一個8*8的棋盤,我們要將其擴充至10*10,為什麼?因為這樣外圍的連接就可以不用越界瞭。
消除基本條件
判斷是否具備消除的基本條件有 3 個
- 兩個方塊不能是同一個坐標
- 兩個方塊必須是同種類型(圖案)
- 兩個方塊中不能有任何一個已經消除過的(消除過後的值用 mark 表示)
// 判斷是否具備消除的基本條件:兩個方塊不能是同一個坐標;兩個方塊必須是同種類型;兩個方塊中不能有任何一個已經消除過的 public static boolean basicCondition(Point a, Point b) { return !a.equals(b) && board[a.x][a.y] == board[b.x][b.y] && !isNull(a) && !isNull(b); } // 判斷格子是否為空或已經被消除 public static boolean isNull(Point c) { return board[c.x][c.y] == 0 || board[c.x][c.y] == mark; }
0折消除
能0折消除,說明兩個方塊一定在同一直線上;它們可能是同一水平直線,也可能是同一垂直直線
如果兩個方塊的相對位置滿足其中之一,並且我們再去判斷連線經過的方塊是否為空就行瞭。
// 判斷同一直線能否相連 public static boolean matchLine(Point a, Point b) { // 水平 if (a.x == b.x) { int minY = Math.min(a.y, b.y), maxY = Math.max(a.y, b.y); for (int i = minY + 1; i < maxY; i++) { if (!isNull(new Point(a.x, i))) return false; } return true; } // 垂直 else if (a.y == b.y) { int minX = Math.min(a.x, b.x), maxX = Math.max(a.x, b.x); for (int i = minX + 1; i < maxX; i++) { if (!isNull(new Point(i, a.y))) return false; } return true; } // 不在水平或垂直上 return false; }
1折消除
1折消除也就2種情況,就是上折和下折,這樣可以知道折點是(a.x, b.y)和(b.x, a.y) ;即判斷a點到折點能否0折消除,且b點到折點能否0折消除,且折點處為空
// 判斷 1 折能否相連:拐角點 c1 和 c2 與 a b 點能相連並且拐角點為空 public static boolean matchOneTurn(Point a, Point b) { Point c1 = new Point(a.x, b.y); Point c2 = new Point(b.x, a.y); return matchLine(a, c1) && matchLine(b, c1) && isNull(c1) || matchLine(a, c2) && matchLine(b, c2) && isNull(c2); }
2折消除
2折消除的邏輯稍微麻煩瞭一點點,即掃描 a 點所在的行和列,找一點 c ,使得 a 與 c 能夠0折消除且 b 與 c 能1折消除;掃描 b 點所在的行和列,找一點 c ,使得 b 與 c 能夠0折消除且 a 與 c 能1折消除,當然,c 點不能與 a b 點重合,也必須為空。
// 判斷 2 折能否相連:掃描 a 所在的行和列,找一點 c 使之與 a 直線匹配,與 b 1 折匹配;掃描 b 所在的行和列,找一點 c 使之與 b 直線匹配,與 a 1 折匹配 public static boolean matchTwoTurn(Point a, Point b) { // 掃描 a b 所在的行 for (int i = 0; i < c; i++) { Point c1 = new Point(a.x, i); Point c2 = new Point(b.x, i); if (i != a.y && matchLine(c1, a) && matchOneTurn(c1, b) && isNull(c1) || i != b.y && matchLine(c2, b) && matchOneTurn(c2, a) && isNull(c2)) return true; } // 掃描 a b 所在的列 for (int i = 0; i < r; i++) { Point c1 = new Point(i, a.y); Point c2 = new Point(i, b.y); if (i != a.x && matchLine(c1, a) && matchOneTurn(c1, b) && isNull(c1) || i != b.x && matchLine(c2, b) && matchOneTurn(c2, a) && isNull(c2)) return true; } // 不存在這樣的 c 點 return false; }
將上述所有判斷整合,就完成瞭一對方塊完整的消除判斷
// 整合判斷 public static boolean match(Point a, Point b) { return basicCondition(a, b) && (matchLine(a, b) || matchOneTurn(a, b) || matchTwoTurn(a, b)); }
關鍵算法解決瞭,相信寫一個連連看遊戲的障礙被打破瞭,是不是躍躍欲試瞭呢?
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。
推薦閱讀:
- 利用Java實現帶GUI的氣泡詩詞特效
- 前端canvas中物體邊框和控制點的實現示例
- 基於Python繪制子圖及子圖刻度的變換等的問題
- JavaScript實現div的鼠標拖拽效果
- 教你怎麼用Java回溯算法解數獨