Android游戏开发之连连看算法

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

 

改写的连连看算法如下：

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

首先是横向检测：

 

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

 其次是纵向检测：

 

    private boolean vertical(Point a, Point b)
    {
        if(a.x == b.x && a.y == b.y)
            return false;
        int y_start = a.x <= b.x ? a.x : b.x;
        int y_end = a.x <= b.x ? b.x : a.x;
        for(int y = y_start + 1; y < y_end; y++)
            if(map[y][a.y] != -1)
                return false;
        return true;
    }

 一个拐角的检测：

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

 

    private boolean oneCorner(Point a, Point b)
    {
        Point c = new Point(a.x, b.y);
        Point d = new Point(b.x, a.y);
        if(map[c.x][c.y] == -1)
        {
            boolean method1 = horizon(a, c) && vertical(b, c);
                return method1;
        }
        if(map[d.x][d.y] == -1)
        {
            boolean method2 = vertical(a, d) && horizon(b, d);
            return method2;
        } else
        {
            return false;
        }
    }

 两个拐角的检测：

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

LIne类结构如下：

 

class Line
    {
        public Point a;
        public Point b;
        public int direct;

        public Line()
        {
        }

        public Line(int direct, Point a, Point b)
        {
            this.direct = direct;
            this.a = a;
            this.b = b;
        }
    }

 

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

 

	private LinkedList scan(Point a, Point b)
	    {
	        ll = new LinkedList<Line>();
	        //Point c = new Point(a.x, b.y);
	        //Point d = new Point(b.x, a.y);
	        for(int y = a.y; y >= 0; y--)
	            if(map[a.x][y] == -1 && map[b.x][y] == -1 && vertical(new Point(a.x, y), new Point(b.x, y)))
	                ll.add(new Line(0, new Point(a.x, y), new Point(b.x, y)));
	
	        for(int y = a.y; y < map.row; y++)
	            if(map[a.x][y] == -1 && map[b.x][y] == -1 && vertical(new Point(a.x, y), new Point(b.x, y)))
	                ll.add(new Line(0, new Point(a.x, y), new Point(b.x, y)));
	
	        for(int x = a.x; x >= 0; x--)
	            if(map[x][a.y] == -1 && map[x][b.y] == -1 && horizon(new Point(x, a.y), new Point(x, b.y)))
	                ll.add(new Line(1, new Point(x, a.y), new Point(x, b.y)));
	
	        for(int x = a.x; x < map.column; x++)
	            if(map[x][a.y] == -1 && map[x][b.y] == -1 && horizon(new Point(x, a.y), new Point(x, b.y)))
	                ll.add(new Line(1, new Point(x, a.y), new Point(x, b.y)));
	
	        return ll;
	  }

 最后是两个拐角的算法：

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

    private boolean twoCorner(Point a, Point b)
    {
        ll = scan(a, b);
        if(ll.isEmpty())
            return false;
        for(int index = 0; index < ll.size(); index++){
            Line line = (Line)ll.get(index);
            if(line.direct == 1){
                if(vertical(a, line.a) && vertical(b, line.b)){
                    return true;
                }

            } else
            if(horizon(a, line.a) && horizon(b, line.b)){
                return true;
            }
        }
        return false;
    }

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

	public boolean checkLink(Point a,Point b){
		if(map[a.x][a.y] != map[b.x][b.y])//如果图案不同，直接为false
            return false;
        if(a.x == b.x && horizon(a, b))
            return true;
        if(a.y == b.y && vertical(a, b))
            return true;
        if(oneCorner(a, b))
            return true;
        else
            return twoCorner(a, b);
	}

 

评论

23 楼 lujl1988 2010-09-15  

假如你的地图是8*10的，

sinye 写道

楼主，你的那个横向检测方法，在其中取x值范围区间的时候，我看的有些不明白。横向检测的时候，A点和B点的y坐标是相同的，是否应该
int x_start = a.x <= b.x ?a.x : b.x;  
int x_end = a.x <= b.x ? b.x : a.x;
这样横向时,可以取得A点和B点中间的点的坐标！望指导一二！

我也有同样的疑问，还望楼主指点一二

22 楼 dxq530610286 2010-04-16  

太激动了  好东西啊   回去也学习写一个

21 楼 sinye 2010-04-02  

