艾克斯の编码者

一个伪宅级别的码畜。

连连看核心算法小分享——1

写于
更新于
大纲
  1. 1. 正文
  2. 2. 回忆时间

　　注：这篇文章我到现在也没有填第二篇的坑。数据没了重新从 Capture 里面取出来，看看舍不得，于是把这篇文章也拿回来了。权当纪念吧，以及当时和 Kalxd 的对话。

正文

　　刚忙完邀请赛，蹭了块铜。刚才在逛别人博客的时候看别人的文章，突然心血来潮想记一些东西。

　　连连看是我学HGE做的第一个小游戏，素材用的是QQ的。时间大概是去年国庆吧。好吧，废话不多说，就讲讲连连看怎么找到能消的两块吧。

　　首先来回顾一下消方块的规则，一共有三种可能性：

  1. 直线消除（包括水平或者垂直）
  2. 一个拐角消除
  3. 两个拐角消除

　　嗯，接下去我们就针对每种可能性开始写代码。

　　首先讲讲一些定义：

　　座标结构体，这个结构体包含了x、y的值以及一些座标中常用的函数。

/**
 * @brief 地图座标结构体
 *
 * 地图座标结构体，包含x轴值、y轴值
 * 以及一些操作函数。
 */
struct CoorType {
    int x;                                          ///< x轴
    int y;                                          ///< y轴

    /**
     * 重载构造函数
     * 将x、y值各初始化为-1
     */
    CoorType()
    {
        x = -1, y = -1;
    }

    /**
     * 构造函数重载
     * 将x、y各赋值为b、a
     * @param a 将要赋值的y轴数值
     * @param b 将要赋值的x轴数值
     */
    CoorType(int a, int b)
    {
        y = a, x = b;
    }

    /**
     * 设置座标
     * 将x、y各赋值为b、a
     * @param a 将要赋值的y轴数值
     * @param b 将要赋值的x轴数值
     */
    void Set(int a, int b)
    {
        y = a, x = b;
    }

    /**
     * 运算符"+="重载
     * 将此座标与另一座标相加
     * @param &a 另一座标
     * @return 返回结果座标值
     */
    CoorType & operator += (const CoorType &a)
    {
        y += a.y, x += a.x;
        return *this;
    }

    /**
     * 重载运算符"!="
     * 判断与另一座标是否表示同一个值
     * @param &a 另一座标
     * @return 返回布尔类型表示是否相等
     */
    bool operator != (const CoorType &a)
    {
        if(y != a.y || x != a.x) return false;
        else return true;
    }

    /**
     * 判断此座标是否合法
     * 若出界则不合法
     * @return 返回布尔类型表示是否合法
     */
    bool isIll()
    {
        if(y >= 0 && x >= 0 && y < MAP_HEIGHT && x < MAP_WIDTH) return true;
        else return false;
    }
};

　　然后是关于地图数组的定义：

int Map[MAP_HEIGHT][MAP_WIDTH];

　　接着是路径结构体：

/**
 * @brief 路线结构体
 *
 * 合法路线结构体
 * 储存最多四个点（起点终点和两个转折点）
 */
struct PointPath {
    bool bExist;                                    ///< 是否有路径
    int Num;                                        ///< 驻点个数
    CoorType Points[4];                             ///< 各驻点
};

　　接着可以正式开始了。首先我们来想一下，哪些条件各符合上面三种情况的哪一种。对于一条直线的，显然是x相等或者y相等；对于有一个转折点的话，我们只需要判断起点横向画线（或者纵向），然后终点纵向画线（或者横向），然后从起点到交点以及从交点到终点各可行不；对于两个转折点，其中一个转折点的x或者y跟起点的x或者y相等，另一个转折点跟终点的x或者y相等。于是这两个转折点就根据这样的性质进行枚举。因为连连看的地图比较小，所以这种O(n^2)的时间复杂度不碍事。

　　为了方便，我们写一个 Abled(CoorType, CoorType, bool, bool); 函数来进行判断两个点（当然两点是在同一直线上的）是否有同路（即中间没有东西挡着）。我们先放着这个Abled不管，先实现寻路过程吧。

　　我是用一个CMapSearch类来实现的，声明如下：

/**
 * @brief 地图搜索类
 *
 * 根据指定地图搜索出各合法路径。
 */
