Iterating over a list in pseudo-random order without storing a shuffled list

Question

In a game, we use a technique called 'colour picking' to select units.

This means that every visible unit is given a unique colour.

Here is an example of a scene drawn for colour picking:

As some users may have 16-bit displays, these colours can be in the range 0..64K.

However, if we give the units incremental colours e.g. unit0 is 0, unitN is N then the colours are very hard for humans to debug. Units are virtually indistinguishable.

We want to give the units unique and distinctive colours.

We are currently incrementing in a fixed step using a binary tree (C++ map) to store used colours to check for collisions. This is a performance problem on low-end hardware. Even if this were a hash table and avoided using string, temporary memory allocation in game frames is to be frowned upon. So rather than optimising the code as it stands, I'm keen to discover if there are ways to avoid maintaining a history entirely.

Is there a way to iterate over the numbers 0..64K with a large step or randomly such that most of the 64K possible values are used, and avoiding using a history of already-allocated colours to avoid collisions?

^{(It is so unlikely that there are more than 64K visible units on the screen that we do not have to handle that case!)}

Messmate

Values 0 through 64K can be stored using 16-bit integers, so if you were to use an array and a Fisher-Yates shuffle, you would only need a 128K array and a single 16-bit index for the next unit's color. – Muddy

I don't think I understand this part: "However, if we give the units incremental colours e.g. unit0 is 0, unitN is N then the colours are very hard for humans to debug. Units are virtually indistinguishable." Do you mean the point of the exercise is to avoid having similar colors near each other?? – Poncho

How about LFSR ? – Oldworld

There exists a hack using a linear congruential generator, but you need some special constants so it will pick every element exactly once. Unluckily I don't remember the name of the hack and can't find a reference... – Steady

People reading this now may also want to consider this 2015 answer: https://mcmap.net/q/1018017/-generate-random-permutation-of-huge-list-in-python – Forman

Answer 1

My try:

1. Pick a prime number near your desired range (64007 is a good candidate here).
2. Find the primitive roots modulo p of this number.

3. Pick a "medium range" primitive root (43062 43067 is a good candidate).

   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;
   };
   

This cycles all the numbers in range [1, 64007) exactly once, in a pseudo-random fashion.

Extravehicular

I like this approach a lot! But I can't get the simplest test app to work with it: gist.github.com/williame/0a91da1452890eb1b061 ? – Messmate

Turns out I copied and pasted the wrong number, 43062 is not a primitive root of 64007. 43067 is good tho, I fixed my answer. – Extravehicular

I would love to see a general implementation that takes "desired range" as input. – Feasible

Answer 2

Can you simply take step_size to be the total available colors divided by the total units, and then use (unit_index * step_size) as the color for each unit?

Poncho

Answer 3

I don't really see the problem. As I wrote in the comments, you need only 128K to store a permutation of [0..64K), and you don't need any allocations inside the main loop. Here's a stateful color store in C++11 (in older C++, use a vector or new[]):

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++];
    }
};

You only need one of these structures. Now, whenever you create a new unit, call next_color on the ColorPicker and store it on the unit as an attribute.

This solution will cycle though the colors. If that's not desired, do a random_shuffle each time the index wraps around to zero.

Muddy

Answer 4

It seems to me that what's important is that the contrast between units which are close to each other is high enough, i.e. I would try to come up with some way to take the proximity of units into account.

For instance, you could take the X/Y coordinates of the units into account such that coordinates which are close to each other get colors with a high contrast, low contrast is only used for units which are sufficiently far away.

A first shot might be to have a simple array a of 256 colors such that there's a large contrast between a[n] and a[n+1]. You can then pick the color of units by using their X and/or Y coordinate modulo 256 as the index into the array. That way, you will get colors reused for units which are at least 256 pixels (or whatever metric you may use) apart, but different colors for units which are very close to each other.

Irreformable

Answer 5

First, use binary to store color states(1-used, 0-unused). 2^16=65536(states). If we use 1 bit for one color, 65536/8=8192 bytes are needed.
Next question is how to manage these bytes. I suggest a tree structue: upon these 8192 bytes, another (8192/8=)1024 bytes are needed, every bit in these upper bytes representes one byte in 8192 bytes, if one of lower bytes are ALL 1, its upper bit is 1.
This rule can expand upper and upper: 8192 -> 1024 -> 128 ... at last, to 1 byte(not fully used though).
To use this structure, you can generate a random number in 0..7 for many times, from the root byte, if its bit is 1, try again; if its 0, down to the lower byte, repeat these action until the lowest byte is reached.
Additionally, you can build this tree in one array: just like the heap in heapsort. (with some empty units).

APPEND: A int16 is need for one color, once down to a lower byte, you get a three-bit binary number, append them from left to right to the color number: int16. (The root byte represent only 2 states, and only generate 1-bit binary number, its form is 111111??.

Haldeman