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!)}

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.

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?

Answer 3

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.

Answer 4

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.