Iterating over a list in pseudo-random order without storing a shuffled list
c++, random
Solution
My try:
- Pick a prime number near your desired range (64007 is a good candidate here).
- Find the primitive roots modulo p of this number.
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.
Problem
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!)