Android游戏开发之连连看算法

Question

转自 http://www.javaeye.com/topic/480020

因为有朋友在站内信中问到连连看的具体算法，所以我就把算法post出来，这个算法也是参考网上Flash游戏的算法改写的，原来的参考信息已经找不到了，不过非常感谢那些无私的朋友。



改写的连连看算法如下：

前置条件：用一二维数组存放Map,-1表示没有图案可以连通，非-1表示不同的图案。

首先是横向检测：

www.javaeye.com__04d87645-d55a-344a-8cde-e2b148cb12dc.jpg (19.53 KB, 下载次数: 2)

下载附件

2011-03-21 16:16 上传

1.         private boolean horizon(Point a, Point b)
   
2.             {
   
3.                 if(a.x == b.x && a.y == b.y)//如果点击的是同一个图案，直接返回false
   
4.                     return false;
   
5.                 int x_start = a.y <= b.y ? a.y : b.y;
   
6.                 int x_end = a.y <= b.y ? b.y : a.y;
   
7.                 for(int x = x_start + 1; x < x_end; x++)//只要一个不是-1，直接返回false
   
8.                     if(map[a.x][x] != -1){
   
9.                         return false;
   
10.                     }
    
11.                 return true;
    
12.             }

复制代码其次是纵向检测：

www.javaeye.com__09e04ead-e191-3077-a471-9a101393f68c.jpg (15.95 KB, 下载次数: 2)

下载附件

2011-03-21 16:16 上传

1.     private boolean vertical(Point a, Point b)
   
2.     {
   
3.         if(a.x == b.x && a.y == b.y)
   
4.             return false;
   
5.         int y_start = a.x <= b.x ? a.x : b.x;
   
6.         int y_end = a.x <= b.x ? b.x : a.x;
   
7.         for(int y = y_start + 1; y < y_end; y++)
   
8.             if(map[y][a.y] != -1)
   
9.                 return false;
   
10.         return true;
    
11.     }

复制代码一个拐角的检测：

如果一个拐角能连通的话，则必须存在C、D两点。其中C点的横坐标和A相同，纵坐标与B相同，D的横坐标与B相同，纵坐标与A相同。

www.javaeye.com__8eeb8866-2de9-36ad-95fc-1fe01890d1ba.jpg (25.58 KB, 下载次数: 2)

下载附件

2011-03-21 16:16 上传

1.     private boolean oneCorner(Point a, Point b)
   
2.     {
   
3.         Point c = new Point(a.x, b.y);
   
4.         Point d = new Point(b.x, a.y);
   
5.         if(map[c.x][c.y] == -1)
   
6.         {
   
7.             boolean method1 = horizon(a, c) && vertical(b, c);
   
8.                 return method1;
   
9.         }
   
10.         if(map[d.x][d.y] == -1)
    
11.         {
    
12.             boolean method2 = vertical(a, d) && horizon(b, d);
    
13.             return method2;
    
14.         } else
    
15.         {
    
16.             return false;
    
17.         }
    
18.     }

复制代码两个拐角的检测：

这个比较复杂，如果两个拐角能连通的话，则必须存在图中所示的连线，这些连线夹在A、B的横、纵坐标之间,这样的线就以下这个类存储，direct是线的方向，用0、1表示不同的方向

www.javaeye.com__b7818289-3a4b-3c0d-94a8-c684e922b3a9.jpg (35.53 KB, 下载次数: 2)

下载附件

2011-03-21 16:16 上传

LIne类结构如下：

1. class Line
   
2.     {
   
3.         public Point a;
   
4.         public Point b;
   
5.         public int direct;
   
6. 
   
7.         public Line()
   
8.         {
   
9.         }
   
10. 
    
11.         public Line(int direct, Point a, Point b)
    
12.         {
    
13.             this.direct = direct;
    
14.             this.a = a;
    
15.             this.b = b;
    
16.         }
    
17.     }

复制代码从A、B点的横纵两个方向进行扫描，就是Scan函数做的事情，把合适的线用LinkList存起来。

www.javaeye.com__a78358ac-78d9-3647-9903-630fd7c7d3c9.jpg (41.29 KB, 下载次数: 2)

下载附件

2011-03-21 16:16 上传

1.         private LinkedList scan(Point a, Point b)
   
2.             {
   
3.                 ll = new LinkedList<Line>();
   
4.                 //Point c = new Point(a.x, b.y);
   
5.                 //Point d = new Point(b.x, a.y);
   
6.                 for(int y = a.y; y >= 0; y--)
   
7.                     if(map[a.x][y] == -1 && map[b.x][y] == -1 && vertical(new Point(a.x, y), new Point(b.x, y)))
   
8.                         ll.add(new Line(0, new Point(a.x, y), new Point(b.x, y)));
   
9.        
   
10.                 for(int y = a.y; y < map.row; y++)
    
11.                     if(map[a.x][y] == -1 && map[b.x][y] == -1 && vertical(new Point(a.x, y), new Point(b.x, y)))
    
12.                         ll.add(new Line(0, new Point(a.x, y), new Point(b.x, y)));
    
13.        
    
14.                 for(int x = a.x; x >= 0; x--)
    
15.                     if(map[x][a.y] == -1 && map[x][b.y] == -1 && horizon(new Point(x, a.y), new Point(x, b.y)))
    
16.                         ll.add(new Line(1, new Point(x, a.y), new Point(x, b.y)));
    
17.        
    
18.                 for(int x = a.x; x < map.column; x++)
    
19.                     if(map[x][a.y] == -1 && map[x][b.y] == -1 && horizon(new Point(x, a.y), new Point(x, b.y)))
    
20.                         ll.add(new Line(1, new Point(x, a.y), new Point(x, b.y)));
    
21.        
    
22.                 return ll;
    
23.           }

复制代码最后是两个拐角的算法：

取出LinkList里面的线，测试A与B到该线的两点是否连通。

1.     private boolean twoCorner(Point a, Point b)
   
2.     {
   
3.         ll = scan(a, b);
   
4.         if(ll.isEmpty())
   
5.             return false;
   
6.         for(int index = 0; index < ll.size(); index++){
   
7.             Line line = (Line)ll.get(index);
   
8.             if(line.direct == 1){
   
9.                 if(vertical(a, line.a) && vertical(b, line.b)){
   
10.                     return true;
    
11.                 }
    
12. 
    
13.             } else
    
14.             if(horizon(a, line.a) && horizon(b, line.b)){
    
15.                 return true;
    
16.             }
    
17.         }
    
18.         return false;
    
19.     }

复制代码前面的函数有以下这个总的调用函数来调用，传入两个点，就可以判断这两个点是否符合连连看的算法了：

1.         public boolean checkLink(Point a,Point b){
   
2.                 if(map[a.x][a.y] != map[b.x][b.y])//如果图案不同，直接为false
   
3.             return false;
   
4.         if(a.x == b.x && horizon(a, b))
   
5.             return true;
   
6.         if(a.y == b.y && vertical(a, b))
   
7.             return true;
   
8.         if(oneCorner(a, b))
   
9.             return true;
   
10.         else
    
11.             return twoCorner(a, b);
    
12.         }

复制代码