Saturday, May 8, 2010

Making Random Suck Less

One of the biggest complaints I get about WallSwitch is that the random switching sucks. It repeats images too frequently and just doesn't 'feel right'. I couldn't agree more, so when I ran across this article, I figured I could do something about it.

The problem is that random numbers don't work how the human brain expects. The article above explains it in detail, but suffice it to say that pure/pseudo random numbers suck for most things a user interacts with. What I wanted was a way to provide selections that are still nondeterministic, but closer to what users expect.

The method itself is nothing more than random selection using weighted items. I wanted to keep a feeling of randomness, but make sure more recent selections were less likely to appear. This being Java, the first thing I did was make an interface to hold the object and it's priority:

public interface BetterRandomItem {
 int getPriority();
 void setPriority(int newPriority);

Then, I made a choice() function (name taken from Python's random.choice) that uses this priority.

public static BetterRandomItem choice(List items) {
  if(items == null || items.size() == 0)
   throw new IllegalArgumentException("items is null or empty");
  // Sum all the priority values
  int itemSpace = 0;
  for(int i = 0; i < items.size(); i++)
   itemSpace += items.get(i).getPriority();  
  // Pull an int from that space
  int target = new Random().nextInt(itemSpace + 1);
  // Match the int to the corresponding item
  int tmpVal = 0;
  for(int i = 0; i < items.size(); i++){
   tmpVal += items.get(i).getPriority();
   if(tmpVal >= target)
    return items.get(i);
  // If that failed, return the last in the list, I guess
  return items.get(items.size() - 1);

Not the most complex piece of code ever written, but it'll go a long way to making users a bit happier with 'random' selections. Since putting this in, the emails and comments about my random function sucking have completely stopped.

Note: For my implementation, I kept track of the last 50 images displayed and gave them weights 1-50. Any unseen images were weighted as (num seen images * 10), giving them significantly more weight than those that had been seen.

Another Note: Watch out for int overflows in itemSpace. It would be nice if Random.nextLong took an argument.