连连看所属算法分析与实现

需求

（1）随机生成游戏界面；
（2）选择两个相同图案的图片，并以不超过两个转弯的连线将它们连接起来，便可以消除这对图片，每一局用户需要消除所有的图片；
（3）当没有可以消除的图案时，可以使用重置功能；
（4）选择提示功能时，游戏自动消除一对相同的图片；
（5）实现联网对战

可能存在的问题

生成界面存在的问题

1. 界面中棋子必须成对出现
2. 初始界面必须保证有解

连接时存在的问题

1. 折线次数的判断
2. 配对图片的判断
3. 连接路径上保证没有阻碍

联网同步问题

1. 同步何种数据来体现对战

构思

1. 成对问题： 可以准备两个数组分别存放匹配对，每次各取一个赋给sprite renderer。
2. 初始界面保证有解问题： 可以先随机生成一个棋盘，再用自动匹配算法进行匹配，如果无解则重新生成棋盘。
3. 折线次数问题： 可以用
4. 判断一对棋子是否可以消除时，即最小折线次数小于等于2，可以用广度优先搜索；在自动求解时，可以用深度优先搜索。
5. 图片选项配对问题：可以通过判断名称是否匹配。
6. 连线路径上无障碍：确保路径上的sprite renderer为空即可。
7. 简单实现对战，只要实现一个进度条，同步对方的完成度即可。

棋盘生成算法分析

匹配算法分析

显然这个类型的游戏，判断折线次数内匹配的算法时最核心的，其他都问题不大。下面我们来仔细分解一下这个问题。

$$方法一：分类判断法

首先我们用分类的思想类分析这个问题，这样更有助于我们深入理解。现在要求是折线数少于3次完成连接，那么我们很容易划分出三种情况：0折连，1折连，2折连。

0折连情况（即直连）
这种情况两个选中目标的横坐标或者纵坐标是一样的。只要再判断连线上没有阻碍即可。

0折连

1折连情况
此情况的两个目标横纵坐标都不能相等，相当于矩形上的对角点。所以要判断两个点是否满足1折连就只要确定另外两个对角点上的任一点同时对A和B满足0折连的情况即可。

1折连

2折连情况
向四周查找空格区域，直到“撞墙”，然后记录点C。再看点C是否满足与B 1折连情况。

2折连

$$方法二：广度优先算法
把所有满足情况的点都放在一个集合中，然后只要判断B在不在集合中就行了。具体是这样的：

1. 准备两个数组，组A是存放满足条件的点；组B是存放暂时满足情况的点。
2. 先把A放到组A。
3. 然后把所有与组A 0折连的点放到组B，然后把组B拷贝到组A再清空。折数+1
4. 重复3，直到B在组A中或者折数超过2。

$$方法三：A*寻路算法
虽然A*是解决静态网路寻路问题中求解最短路径的算法，但是其实在这里也可以有很好的应用。（不过我还没实现过，大家可以试试，可以在评论区甩代码链接分享下）

代码参考：

1.棋盘初始化（主题实现）

//初始化布局
    public void InitializeLayout()
    {
        float offset = sample.bounds.size.x;

        layout = new GameObject[Height, Width];

        //初始化空棋盘
        for (int i = 0; i < Height; i++)
            for (int j = 0; j < Width; j++)
            {
                GameObject tile = Instantiate(emptytile, new Vector3(parent.position.x + (offset * j), parent.position.y + (offset * i), 0), Quaternion.identity, parent);
                tile.name = (i * 10 + j).ToString();
                layout[i, j] = tile;
            }

        //矫正位置偏差
        if (SceneManager.GetActiveScene().name.Equals("Single"))
        {
            if (currentLevel <= 5)
                parent.position = parentPOS[currentLevel];
            else
                parent.position = parentPOS[5];
        }

        //给棋盘放上棋子
        GiveSprites();
    }
    void GiveSprites()
    {
        //实现图片的成对放置:遍历棋盘，当前tile没有精灵则贴上精灵并且成对的在棋盘随机位置放上对应精灵
        for (int i = 1; i < Height - 1; i++)
            for (int j = 1; j < Width - 1; j++)
            {
                if (layout[i, j].GetComponent<SpriteRenderer>().sprite == null)
                {
                    layout[i, j].GetComponent<SpriteRenderer>().sprite = GetRandomSprite();
                    GiveSpriteInRandomXY();
                }
            }
    }
//棋子图片随机付给没贴图的棋子，防止摆放太整齐
    void GiveSpriteInRandomXY()
    {
        int x = UnityEngine.Random.Range(100, (Height - 1) * 100);
        x /= 100;
        int y = UnityEngine.Random.Range(100, (Width - 1) * 100);
        y /= 100;

        //随机定位一个位置
        Sprite thisSprite = layout[x, y].GetComponent<SpriteRenderer>().sprite;
        //检查是否有空
        if (thisSprite == null)
            layout[x, y].GetComponent<SpriteRenderer>().sprite = GetRandomSprite();
        else if (thisSprite != null)
            GiveSpriteInRandomXY();
    }
//随机选取棋子图片
    Sprite GetRandomSprite()
    {
        Sprite s = null;
        int index = -1;
        //在s1中获取一张精灵
        if (currentName == "")
        {
            int maxrange = s1.Length * 100;
            index = UnityEngine.Random.Range(0, maxrange);
            index /= 100;
            s = s1[index];
            currentName = s.name;
        }
        //在s2中获取一张精灵
        else
        {
            string name1 = currentName;
            for (int i = 0; i < s1.Length; i++)
            {
                if (s1[i].name.Equals(name1))
                {
                    s = s1[i];
                    currentName = "";
                    break;
                }
            }
        }
        return s;
    }
//重新开始
    public void Play()
    {
        if (CurrentLevel <= 5)
        { //根据当前关卡显示棋盘大小
            Width = ReadLevelRowCol()[0];
            Height = ReadLevelRowCol()[1];
        }

        if (CurrentLevel > 5)
        {
            Width = 7;
            Height = 8;
        }

        GetComponent<GameManager>().PlayAgain();
    }
//打乱棋盘
    public void ConfuseLayout()
    {
        /*当棋盘无解时打乱棋盘*/
        remaining.Clear();
        //1.先把剩余sprite收走，存入数组
        for (int i = 1; i < Height - 1; i++)
            for (int j = 1; j < Width - 1; j++)
                if (layout[i, j].GetComponent<SpriteRenderer>().sprite != null)
                {

                    remaining.Add(layout[i, j].GetComponent<SpriteRenderer>().sprite);
                    layout[i, j].GetComponent<SpriteRenderer>().sprite = null;
                }
        //2.然后把它分发到棋盘上
        ReGive();
    }
    private void ReGive()
    {
        int x = UnityEngine.Random.Range(100, (Height - 1) * 100);
        x /= 100;
        int y = UnityEngine.Random.Range(100, (Width - 1) * 100);
        y /= 100;
        while (remaining.Count > 0)
        {
            if (layout[x, y].GetComponent<SpriteRenderer>().sprite == null)
            {
                layout[x, y].GetComponent<SpriteRenderer>().sprite = remaining[0];
                remaining.RemoveAt(0);
            }
            else
                ReGive();
        }
    }

2.判定（主体实现）

    private void Update()
    {
        SelectDetact();
    }

    void SelectDetact()
    {
        if (Input.GetMouseButtonDown(0))
        {
            position = Input.mousePosition;
            Ray ray = Camera.main.ScreenPointToRay(position);
            RaycastHit hit;
            if (Physics.Raycast(ray, out hit))
            {
                SpriteRenderer hited = hit.transform.GetComponent<SpriteRenderer>();

                //如果第一次点击则记录名字
                if (firstSelect == null)
                {
                    firstSelect = hited;

                    if (firstSelect.sprite == null)
                        firstSelect = null;
                    else    //显示年代
                    {
                        firstSelect.gameObject.GetComponent<Tile>().ShowFrame(true);
                        //记录原先的图，如果选择失败要回退
                        firstSprite = firstSelect.sprite;
                        firstSelect.sprite = layout.ShowDynasty(firstSelect.sprite.name);
                    }

                }
                else
                {
                    nextSelect = hited;
                    
                    //排除无效选择
                    if (firstSelect.sprite == null || nextSelect.sprite == null || firstSelect.transform.position==nextSelect.transform.position )
                    {
                        //选择置空
                        firstSelect.gameObject.GetComponent<Tile>().ShowFrame(false);

                        //图片回退
                        firstSelect.sprite = firstSprite;
                        
                        //移除选择记录
                        firstSelect = null;
                        nextSelect = null;
                        return;
                    }
                    //记录
                    nextSprite = nextSelect.sprite;
                    nextSelect.sprite = layout.ShowDynasty(nextSelect.sprite.name);

                    nextSelect.gameObject.GetComponent<Tile>().ShowFrame(true);
                    //判断选择对是否匹配
                    string name1 = firstSelect.sprite.name;
                    string name2 = nextSelect.sprite.name;

                    if (name1.Equals(name2) && JudgeConnection(firstSelect, nextSelect))
                        //消除
                        StartCoroutine(MatchSuccess());
                    else
                        StartCoroutine(MatchFail());
                }
            }
        }
    }

    bool JudgeConnection(SpriteRenderer a, SpriteRenderer b)
    {
        int count = 0;
        lst1.Add(a);
        while (!lst1.Contains(b) && count < 3)
        {
            foreach (SpriteRenderer s in lst1)
            {
                //0折连且路空则加入lst2
                lst2.AddRange(DirectConnect(s));
            }
            //lst2 -> lst1 并清空
            for (int i = 0; i < lst2.Count; i++)
                if (!lst1.Contains(lst2[i]))
                    lst1.Add(lst2[i]);

            lst2.Clear();
            count++;
        }

        return lst1.Contains(b) ? true : false;
    }

    List<SpriteRenderer> DirectConnect(SpriteRenderer a)
    {
        List<SpriteRenderer> temp = new List<SpriteRenderer>();
        temp.AddRange(FindDirect(Vector2.up, a));
        temp.AddRange(FindDirect(Vector2.left, a));
        temp.AddRange(FindDirect(Vector2.right, a));
        temp.AddRange(FindDirect(Vector2.down, a));

        return temp;
    }

    List<SpriteRenderer> FindDirect(Vector2 dirc, SpriteRenderer a)
    {
        SpriteRenderer start = a;
        List<SpriteRenderer> cast = new List<SpriteRenderer>();
        RaycastHit hit;
        SpriteRenderer sr;
        while (Physics.Raycast(start.transform.position, dirc, out hit))
        {
            sr = hit.transform.GetComponent<SpriteRenderer>();

            if (hit.transform.GetComponent<SpriteRenderer>().Equals(nextSelect))
            {
                cast.Add(sr);
                break;
            }
            else
            {
                if (JudgeRoad(hit.transform.GetComponent<SpriteRenderer>().sprite))
                {
                    cast.Add(sr);
                    start = sr;
                }
                else
                    break;
            }
        }

        ////把所有在A,B形成矩形范围内的点都加入waypoints以便寻路
        //foreach (SpriteRenderer s in cast)
        //{
        //    if (InArea(s, firstSelect, nextSelect))
        //        waypoints.Add(s.transform.position);
        //}

        return cast;
    }

    bool JudgeRoad(Sprite s)
    {
        if (s == null)
            return true;
        else
            return false;
    }

    /// <summary>
    /// 匹配成功动动作
    /// </summary>
    IEnumerator MatchSuccess()
    {
        //匹配成功音效
        SoundManager.instance.SetClip("success");
        yield return new WaitForSeconds(0.2f);
        if (remainingCount > 2)
        {
            remainingCount -= 2;
            if (SceneManager.GetActiveScene().name.Equals("Online"))
                owningSlider.GetComponent<Progress>().CmdMinuse();
        }
        //结算界面
        else
        {
            if (SceneManager.GetActiveScene().name.Equals("Online"))
                owningSlider.GetComponent<Progress>().CmdOver();
            else
            {
                OverPanel("win");
                if (SceneManager.GetActiveScene().name.Equals("Single"))
                    gameObject.GetComponent<LayoutInitailization>().CurrentLevel++;
            }
        }

        firstSelect.GetComponent<ParticleSystem>().Play();
        nextSelect.GetComponent<ParticleSystem>().Play();
        firstSelect.sprite = null;
        nextSelect.sprite = null;
        lst1.Clear();
        OverAction();
    }

    IEnumerator MatchFail()
    {
        //匹配失败音效
        SoundManager.instance.SetClip("fail");

        yield return new WaitForSeconds(0.2f);

        //还原图片
        firstSelect.sprite = firstSprite;
        nextSelect.sprite = nextSprite;

        lst1.Clear();
        OverAction();
    }

    void OverAction()
    {
        //选择置空
        firstSelect.gameObject.GetComponent<Tile>().ShowFrame(false);
        nextSelect.gameObject.GetComponent<Tile>().ShowFrame(false);
        firstSelect = null;
        nextSelect = null;
    }

    public void OverPanel(string v)
    {
        restartPanel.SetActive(true);
        playingButton.SetActive(false);

        image.sprite = v.Equals("fail") ? fail : win;
        SoundManager.instance.SetClip(v.Equals("fail") ? "over" : "win");

        if (changebtn[0] != null)
        {
            changebtn[0].SetActive(v.Equals("fail"));
            changebtn[1].SetActive(v.Equals("win"));
            timenow = 10000;
        }
    }

    public void PlayAgain()
    {
        //更新行列值
        countRecord = (GetComponent<LayoutInitailization>().Height - 2) * (GetComponent<LayoutInitailization>().Width - 2);
        remainingCount = countRecord;
        //更新UI
        restartPanel.SetActive(false);
        playingButton.SetActive(true);
        timenow = 51;
        time.text = "51";

        //开始倒计时
        StopCoroutine("TimeCount");
        StartCoroutine("TimeCount");

        pa.DestroyChildren();

        //布局
        layout.InitializeLayout();
    }
}

【https://github.com/jewis123/AntiqueCoin/blob/master/LinkUpScriptExample】