class CMapSearch
{
private:
    int Map[MAP_HEIGHT][MAP_WIDTH];                                             ///< 地图数据矩阵
    PointPath dis[MAP_HEIGHT][MAP_WIDTH][MAP_HEIGHT][MAP_WIDTH];                ///< 路径数组
    STLMap grap;                                                                ///< STL映射
    CoorType dir[4];                                                            ///< 常量座标增量
    PointPath Hint;                                                             ///< 提示时用的合法路径

    /**
     * @brief 两点寻径
     *
     * 对(x1, y1)和(x2, y2)进行寻径
     * @param x1 第一个座标的x轴
     * @param y1 第一个座标的y轴
     * @param x2 第二个座标的x轴
     * @param y2 第二个座标的y轴
     * @return 返回一个路线结构体的值，若不存在路径，则结构体的bExist为假
     * @see Abled
     */
    PointPath DoSearch(int y1, int x1, int y2, int x2);

public:
    /**
     * @brief 构造函数
     *
     * @param _Map[][Map_Width] 地图矩阵
     */
    CMapSearch(int _Map[][MAP_WIDTH]);

    /**
     * @brief 析构函数
     */
    ~CMapSearch(void);

    /**
     * @brief 载入地图
     * 从矩阵中载入地图到对象
     *
     * @param _Map[][Map_Width] 地图矩阵
     */
    void LoadMap(int _Map[][MAP_WIDTH]);

    /**
     * @brief 搜索地图
     * 对整个地图进行搜索每两个相同方块之间的路径
     *
     * @return 如果存在至少一条路径则返回真，否则为假，用于是否重列
     * @see CreateSTLMap
     * @see DoSearch
     */
    bool Search();

    /**
     * @brief 创建map映射
     * 创建一个方块ID的映射，对每个ID创建一条的该ID的方块在地图中的各座标的链表
     */
    void CreateSTLMap();

    /**
     * @brief 判断是否有障碍
     * 对于a、b两座标（在同一直线）进行判断期间是否有方块障碍而导致不能连线
     *
     * @param a 座标a（头座标）
     * @param b 座标b（尾座标）
     * @param head 若包括头座标则为true，否则为false
     * @param tail 若包括尾座标则为true，否则为false
     * @return 若有障碍则返回false，否则为true
     */
    bool Abled(CoorType a, CoorType b, bool head = false, bool tail = false);

    /**
     * @brief 得到路径
     * 得到两个座标的连线具体路径
     *
     * @param y1 第一个座标的y轴
     * @param x1 第一个座标的x轴
     * @param y2 第二个座标的y轴
     * @param x2 第二个座标的x轴
     * @return 返回一个路线结构体，表示该两个座标直接的路线
     */
    PointPath GetPath(int y1, int x1, int y2, int x2);

    /**
     * @brief 得到提示路径
     * 得到一条提示的路径的相应两个方块
     *
     * @param &a 接受第一个方块ID的变量
     * @param &b 接受第二个方块ID的变量
     */
    void GetRandomHint(int &a, int &b);
};

　　然后我这个分享里所讲的算法就是DoSearch和Abled函数了，因为其它函数就是用于“提示”道具的。在DoSearch中我们先定义两个临时变量，一个是返回值（一个PointPath），四个座标变量：

PointPath ans;
CoorType a(y1, x1), b(y2, x2), c, d;

　　其中a、b表示起点和终点，c、d表示可能用到的两个转折点。

　　首先我们先来判断直线情况吧，这种情况比较简单：

//如果是直线
if(a.x == b.x || a.y == b.y)
{
    if(Abled(a, b, true, true))
    {
        ans.bExist = true;
        ans.Num = 2;
        ans.Points[0] = a, ans.Points[1] = b;
        return ans;
    }
}

　　对于这种情况，我们只需直接判断a、b直接有没有通路就好，如果有通路我们就将结果记录到ans中并返回即可。

　　而有一个转折点、两个转折点的情况以及Abled函数将在下一篇文章中小分享一下。

回忆时间

　　然后下面就是在这篇文章里面我跟 Kalxd 的对话了，想想现在真是沧海桑田啊。

　　CSS 样式早已经不在了，截图里面是一篇白板

评论回忆