【游戏开发答疑】马里奥派对选面积大作战玩法的功能实现(Unity | 算法 | 四邻域 | 连通块 | 面积比例分割)

【游戏开发答疑】马里奥派对选面积大作战玩法的功能实现(Unity | 算法 | 四邻域 | 连通块 | 面积比例分割),第1张

本文运行效果如下

文章目录
      • 一、前言
      • 二、实现方案
        • 1、构造二维数组
        • 2、顺序填充颜色
        • 3、交换格子颜色
        • 4、计算连通块个数(四邻域连通)
        • 5、运行起来
      • 三、工程源码
      • 四、完毕

一、前言

嗨,大家好,我是新发。
有同学私信问了我一个问题,如下

游戏视频如下

【超级马力欧派对】(四十六)选面积大作战

我以第一回合为例,也就是把5*9的方格分成9:11:12:13的面积,并且确保面积是四邻域连通的,什么是四邻域呢?一个格子的上下左右紧邻的格子就是它的四邻域。

好了,下面讲一下实现方案。

二、实现方案 1、构造二维数组

为了演示,我先做了一个简单的UI界面,如下,下面是一个5*9的方格阵列,

如果对应成代码,它就是一个二维数组,像这样子

/// 
/// 行数
/// 
private const int ROW_CNT = 5;
/// 
/// 列数
/// 
private const int COL_CNT = 9;

/// 
/// 格子二维数组
/// 
public Image[,] grid = new Image[ROW_CNT, COL_CNT];
2、顺序填充颜色

我们定义四种颜色,

把格子按9:11:12:13的比例顺序填充不同的颜色,像这样子

对应成代码就是这样子:

// 划分成4种颜色,9个color1, 11个color2, 12个color3, 13个color4
for (int i = 0; i < ROW_CNT; ++i)
  {
      for (int j = 0; j < COL_CNT; ++j)
      {
          var index = i * COL_CNT + j;
          if (index < 9)
          {
              grid[i, j].color = color1;
          }
          else if (index < 9 + 11)
          {
              grid[i, j].color = color2;
          }
          else if (index < 9 + 11 + 12)
          {
              grid[i, j].color = color3;
          }
          else
          {
              grid[i, j].color = color4;
          }
      }
  }
3、交换格子颜色

对某两个格子进行交换,写成代码是这样子,

int i1 = Random.Range(0, ROW_CNT);
int j1 = Random.Range(0, COL_CNT);

int i2 = Random.Range(0, ROW_CNT);
int j2 = Random.Range(0, COL_CNT);

var tmpColor = grid[i1, j1].color;
grid[i1, j1].color = grid[i2, j2].color;
grid[i2, j2].color = tmpColor;

交换后有两种结果:
情况1: 没有破坏连通性,依然是4个大的连通块:

情况2: 破坏了原有的连通性,像这样子,出现了7个连通块:

如果破坏了原来的连通性,这次交换就要作废。

那,我们如何检测有没有破坏原来的连通性呢?这个问题等效于:我们如何检查连通块的个数呢?只要确保连通块的个数是4,就说明没有破坏原来的连通性。

4、计算连通块个数(四邻域连通)

这里我用的是深度优先遍历,通过递归来实现。

首先我们定义格子的状态值:01,如果被遍历过,则标记为1;我们可以定义一个二维数组来存储格子状态:

/// 
/// 格子状态,遍历过的标记为为1,否则为0
/// 
int[,] ergodic = new int[ROW_CNT, COL_CNT];

为了存储四邻域连通的个数,我们再定义一个变量

/// 
/// 统计连通块个数
/// 
int connectGroupCnt = 0;

然后从[0, 0]的位置开始,如果发现格子状态为0,则让connectGroupCnt自增1,把格子标记为1,然后遍历格子的上下左右邻域的格子,如果发现颜色与当前格子相同,则标记为1,否则不 *** 作,以此类推,直到全部遍历完毕。
为了方便大家对这个过程有个更直观的感受,我特意做了个动态图,如下

对应成代码如下

/// 
/// 检测连通性
/// 
/// 
bool CheckContinuous()
{
    int i = 0;
    connectGroupCnt = 0;
    ergodic = new int[ROW_CNT, COL_CNT];

    while (i < ROW_CNT)
    {
        int j = 0;
        while (j < COL_CNT)
        {
            Dfs(i, j, grid);
            j++;
        }
        i++;
    }

    // 如果四连通块超过4个,则说明产生了不连续颜色块
    if (connectGroupCnt > 4)
        return false;

    return true;
}


/// 
/// 深度优先,递归调用,计算连通块数量
/// 
void Dfs(int x, int y, Image[,] grid)
{
    if (x < 0 || y < 0 || x == ROW_CNT || y == COL_CNT)
    {
        return;
    }
    if (ergodic[x, y] == 0)
    {
        ergodic[x, y] = 1;
        connectGroupCnt++;

    }
    // 右
    if (y < COL_CNT - 1 && grid[x, y].color == grid[x, y + 1].color && ergodic[x, y + 1] == 0)
    {
        ergodic[x, y + 1] = 1;
        Dfs(x, y + 1, grid);
    }
    // 左
    if (y > 0 && grid[x, y].color == grid[x, y - 1].color && ergodic[x, y - 1] == 0)
    {
        ergodic[x, y - 1] = 1;
        Dfs(x, y - 1, grid);
    }
    // 下
    if (x < ROW_CNT - 1 && grid[x, y].color == grid[x + 1, y].color && ergodic[x + 1, y] == 0)
    {
        ergodic[x + 1, y] = 1;
        Dfs(x + 1, y, grid);
    }
    // 上
    if (x > 0 && grid[x, y].color == grid[x - 1, y].color && ergodic[x - 1, y] == 0)
    {
        ergodic[x - 1, y] = 1;
        Dfs(x - 1, y, grid);
    }
}
5、运行起来

现在,我们弄个协程,让它快速执行变化,看下效果吧~

三、工程源码

本文工程源码我以上传到GitCode,感兴趣的同学可自行下载。
地址:https://gitcode.net/linxinfa/GridBlockGame

注:完整代码见Assets/Scripts/Main.cs脚本

四、完毕

本文我的的实现方案只是我抽空写的一个简单的算法,并没有考虑最优解,大家可以思考一下其他更好的解决办法。

好了,我是林新发,https://blog.csdn.net/linxinfa
一个在小公司默默奋斗的Unity开发者,希望可以帮助更多想学Unity的人,共勉~

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1295769.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存