[游戏开发]Unity随机网格中空位置_二叉树

这篇具有很好参考价值的文章主要介绍了[游戏开发]Unity随机网格中空位置_二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0. 前言

在做个小游戏,需要随机在网格的空位置上生成方块,在随机的时候,感觉简单随机的方式效率很低而且不稳定。就在想有没有比较快的方式能够随机到想要的位置。最后是用二叉树记录下权重并进行随机,很稳定而且效率还不错。所以写个文章记录一下,以供参考。

1. 简单随机

在一个固定的网格中随机一个空位置。比如说在一个20*20的棋盘上,上面有若干个棋子,现在要生成新的棋子在空的位置上。最简单的方式就是在矩形内随机一个坐标,然后判断该位置是否有棋子,没有的话再随机一次,如下。

public Vector2Int RandomPos()
{
    int x, y;
    do
    {
        x = Random.Range(0, bound.width);
        y = Random.Range(0, bound.height);
    }
    while (flagMap[x, y]);
    return new Vector2Int(x, y);
}

这样简单随机容易在空位比较少的时候随机很久才能随机到空位,比如只剩下一个位置,那20*20的格子,就是1/400的概率随机到,那就需要重复很多次了。而且有安全问题,比如现在棋子都下满了没位置生成时调用就会无限循环。

稍微改进方法的是,加一个外额随机次数限制,比如说最多随机个1000次,如果没有,就当没有空位。解决死循环、随机太多次的问题,会跟推荐一点。总的来说:

优点:编写简单,运行较快,特别是地图大,空位多的时候随机非常快。
缺点:空位少时,运行时间长,容易漏掉某个位置随机不到,不稳定

2. 可用位置内随机

除了直接随机坐标的方式,还有另一种简单方法,就是预先计算一下可用位置,然后在可用位置内随机。

public Vector2Int RandomPos()
{
    int w = flagMap.GetLength(0);
    int h = flagMap.GetLength(1);

    // 计算所有可能
    tempPos.Clear();
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            if (!flagMap[i, j])
            {
                tempPos.Add(new Vector2Int(i, j));
            }
        }
    }

    // 随机一个
    if (tempPos.Count <= 0)
    {
        return Vector2Int.zero;
    }
    else
    {
        int index = Random.Range(0, tempPos.Count);
        return tempPos[index];
    }
}

这种方法就是非常稳定,如果有空位毕竟可以随机到,而且不会有脸黑多次随机的问题。带来的额外问题就是,计算并记录所有位置需要额外的开销。

稍微改进方法是,在放置或者移除棋子的时候预先保存可用位置计数n,[0,n)之间随机出m,然后再依次找到第m个空位,即为随机位置。这样就可以减少检查和缓存的数据量。那么,这种方法的话:

优点:稳定,不会遗漏空位。地图小的时候,而且对空位要求严格的时候还是挺好用的。
缺点:效率低,特别是地图大的话,要计算一下所有的位置就比较麻烦了。

3. 二叉树权重随机

终于到了今天要讲的这个方法了,是按照分区域随机的思路想出来的。

(1)分区域随机

比如说我们可以先将网格分成均分成4个部分,然后随机一个位置,这个小区域也可以再划分为4个区域,直到剩下4个位置,就可以在这4个位置中随机一个,如果没有空位了。则重新跳回上一层区域再随机其他位置,如此重复。如下图(8*8)可供参考。
[游戏开发]Unity随机网格中空位置_二叉树,游戏开发,unity,c#,游戏
分层的最主要目的还是为了,在保证能够随机出空位的前提下,减少每次计算的量,不用每次都将地图从头开始判断是否可用。

(2)设置权重均衡概率

那么这个时候,聪明的小伙子就会发现这个方法的问题,概率不随机。比如说,如下图(4*4),我们在随机到左上区域的概率是1/4,但里面只有两个空位,那么这个时候这两个空位就会享受这1/8的概率。而右下的4空位分别只有1/16的概率。
[游戏开发]Unity随机网格中空位置_二叉树,游戏开发,unity,c#,游戏
解决问题的方法,是计算并缓存一下权重,比如说左上只有两个空位,随机时享有2的权重,右下享有4的权重。如何比较好的计算并保存这个权重呢?刚刚随机区域的时候,有没有感觉很像深度优先搜索。这也让我联想到树结构,就打算用二叉树来做这个权重的缓存,而且二叉树有个好处就是非此即彼,每次只要判断一下做或者右即可。

(3)二叉树缓存权重

我们先考虑将这个数组降到1维,因为一维的话就只有左右之分, 更符合二叉树。我们编个号,可以随机的位置权重为1,不可以随机的位置权重为0。如下图。
[游戏开发]Unity随机网格中空位置_二叉树,游戏开发,unity,c#,游戏
那么我们就就可以得到如下的二叉树,蓝色为权重。
[游戏开发]Unity随机网格中空位置_二叉树,游戏开发,unity,c#,游戏

这种情况下,需要缓存的数据也不会太多,毕竟是取对数的,越往上消减得越快,缓存的数据在格子数量的2倍以内。而且为了存储和索引更加简单,我们用可以数组(记为weight)存一下这个二叉树。刚刚举的例子是一个16格的网格,意外(故意)刚好是2的指数倍,如果是3*3共9格,那就需要把后面的10-15权重置零就可以了。

另外是修改权重也会比较简单,每次放置或者移除棋子时,往上更改权重即可,如下。

public void SetEnable(int x, int y, bool enable)
{
    int index = Pos2Index(x, y);
    if (index < 0 &&
        index >= weight[layerCount - 1].Length)
    {
        throw new System.Exception("x,y is out of Length");
    }
    int value = enable ? 1 : 0;
    SetWeight(index, value);
}

private void SetWeight(int index, int value)
{
    int changeValue = value - weight[layerCount - 1][index];
    if (changeValue != 0)
    {
        for (int layer = layerCount - 1; layer >= 0; layer--)
        {
            weight[layer][index] += changeValue;
            index = index >> 1; // =index /2;
            index = index > 0 ? index : 0;
        }
    }
}

private int Pos2Index(int x, int y)
{
    int i = x - gridBound.x;
    int j = y - gridBound.y;
    return i * gridBound.height + j;
}

其中,SetEnable 用于设置改位置是否可以被随机到,SetWeight 用于设置权重,Pos2Index用于转换坐标到一维数组的坐标。

(4)利用二叉树随机

随机的时候。首先是[0,13)内随机一个数,假设是9好了,大于或等于5,所以可以判断是右边部分。对于下一个节点判断是,9 - 5=4,大于或等于4,所以是判断为左边。依次不断进行到网格最底部就可以了,还是挺好理解的。那么代码如下。

public Vector2Int RandomPos()
{
    if (IsEmpty)
    {
        return Vector2Int.zero;
    }
    else
    {
        int index = 0;
        int value = Random.Range(0, weight[0][0]);
        for (int layer = 1; layer < layerCount; layer++)
        {
            if (value >= weight[layer][index])
            {
                value -= weight[layer][index];
                index = (index << 1) + 1;// i*2+1
            }
            else
            {
                index = index << 1;
            }
        }
        return Index2Pos(index);
    }
}

好咯,那么到现在,我们就可以又快又稳定的随机到这个点了。

(5)优缺点

优点:随机稳定,效率高。如果有空位一定能够随机到
缺点:额外内存开销,设置可否随机状态时有额外计算开销。

不适合地图比较大的情况,不过通常要严格随机位置的,应该不会区域太大,围棋棋盘也就19*19,看起来也挺密密麻麻的了。

4. 测试对比

简单测试一下,这个【3.二叉树权重随机】,和【1. 简单随机】比较一下。
在20*20的大小内,有一半已经有棋子的情况下,随机200次的时间开销。

RectInt rect = new RectInt(0, 0, 20, 20);
int repeatTime = 1000;
int setPosCount = 200;
int randomCount = 200;

RandomGrid grid = new RandomGrid(rect);
for (int j = 0; j < setPosCount; j++)
{
    Vector2Int pos = grid.RandomPos();
    grid.SetEnable(pos, false);
}
long time = System.DateTime.Now.Ticks;
for (int i = 0; i < repeatTime; i++)
{
    for (int j = 0; j < randomCount; j++)
    {
        grid.RandomPos();
    }
}
DebugU.Log("time1:" + (System.DateTime.Now.Ticks - time));

RandomGrid2 grid2 = new RandomGrid2(rect);
for (int j = 0; j < setPosCount; j++)
{
    Vector2Int pos = grid2.RandomPos();
    grid2.SetEnable(pos, false);
}
time = System.DateTime.Now.Ticks;
for (int i = 0; i < repeatTime; i++)
{
    for (int j = 0; j < randomCount; j++)
    {
        grid2.RandomPos();
    }
}
DebugU.Log("time2:" + (System.DateTime.Now.Ticks - time));
time1:179407
time2:259427

time1为二叉树权重随机的时间,time1比time2要快挺多,说明二叉树权重随机的方法效率还不错的,下面是网格内有不同数空位情况下,两种花费时间。

// 380个空位 / 95% 为空位 
time1:149498
time2:89699
// 300个空位 / 75% 为空位
time1:179401
time2:149499
// 200个空位 / 50% 为空位
time1:179407
time2:259427
// 100个空位 / 25% 为空位
time1:129564
time2:358803
// 20个空位 / 5% 为空位 
time1:129571
time2:2178037

比较一下,也可以发现二叉树权重随机会更加稳定一点,而且效率也还不错。其实最重要的是能够确保,有空位的时候能够随机到该位置。

4. 结束咯

在实际用二叉树权重随机的方法的时候,有个问题,比如我想要随机出一个3*3的小空位,而不是单独一个点,那么这个时候就没办法直接随机了。另外,比如需要限定点在第一第二行内,这种带范围的随机,也不好处理。

