シャッフルされたリストを保存せずに擬似ランダム順でリストを反復する

Question

a gameには、ユニットを選択するために 'colour picking'というテクニックが使用されています。

これは、すべての可視ユニットに一意の色が与えられていることを意味します。ここ

カラーピッキングのために描かれたシーンの一例である：

一部のユーザーは、16ビットのディスプレイを有することができるように、これらの色が範囲0..64Kであることができます。

ただし、ユニットのインクリメンタルカラーを指定すると、 unit0が0、unitNがNならば、色は人間がデバッグするのが非常に困難です。単位は事実上区別できません。

ユニークで個性的な色を与えたいと考えています。

現在、バイナリツリー（C++ map）を使用して固定ステップでインクリメントして、使用する色を保存して衝突をチェックしています。これはローエンドのハードウェアでのパフォーマンス上の問題です。これがハッシュテーブルであっても、stringの使用を避けても、ゲームフレーム内の一時的なメモリ割り当ては嫌われます。したがって、コードを最適化するのではなく、履歴を完全に保持しないようにする方法があるかどうかを知りたいと思っています。

64Kの可能な値の大部分が使用されるように、0.64Kを大きなステップでランダムに反復する方法はありますか？衝突を回避するために既に割り当てられた色の履歴を使用しないでください。

^{（私たちはそのような場合に対処する必要はありません、画面上に複数64K見えユニットがあるようにはほとんどありません！）}

Answer 1

私の試み：

1. （64007はここで良い候補である）あなたの所望の範囲に近いprime numberを選択します。
2. この番号のprimitive roots modulo pを見つけます。

3. 「中範囲」のプリミティブルートを選択します（ 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）ですべての数字、。

Answer 2

あなたは、単にで割った総利用可能な色であることをstep_size取ることができますユニット全体の色として（unit_index * step_size）を使用しますか？

Answer 3

まず、カラー状態（1使用、0未使用）を保存するためにバイナリを使用します。 2^16 = 65536（州）。 1つの色に1ビットを使用する場合、65536/8 = 8192バイトが必要です。
次の質問は、これらのバイトを管理する方法です。これらの8192バイトには、別の（8192/8 =）1024バイトが必要です。これらの上位バイトの各ビットは、下位バイトのいずれかがALLである場合、8192バイトの1バイトを表し、その上位ビット
このルールは、8192 - > 1024 - > 128 ...最後に1バイトまで（全面的には使用されていません）、上位と上位を拡張できます。
この構造体を使用するには、ビットが1の場合、ルートバイトから何度も0..7で乱数を生成することができます。 0の場合、下位バイトまで下位バイトに達するまでこれらの動作を繰り返します。
さらに、ヒープソースのヒープと同様に、このツリーを1つのアレイに構築できます。 （いくつかの空の単位で）。

APPEND：int16は1つの色が必要ですが、下位バイトまでは3ビットの2進数を得て、左から右に色番号int16を付け加えます。 （ルートバイトは2状態のみを表し、その形式は111111です。

Answer 4

私はコメントに書いたとおり、128Kにする必要があります順列を格納する[0 ..64K）、メインループの内部に割り当てを必要としません。ここでは、ステートフル色ストアは（古いC++で、vectorまたはnew[]を使用）C++ 11である：

class ColorPicker { 
    std::array<uint16_t, 65536> colors; 
    uint16_t idx; 

    public: 
    ColorPicker() : idx(0) 
    { 
     std::iota(colors.begin(), colors.end(), 0); 
     std::random_shuffle(colors.begin(), colors.end()); 
    } 

    uint16_t next_color() 
    { 
     return colors[idx++]; 
    } 
}; 

あなただけのこれらの構造のうちの1つを必要とします。今度は、新しいユニットを作成するたびに、ColorPickerにnext_colorと呼び出し、それを属性としてユニットに格納します。

このソリューションは、色を循環します。それが望ましくない場合は、インデックスが0に折り返されるたびにrandom_shuffleを実行します。

Answer 5

重要なことは、お互いに近いユニット間のコントラストが十分高いことです。つまり、ユニットの近接を考慮する方法を考案することになります。

たとえば、互いに近くにある座標が高いコントラストで色を取得し、低いコントラストが十分に遠い単位に対してのみ使用されるように、ユニットのX/Y座標を考慮に入れることができます。

最初のショットは、a[n]とa[n+1]の間に大きなコントラストがあるように、256色の単純な配列aを持つことがあります。次に、配列のインデックスとして、モジュロ256のXおよび/またはY座標を使用して、単位の色を選択できます。こうすることで、少なくとも256ピクセル（または使用するメトリック）の単位で色を再利用できますが、互いに非常に近い単位では色が異なります。