文章目录
一、如何实现乱序的随机排序，而不占用空间
（1）想法来源
最近看了游戏开发精粹1的可预测随机数，感觉有点用处，就记录下来，其实没啥大用
（2）算法作用
在资源有限的环境下，在游戏空间中给出无限空间的幻觉
（3）效果展示
- 参数说明
1）seed 种子，seed is a seed value between 1 and the maximum long integer value allowed by ANSI.
2）max 序列的最大值
3）runs 展示序列的多少个元素
Prandgen <seed> <n_max> <n_runs>
（4）代码
因为是老代码，所以我用cmake重新简单改造了下
-
目录
-
代码
1）cmakelists.txt
cmake_minimum_required(VERSION 2.8)
PROJECT(prand_1)
SET(SRC_LIST main.cpp Prandgen.cpp Prandgen.h)
ADD_EXECUTABLE(prand ${SRC_LIST})
2）main.cpp
#include <stdlib.h>
#include <string.h>
#include "Prandgen.h"
using namespace std;
CPseudorandom * rand_gen = NULL;
int main (int argc, char * argv[])
{
uint32_t lSeed, lMax, lRand, i;
int32_t nPad, nPerLine, nRuns, nLinePos;
// Expect the seed, maximum and runs as arguments
if (argc < 4)
{
printf("\nPrandgen <seed> <n_max> <n_runs>\n");
return -1;
}
lSeed = atol(argv[1]);//把字符串改成长整型
//is a seed value between 1 and the maximum long integer value allowed by ANSI.
lMax = atol(argv[2]);
nPad = strlen(argv[2]); // The width of field
nRuns = atoi(argv[3]); //argument determines the number of pseudorandom numbers to generate.
rand_gen = new CPseudorandom(); // Create a new random number object
if(!rand_gen) return -1;
rand_gen->SRand(lSeed); // Initialise it with the seed value
nPerLine = (79-nPad) / nPad; // Calculate number of numbers per line
nLinePos = 0;
while (nRuns > 0)
{
if (nLinePos > nPerLine)
{
nLinePos = 0;
printf("\n");
}
lRand = rand_gen->Rand(lMax);//80
printf("%ld",lRand);
if (lRand == 0) lRand = 1;
for (i = lRand; i < lMax; i = (i * 10)) printf(" ");
nRuns--;
nLinePos++;
}
delete rand_gen; // Get rid of the object tidily
}
3）Prandgen.cpp
#include "Prandgen.h"
CPseudorandom::CPseudorandom()
{
m_nLSeed = 0;
m_nLGen1 = 0;
m_nLGen2 = 0;
}
CPseudorandom::~CPseudorandom()
{
}
uint32_t CPseudorandom::Rand(uint32_t lMax)
{
uint32_t lNewSeed = this->m_nLSeed;//5
uint32_t lReturn = 0;
lNewSeed = (this->m_nLGen1 * lNewSeed) + this->m_nLGen2;// 3719*3.5 = 3719*(lSeed+0.5)
// Use modulo operator to ensure < ulMax
this->m_nLSeed = lNewSeed; //3719*(lSeed+0.5)
lReturn = this->m_nLSeed % lMax;//3719*(lSeed+0.5) %80
//printf("lReturn_1:%d\n",lReturn);
if (lReturn < 1) lReturn = lReturn * -1; // Keep it positive
//printf("lReturn_2:%d\n",lReturn);
return lReturn;
}
void CPseudorandom::SRand(uint32_t lSeed)
{
this->m_nLSeed = lSeed;
// Pick two large integers such that
// one is double the other
this->m_nLGen2 = 3852;
this->m_nLGen1 = (m_nLGen2 / 2);
}
4）Prandgen.h
#ifndef _PRANDGEN_H__
#define _PRANDGEN_H__
#include <stdint.h>
#include <stdio.h>
class CPseudorandom
{
public:
CPseudorandom();
~CPseudorandom();
uint32_t Rand(uint32_t lMax);
void SRand(uint32_t lSeed);
private:
uint32_t m_nLSeed;
uint32_t m_nLGen1;
uint32_t m_nLGen2;
};
#endif
二、rand()和srand()的使用
rand(）产生伪随机数，需要srand()来设置一个种子，通常用系统时间
0）补充背景说明
（1）rand()函数用来产生随机数，但是，rand()的内部实现是用线性同余法实现的，是伪随机数，由于周期较长，因此在一定范围内可以看成是随机的。rand()会返回一个范围在0到RAND_MAX（32767）之间的伪随机数（整数）。
（2）在调用rand()函数之前，可以使用srand()函数设置随机数种子，如果没有设置随机数种子，rand()函数在调用时，自动设计随机数种子为1。随机种子相同，每次产生的随机数也会相同。
（3）rand()函数需要的头文件是：<stdlib.h>
（4）使用rand()函数产生0-99以内的随机整数：int number1 = rand() % 100;
（5）因此，如要产生[m,n]范围内的随机数num，可用：
int num=rand()%(n-m+1)+m;
其中的rand()%(n-m+1)+m算是一个公式，记录一下方便以后查阅。
1）效果展示
2）代码使用举例
#include <stdlib.h>
#include <string.h>
#include <time.h>
using namespace std;
int main (int argc, char * argv[])
{
srand(time(NULL));//使用系统时间产生随机数
for (int i = 0; i < 10; i++)
{
printf("%d\t", rand());
}
printf("\n");
}
三、游戏中的随机算法简单分类(主指伪随机)
1）出现原因
真随机对于玩家来说有些不近人情，例如在某些抽卡游戏中，如果是真随机的话，有些玩家运气不好，可能抽上百次也抽不到SSR。为了照顾玩家的感受，引入了伪随机。
2）分类
（1）（Pseudo Random Distribution）PRD
-
说明
通常用于游戏中计算概率，为了平衡一些极端情况对游戏体验的影响（例如Dota中虚空先知有百分之25的概率免疫所有伤害，如果有玩家运气特别好，一个丝血的JB脸，就是死不掉，会很让对面崩溃），所以设计师引便了伪随机：例如第一次JB脸被攻击时，不是有25%的概率躲掉，第二次是10%，如果这次没躲掉，那么下次概率躲掉的概率变为20%，再变为30%。个人认为可能阴阳师抽卡也是伪随机 -
背景
PRD算法诞生与《魔兽争霸3》，可以说其诞生就是为了解决游戏中暴击概率所存在的问题。 现在其广泛应于与Dota2、LoL等MOBA游戏和其它竞技性较高的游戏暴击概率运算中。 -
算法
为了便于理解，这里直接给出一个具体例子：
（1）设我们当前玩家暴击率还是0.3，那么对于 PRD算法，此时的 C = 0.3此时第一次攻击时的实际暴击率，即 P(1) = 0.3 * 1 = 0.3，
（2）若没有暴击，则 N + 1，N = 2此时第二次攻击时的实际暴击率，即
P(2) = 0.3 * 2 = 0.6，
（3）若没有暴击，则 N + 1，N = 3此时第三次攻击时的实际暴击率，即
P(3) = 0.3 * 3 = 0.9，
此时对于大部分玩家来说这第三次攻击就会产暴击了，但如果玩家是个非酋，这次仍没有暴击，没关系，N + 1，N = 4
（3）第四次攻击，
P(4) = 0.3 * 4 = 1.2 >= 1，
这一次是一定会暴击的。可以看到，使用 PRD 算法，对于攻击是否会暴击这?问题，仍然是存在着随机性即玩家的运气因素的，但即使是运气最差的玩家，仍然也会在第四次攻击时产生暴击，因此PRD算法可以在保存随机性的同时，减少玩家运气因素对游戏结果的影响。上面的例子展示了PRD算法会避免玩家一直不出现暴击的情况，同样PRD算法也会避免玩家一直出现暴击的情况。
（2）洗牌算法
- 说明
例如音乐播放器中常见的“随机播放”，如果是真随机的话，有可能出现一首歌你永远都听不到，或者不停的播放同一首歌（极端情况）。所以播放器的做法是像洗牌一样把这些歌打乱顺序，然后按顺序播放这个乱序数组
（）补充计算机产生随机数的方法：赝随机数算法（Pseudo-Random Number Generator，简称PRNG）
- 说明
由于计算机中只有确定的0和1，所以要产生3真正的随机数是不可能的，通过随机数算法得到的只是看起来像是，即如果输入随机数算法的值是一样的，那么得到的随机数也是一样的。
