连连看地图生成算法



方法2:
         1.首先确定要生成什么尺寸的连连看,比如12 x 8,16 x 24 ...
         2.在布局中心区域内随机放置一对棋子。第一对棋子不管怎么放,根据连连看的规则都是可以消除的,所以什么都不要管,转到3。
         3.继续放置下一对棋子
         4.还有空位可以放棋子吗,没有的话转到第7步。有的话转到第5步。
         5.检测新放入的这对棋子,可不可以根据连连看规则消除,可以的话转到3,不行的话,转到第6步。
         6.撤销这对棋子的放置,并用数组记录这对新棋子是如何放的,以免下次重复这样放,转到3.
         7.用自动求解函数验证新生成的布局是否有解,有解就大功告成,无解就跳转到第8步。
         8.从最后放的棋子开始回溯,通过回溯改变了棋子的布局,再转到第7步。
          为什么要验证?最后放置的两对棋子可以让整个棋局无解,但回溯的次数应该不多,我猜平均两三次吧。这个方法的缺点是随机产生布局的样本空间比方法1和方法3小,
实际上第5步可以改成用自动求解函数求解当前残局,没有则回溯,有则放置下一对,但这样一来样本空间大了,效率又低了。
方法3:
          1.随机生成一个连连看的布局,这个布局可能无解。
          2.自动求解的这个布局。
          3.有解就大功告成,无解转到第1步。
        另外,其实连连看的初始布局无解也无所谓,但必须保证至少有一对棋子可以消除以及用户在玩游戏过程中每消除一对棋子,都是有至少一对棋子是可以消除的。如果用户在玩游戏过程中出现死局(没有任何一对棋子可以消除了),就变换布局,使得至少有一对棋子可以消除。这样的话初始布局肯定可以消除完。
        最终当我把连连看游戏做出来后,发现自动求解对于一个连连看游戏并不是一个必要的功能,没有自动求解功能的连连看,用户照样可以玩的很high,而自动求解应该是连连看游戏开发过程中,最难的一个模块,比连连看的布局生成还难。

        1.连连看在判断一对棋子是否可以消除时,推荐用广度优先搜索,在自动求解连连看时,推荐用深度优先搜索。

http://www.cocos.com/doc/tutorial/show?id=1828
其实连连看使用的算法并不多,主要还是集中在地图生成算法、匹配消除算法。我们先来看看地图生成算法

地图生成算法

连连看的地图其实可以简单的看成一个二维数组,数组的大小取决于所要绘制的元素的个数。但是我们我们必须要保证元素是成对出现的,也就是说,假如显示的数组的长为m,宽为n,那么必须要保证* m \ n / 2 == 0 **。
现在我们来看下地图生成的几种算法(以5*6)的数组为例:
  1. 生成一个m*n/2的数组,然后再把数组的前一半拷贝到数组的后一半,随机进行打乱。
    我们用lua来演示下吧:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    matrix = {}
    total_row = 5
    total_col = 6
    total_type = 5
    for i = 1, (total_row*total_col)/2 do
        matrix[i] = math.random(1, 5)
    end
    for i = 1, (total_row*total_col)/2 do
        table.insert(matrix, matrix[i])
    end
    ==> 1,3,1,5,3,3,
        2,5,5,4,1,5,
        4,3,2,1,3,1,
        5,3,3,2,5,5,
        4,1,5,4,3,2,
    从生成的数据可以看出,这种方法离散度并不是太强。我们还需要再随机一次,将原有的数据打乱。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    for seq = 1, 13*2 do
        for i = 1, #self.m_sprites do
            local row_org = math.random(1, total_row)
            local col_org = math.random(1, total_col)
            local row_dest = math.random(1, total_row)
            local col_dest = math.random(1, total_col)
            matrix[(row_org-1)*total_col + col_org], matrix[(row_dest-1)*total_col + col_dest]
            = matrix[(row_dest-1)*total_col + col_dest], matrix[(row_org-1)*total_col + col_org]
        end
    end
    ==> 5,2,1,3,1,3,
        3,5,1,3,3,4,
        3,5,4,1,2,4,
        3,2,1,1,5,5,
        5,2,3,5,5,4,
  2. 模板法。所谓模板就是手动或者用工具建立一个模板,在生成地图时,根据模板的设置来生成地图。比如我们生成一个地图格式如下:
    1
    2
    3
    4
    5
    6
    7
    map = {
        1,2,3,4,5,6,
        5,4,3,2,1,6,
        1,2,3,4,5,5,
        3,5,4,2,1,6,
        2,4,3,5,2,1
    }
    我们可以根据上面的地图模板生成对应的精灵并且显示出来。其实这个方法应该是最有效的生成地图的方法,能适应各种需求。
上面描述的方法中,我们都没有确定地图是否有解。对于模板法其实我们在生成地图的时候就可以生成一个有解的地图;对于随机生成法来说就比较麻烦了,我们必须要去解地图。而解地图就要用到我们下面要讲述的匹配消除算法了。
http://upupxjg.blog.51cto.com/2665891/662658/
方法三:
1、先随机生成二维数组半数的元素,将其复制到二维数组的另一半。
2、遍历数组,随机交换数组中的元素。

判断图是否有解最直接的方法就是——解一张图,如果发现无解就重新生成一张再解(暴力啊)。
另一方法:
1、解图,将消去的元素按其位置不变存放于另一个空二维数组中,直到原图无解;
2、将原图元素限定在非空元素位置重排;
3、然后继续解图,将消去元素对应位置放于另一个数组中。
4、重复2、3直到原图消完。此时另一个数组中存放的即是一个有解图。
注:本人认为此方法可行性最高。





Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts