cocos2d-x3.6 连连看连通算法_app

概述我的博客：http://blog.csdn.net/dawn_moon 上一章讲了连连看游戏的主要逻辑，连通算法并有讲如何实现。这个连连看没有使用广度优先搜索算法，采用的是一种比较有技巧的算法，参见前面章节。大致分为几个部分：直连通两个点X轴扩展后可以直连通两个点Y轴扩展后可以直连通看下连接函数 bool GameScene::link(cocos2d::Vec2 v1, cocos2

我的博客：http://blog.csdn.net/dawn_moon

上一章讲了连连看游戏的主要逻辑，连通算法并有讲如何实现。

这个连连看没有使用广度优先搜索算法，采用的是一种比较有技巧的算法，参见前面章节。

大致分为几个部分：

直连通两个点X轴扩展后可以直连通两个点Y轴扩展后可以直连通

看下连接函数

bool GameScene::link(cocos2d::Vec2 v1,cocos2d::Vec2 v2){    if (v1.equals(v2)) {        return false;    }    // 路径点集，是一个vector    mPath.clear();    // 判断点击的两个点是不是图案一致    if (mMap[(int)v1.x][(int)v1.y] == mMap[(int)v2.x][(int)v2.y]) {        // 直连        if (linkD(v1,v2)) {            mPath.push_back(v1);            mPath.push_back(v2);            return true;        }        // 一个拐角，对角可直连        auto p = Vec2(v1.x,v2.y);        if (mMap[(int)p.x][(int)p.y] == 0) {            if (linkD(v1,p) && linkD(p,v2)) {                mPath.push_back(v1);                mPath.push_back(p);                mPath.push_back(v2);                return true;            }        }        // 一个拐角，对角可直连        p = Vec2(v2.x,v1.y);        if (mMap[(int)p.x][(int)p.y] == 0) {            if (linkD(v1,v2)) {                mPath.push_back(v1);                mPath.push_back(p);                mPath.push_back(v2);                return true;            }        }        // X扩展，判断是否有可直连的点        expandX(v1,p1E);        expandX(v2,p2E);        for (auto pt1 : p1E) {            for (auto pt2 : p2E) {                if (pt1.x == pt2.x) {                    if (linkD(pt1,pt2)) {                        mPath.push_back(v1);                        mPath.push_back(pt1);                        mPath.push_back(pt2);                        mPath.push_back(v2);                        return true;                    }                }            }        }        // Y扩展，判断是否有可直连的点        expandY(v1,p1E);        expandY(v2,p2E);        for (auto pt1 : p1E) {            for (auto pt2 : p2E) {                if (pt1.y == pt2.y) {                    if (linkD(pt1,pt2)) {                        mPath.push_back(v1);                        mPath.push_back(pt1);                        mPath.push_back(pt2);                        mPath.push_back(v2);                        return true;                    }                }            }        }        return false;    }    return false;}

连通函数的基础是直连通，两个点，最后都要转化成是否可直连，来看这个函数：

bool GameScene::linkD(Vec2 v1,Vec2 v2){    // X坐标一致，逐个扫描Y坐标，中间如果都是通路，那么可以直连    if (v1.x == v2.x) {        int y1 = MIN(v1.y,v2.y);        int y2 = MAX(v2.y,v2.y);        bool flag = true;        for (int y = y1 + 1; y < y2; y++) {            if (mMap[(int)v1.x][y] != 0) {                flag = false;                break;            }        }        if (flag) {            return true;        }    }    // Y坐标一致，逐个扫描X坐标，中间如果都是通路，那么可以直连    if (v1.y == v2.y) {        int x1 = MIN(v1.x,v2.x);        int x2 = MAX(v1.x,v2.x);        bool flag = true;        for (int x = x1 + 1; x < x2; x++) {            if (mMap[x][(int)v1.y] != 0) {                flag = false;                break;            }        }        if (flag) {            return true;        }    }    return false;}

注意这里的坐标都是地图坐标，就是第几格第几格这样的整数。

再来看下扩展函数：

voID GameScene::expandX(Vec2 v,std::vector<Vec2> &vector){    // 注意第二个参数vector是传的引用    vector.clear();    // X轴扩展到边界，如果都是空的就将扩展的点放入容器    for (int x = (int)v.x + 1; x < xCount; x++) {        if (mMap[x][(int)v.y] != 0) {            break;        }        vector.push_back(Vec2(x,(int)v.y));    }    // Y周扩展到边界，如果都是空的就将扩展的点放入容器    for (int x = (int)v.x - 1; x >= 0; x--) {        if (mMap[x][(int)v.y] != 0) {            break;        }        vector.push_back(Vec2(x,(int)v.y));    }}voID GameScene::expandY(Vec2 v,std::vector<Vec2> &vector){    vector.clear();    for (int y = (int)v.y + 1; y < yCount; y++) {        if (mMap[(int)v.x][y] != 0) {            break;        }        vector.push_back(Vec2((int)v.x,y));    }    for (int y = (int)v.y - 1; y >= 0 ; y--) {        if (mMap[(int)v.x][y] != 0) {            break;        }        vector.push_back(Vec2((int)v.x,y));    }}