以伪随机顺序迭代列表而不存储混洗列表

Question

在游戏中,我们使用一种称为" 颜色选择 " 的技术来选择单位.

这意味着每个可见单元都具有独特的颜色.

以下是为颜色拾取绘制的场景示例:

由于某些用户可能具有16位显示器,因此这些颜色可以在0..64K范围内.

但是,如果我们给单位增量颜色,例如unit0为0,则unitN为N,那么人类调试的颜色非常难.单位几乎无法区分.

我们希望为这些单位提供独特而独特的色彩.

我们目前正在使用二叉树(C++ map)以固定步骤递增以存储用过的颜色以检查冲突.这是低端硬件上的性能问题.即使这是一个哈希表并且避免使用string,游戏帧中的临时内存分配也是不受欢迎的.因此,我很想发现是否有办法避免完全保留历史,而不是优化代码.

有没有办法用大步骤或随机迭代数字0..64K,以便使用大多数64K可能的值,并避免使用已分配颜色的历史来避免冲突？

^{(屏幕上不可能有超过64K的可见单元,我们不必处理这种情况!)}

Answer 1

我的尝试:

1. 选择一个接近所需范围的素数(64007是一个很好的候选者).
2. 找到这个数字的原始根模数.

3. 选择"中等范围"原始根(43062 43067是一个很好的候选者).

   class Sequence
   {
   public:
        uint32_t get() const {return state;}
        void advance() { state = (state * k)%p;}
        void reset() { state = k; }
   private:
        uint32_t state = 43067;
        const uint32_t k = 43067;
        const uint32_t p = 64007;
   };
   

这以伪随机方式将范围[1,64007]中的所有数字恰好循环一次.