那么这个时候,我是用了一个临时权重TempWeight,原本的权重Weight,需要加上这个值才是最后的权重值。那么在随机的点不是3*3的空位(或者其他条件)时,在该位置TempWeight置为-1,那么和Weight相加为0,即权重为0,不会再随机到。然后我们再重复操作,直到找到符合要求的点。完成之后就可以重置一下TempWeight,不会影响下次操作。当然,如果下次随机的条件也是相同的,那还是可以先暂时保留TempWeight,以提高随机小卢。

ok,那就结束咯。

突发奇想的一个方法,希望能够各位有所帮助。文章来源地址https://www.toymoban.com/news/detail-531736.html

到了这里,关于[游戏开发]Unity随机网格中空位置_二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 空间划分算法优化碰撞检测研究(网格划分、四叉树\八叉树、层次包围盒树BVH)Unity C#实现

    目录 前言 一、Demo说明 二、暴力法  三、网格划分 实测 分析 四、四叉树 四叉树的构建细节  实测 五、松散四叉树 实测 八叉树 六、层次包围盒树(BVH) 包围盒 AABB树 AABB树构建细节 实测 总结   碰撞检测是一个非常经典的问题。虽然现在我们都有物理引擎提供的便捷接口

    2023年04月11日
    浏览(84)
  • Unity--随机生成游戏对象

    在脚本中声明数组 RandomObjects 用于保存生成对象的类型,在project文件中拖入对象。 先将脚本拖到一个对象上,然后点击检查器-覆盖-应用到全部,这样将使所有预制件都拥有该属性。

    2024年02月15日
    浏览(42)
  • 【实现100个unity游戏之20】制作一个2d开放世界游戏,TileMap+柏林噪声生成随机地图(附源码)

    我的上一篇文章介绍了TileMap的使用,主要是为我这篇做一个铺垫,看过上一篇文章的人,应该已经很好的理解TileMap的使用了,这里我就不需要过多的解释一些繁琐而基础的知识了,省去很多时间。所有没看过上一篇文章的小伙伴我强烈建议先去看看:

    2024年01月20日
    浏览(52)
  • 【用unity实现100个游戏之4】手搓一个网格放置功能,及装修建造种植功能(2d3d通用,附源码)

    参考原视频链接 【视频】:https://www.youtube.com/watch?v=l0emsAHIBjU 注意 :本文为学习笔记记录,推荐支持原作者,去看原视频自己手敲代码理解更加深入

    2024年02月13日
    浏览(43)
  • Unity3D PVP游戏位置同步算法优化详解

    在Unity3D中,PVP(Player versus Player)游戏的位置同步是一项重要的技术,它决定了游戏中玩家之间的互动体验。本文将详细介绍Unity3D PVP游戏位置同步算法的优化方法,并给出相应的技术详解和代码实现。 对啦!这里有个游戏开发交流小组里面聚集了一帮热爱学习游戏的零基础

    2024年01月16日
    浏览(63)
  • 开发过程中空指针异常如何规避?

    if(status.equals(SUCCESS)){ } 这个时候 status 可能为 null 造成空指针异常,应该把常量放前面,就能避免空指针异常。 if(SUCCESS.equals(status)){ } 这个应该在各种开发规范里面都会提到,也是最基础的。 在对象初始化的时候给它一个默认值或者默认构造实现,如: User user = new User(); S

    2024年02月03日
    浏览(42)
  • 基于网格搜索的随机森林回归算法Python实现

            随机森林回归算法的应用领域很广,可用于市场销售预测、客户细分、商品推荐等领域,也可应用于气候模型预测、土地利用分析、水资源管理等环境领域问题。其算法的Python实现涉及到多参数调优问题,本文使用了网格搜索法,以MSE作为评价指标,选取最佳MSE的参

    2024年02月06日
    浏览(50)
  • Unity游戏开发之游戏动画(Unity动画系统)

    Unity动画系统分为 动画片段 Animation Clip: 动画资源,与模型无关 动画状态机 Animator Controller:帮助我们跟踪当前动画的播放状态,并且根据设置觉得如何切换动画片段 动画组件 Animator Component:玩家角色需要播放动画功能时,需要动画组件,将游戏对象需要的动画状态机(以

    2024年02月13日
    浏览(58)
  • Unity开发笔记:截取指定位置含有UI的场景截图并输出

    学习记录整理,自用,也希望能帮助到有相同需求的人。 如果直接截全图: 截取指定位置含有UI的场景截图: 例如这种情况下只想要中间的: UI所在的Canvas设置为RenderMode.ScreenSpaceCamera并挂载相机,然后设置该相机的渲染RenderTexture并开始render,注意这里渲染是从屏幕中心扩展

    2024年02月13日
    浏览(39)
  • Unity游戏开发之游戏存档方式

    目录 1.Unity自带存储方式PlayerPrefs 2.XML存储方式 3.Json类型存储方式 1.Unity的序列化问题 2.Unity中支持序列化的类 3.Unity中Json的使用方法  4.SQLite 1.SQLite的一些基础(简单介绍,不会深入讲解) 2.在Unity中使用SQLite 3.SQLite的优劣 结语         属于unity自带的数据存储方法,其形式

    2024年02月06日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包