楼主，你的那个横向检测方法，在其中取x值范围区间的时候，我看的有些不明白。横向检测的时候，A点和B点的y坐标是相同的，是否应该
int x_start = a.x <= b.x ?a.x : b.x;  
int x_end = a.x <= b.x ? b.x : a.x;
这样横向时,可以取得A点和B点中间的点的坐标！望指导一二！

20 楼 HEXLee 2009-10-14  

BZ写的很细致，我也写了一个连连看算法，BZ也到我的博客去看看哈~
我也喜欢游戏制作，希望加我好友QQ81539637

19 楼 wtotal 2009-10-10  

bengan 写道

raymondlueng 写道

bengan 写道

可以介紹下連連看遊戲場景生成的算法嘛？怎麼確保生成遊戲場景不是一出來就是死胡同

假如你的地图是8*10的，游戏中一共有80个图案，又假如图案的种类有10种，则可以定义每种图案8个的8*10的二维数组，然后将数组打乱，那这样的生成的场景就是可配对的了。
另外，有可能生成的地图刚好每一个都不能连通的，这就要做一个CheckAvailable（）函数，因为连连看中都会有提示功能，CheckAvailable（）函数调用提示功能的函数，利用其返回值就可以知道游戏能不能玩了，能玩就继续，不能玩就以某种方式对地图重新排列。

能否再講解一下CheckAvailable（）函数的實現呢。我怕會有這樣一種情況，地圖連第一個是可以一直到了第10個才發現到了死胡同，這種情況你現在是怎麼處理呢？

到第10个发现玩不下去可以gameover或重排嘛。

18 楼 bengan 2009-10-07  

raymondlueng 写道

bengan 写道

可以介紹下連連看遊戲場景生成的算法嘛？怎麼確保生成遊戲場景不是一出來就是死胡同

假如你的地图是8*10的，游戏中一共有80个图案，又假如图案的种类有10种，则可以定义每种图案8个的8*10的二维数组，然后将数组打乱，那这样的生成的场景就是可配对的了。
另外，有可能生成的地图刚好每一个都不能连通的，这就要做一个CheckAvailable（）函数，因为连连看中都会有提示功能，CheckAvailable（）函数调用提示功能的函数，利用其返回值就可以知道游戏能不能玩了，能玩就继续，不能玩就以某种方式对地图重新排列。

能否再講解一下CheckAvailable（）函数的實現呢。我怕會有這樣一種情況，地圖連第一個是可以一直到了第10個才發現到了死胡同，這種情況你現在是怎麼處理呢？

17 楼 raymondlueng 2009-10-02  

变精华帖了，太感动了！

16 楼 xuhuiflygo 2009-09-30  

真的很不错。

15 楼 tedeyang 2009-09-30  

留名待查。。。。。

14 楼 raymondlueng 2009-09-30  

bengan 写道

可以介紹下連連看遊戲場景生成的算法嘛？怎麼確保生成遊戲場景不是一出來就是死胡同

假如你的地图是8*10的，游戏中一共有80个图案，又假如图案的种类有10种，则可以定义每种图案8个的8*10的二维数组，然后将数组打乱，那这样的生成的场景就是可配对的了。
另外，有可能生成的地图刚好每一个都不能连通的，这就要做一个CheckAvailable（）函数，因为连连看中都会有提示功能，CheckAvailable（）函数调用提示功能的函数，利用其返回值就可以知道游戏能不能玩了，能玩就继续，不能玩就以某种方式对地图重新排列。

13 楼 bengan 2009-09-30  

可以介紹下連連看遊戲場景生成的算法嘛？怎麼確保生成遊戲場景不是一出來就是死胡同

12 楼 zst504 2009-09-30  

谢谢楼主了！！

11 楼 hehawjq 2009-09-30  

多谢分享……

10 楼 lzyzizi 2009-09-30  

我记得我们站有个JS的连连看，那个算法好像也不错，有兴趣的可以参考下。

9 楼 superhanliu 2009-09-30  

不错。。学习学习。。谢谢分享。。

8 楼 lovesun723 2009-09-30  

楼主新帖，学习来了

7 楼 DoubleEO 2009-09-29  

谢谢，正在学习

6 楼 alexma 2009-09-29  

楼主，看了一下算法，感觉 two corner 的逻辑其实已经包含了 one corner 的情况了。总控函数只要调用一次 twocorner 就够了吧。

5 楼 lucane 2009-09-29  

两个拐角的检测就弄不明白了

4 楼 mikeshi 2009-09-29  

收藏了，以后有空仔细看看，谢谢楼主的无私奉献