游戏常用算法-洗牌算法
大家好,又见面了,我是你们的朋友全栈君。
洗牌算法是一个比较常见的面试题。
一副扑克54张牌,有54!种排列方式。最佳的洗牌算法,应该能够等概率地生成这54!种结果中的一种
基于Unity的洗牌算法代码实现
抽牌洗牌
原理
这是完全合乎现实洗牌逻辑的算法。
就是抽出纸牌的最后一张随机插入到牌库中,这般抽54次就完成了对扑克牌的洗牌
复杂度
空间O(1),时间O(n^2)
优缺点
如果牌库是以一个数组描述,这种插入式的洗牌不可避免地要大量移动元素。
Fisher_Yates算法
原理
取两个列表,一个是洗牌前的序列A{1,2….54),一个用来放洗牌后的序列B,B初始为空
while A不为空
随机从A取一张牌加入B末尾
复杂度
空间O(n),时间O(n^2)
代码实现
1 List<int> list = new List<int>(pukes.pukes);//洗牌前的序列A
2 List<int> newlist = new List<int>(list.Count);//洗牌后的序列B
3 for(int i = 0 ; i < pukes.pukes.Length ; ++i)
4 {
5 int randomIndex = Random.Range(0, list.Count);
6 int r = list[randomIndex];//随机取牌
7 newlist.Add(r);
8 list.RemoveAt(randomIndex);
9 }
10 pukes.ResetPuke(newlist.ToArray());//序列B为洗牌后的结果
优缺点
算法原理清晰,但额外开辟了一个List,而且为List删除元素是不可避免地需要移动元素
通过54次生成的随机数取1/54,1/53,…1/1能等概率地生成这54!种结果中的一种
Knuth_Durstenfeld算法
Knuth 和Durstenfeld 在Fisher 等人的基础上对算法进行了改进。 每次从未处理的数据中随机取出一个数字,然后把该数字放在数组的尾部, 即数组尾部存放的是已经处理过的数字 。 这是一个原地打乱顺序的算法,算法时间复杂度也从Fisher算法的 O ( n 2 )提升到了 O ( n )。
1 for(int i = pukes.pukes.Length - 1;i>0;--i)
2 {
3 int randomIndex = Random.Range(0, i+1);
4 pukes.Swap(randomIndex, i);
5 }
是最佳的洗牌算法
Inside_Out算法
C++ stl中random_shuffle使用的就是这种算法
原理
在[0, i]之间随机一个下标j,然后用位置j的元素替换掉位置i的数字
通过54次生成的随机数取1/1,1/2,…1/54能等概率地生成这54!种结果中的一种
复杂度
空间O(1),时间O(n)
代码实现
1 public static void Shuffle(Pukes pukes)
2 {
3 int len = pukes.pukes.Length;
4 for (int i = 0; i < len; ++i)
5 {
6 int randomIndex = Random.Range(0, i + 1);
7 pukes.Swap(i, randomIndex);
8 }
9 }
random_shuffle
关于c++ stl 的random_shuffle
它的算法原理和Knuth_Durstenfeld类似
先从所有元素中选一个与位置1的元素交换,然后再从剩下的n-1个元素中选择一个放到位置2,以此类推
参考链接
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/155556.html原文链接:https://javaforall.cn
相关文章
- ICML 2022 | 游戏AI学会见招拆招,腾讯AI Lab提出「对手建模」算法框架GSCU
- 【笔记】《游戏编程算法与技巧》7-12
- 基于js原生算法+cocos游戏引擎+uni框架Cloud托管网页:开发2048小游戏域名发布版本
- 区块链游戏开发小程序游戏链改开发详细流程介绍
- leetcode-55. 跳跃游戏
- 说透游戏中常用的两种随机算法
- 小游戏与H5游戏的前世今生
- 【Unity3D】Unity 脚本 ④ ( 游戏物体 GameObject 的坐标 | 修改 游戏物体 GameObject 的本地坐标 )
- Linux上的游戏之旅:让你的游戏梦想变成现实(linux设计游戏)
- 基于Linux环境下Python开发游戏之Pygame(linuxpygame)
- 通过编写一个简单的游戏学习 C 语言
- 在Linux上体验游戏乐趣(linux上的游戏)
- 尽显英雄本色!AMD潘晓明专访:打造卓越游戏体验
- 玩转Redis,让游戏体验更精彩(游戏 redis 用法)
- 初学者的福音:游戏开发新手入门指南