jump to navigation

A predictable (game) random generator May 28, 2009

Posted by pageman in Gaming / GameDev News & Articles.
Tags: , , , , , , ,
trackback

I just ran across this question in StackOverflow:

“I’m a web-game developer and I got a problem with random numbers. Let’s say that a player has 20% chance to get a critical hit with his sword. That means, 1 out of 5 hits should be critical. The problem is I got very bad real life results — sometimes players get 3 crits in 5 hits, sometimes none in 15 hits. Battles are rather short (3-10 hits) so it’s important to get good random distribution.”

Sounds familiar?  Here’s a “game mechanics” situation from GameDev.net as suggested by a commenter:

“A blade spider is at your throat. It hits and you miss. It hits again and you miss again. And again and again, until there’s nothing left of you to hit. You’re dead and there’s a two-ton arachnid gloating over your corpse. Impossible? No. Improbable? Yes. But given enough players and given enough time, the improbable becomes almost certain. It wasn’t that the blade spider was hard, it was just bad luck. How frustrating. It’s enough to make a player want to quit.“

Obviously, there has to be a way to do it. One suggestion was to use a shufflebag:

“In games or educational programs you often don’t want real randomness. Unsurprisingly random it’s often a bit too random. You may get some items several times in a row and others too rarely. It’s either too easy or too hard. Balancing the weights is hard as well, because each run is too different. And if that wouldn’t be already bad enough; it’s also difficult to verify the results.

Here’s the code of the commenter based from his own java code:

package net.orfjackal.puzzlewarrior;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
* @author Esko Luontola
* @since 25.2.2008
* @originally here: http://bit.ly/9vgIV
*/
public class ShuffleBag {

private final Random random;

/**
* Unused values are in the range {@code 0 <= index < cursor}.
* Used values are in the range {@code cursor <= index < values.size()}.
*/
private final List values = new ArrayList();
private int cursor = 0;

public ShuffleBag() {
this(new Random());
}

public ShuffleBag(Random random) {
this.random = random;
}

public void add(T value) {
values.add(value);
}

public T get() {
if (values.size() == 0) {
throw new IllegalStateException("bag is empty");
}
int grab = randomUnused();
T value = values.get(grab);
markAsUsed(grab);
return value;
}

private int randomUnused() {
if (cursor <= 0) {
cursor = values.size();
}
return random.nextInt(cursor);
}

private void markAsUsed(int indexOfUsed) {
cursor--;
swap(values, indexOfUsed, cursor);
}

private static void swap(List list, int x, int y) {
T tmp = list.get(x);
list.set(x, list.get(y));
list.set(y, tmp);
}

public void addMany(T value, int quantity) {
for (int i = 0; i < quantity; i++) {
add(value);
}
}

public List getMany(int quantity) {
List results = new ArrayList(quantity);
for (int i = 0; i < quantity; i++) {
results.add(get());
}
return results;
}
}

If you’re not into Java, here’s ShuffleBag code in Ruby:

class Fairish
def initialize(probability, unfair_low, unfair_high, min_rolls)
@probability, @unfair_low, @unfair_high, @min_rolls = probability, unfair_low, unfair_high, min_rolls
@rolls, @hits = 0, 0
end

def fire!
hit = if @rolls >= @min_rolls && observed_probability > @unfair_high
false
elsif @rolls >= @min_rolls && observed_probability < @unfair_low
true
else
rand <= @probability
end
@hits += 1 if hit
@rolls += 1
return hit
end

private
def observed_probability
@hits.to_f / @rolls
end
end

class Random
def initialize(probability)
@probability = probability
end

def fire!
rand <= @probability
end
end

trials = 100000
trial_size = 10
random_out_of_bounds_low = 0
random_out_of_bounds_high = 0
fairish_out_of_bounds_low = 0
fairish_out_of_bounds_high = 0

probability = 0.2
lower_bound = 0.1
upper_bound = 0.4
min_rolls = trial_size / 2

trials.times do |n|
fairish = Fairish.new probability, lower_bound, upper_bound, min_rolls
fairish_hits = 0
random = Random.new probability
random_hits = 0

trial_size.times do |x|
fairish_hits += 1 if fairish.fire!
random_hits += 1 if random.fire!
end

fairish_out_of_bounds_low += 1 if fairish_hits.to_f / trial_size upper_bound
random_out_of_bounds_low += 1 if random_hits.to_f / trial_size upper_bound
end

puts "Fairish was out of bounds #{(fairish_out_of_bounds_low + fairish_out_of_bounds_high).to_f/trials * 100}% of the time (#{fairish_out_of_bounds_low.to_f/trials * 100}% low and #{fairish_out_of_bounds_high.to_f/trials * 100}% high)."
puts "Random was out of bounds #{(random_out_of_bounds_low + random_out_of_bounds_high).to_f/trials * 100}% of the time (#{random_out_of_bounds_low.to_f/trials * 100}% low and #{random_out_of_bounds_high.to_f/trials * 100}% high)."

Happy ShuffleBagging!

posted by Paul “The Pageman” Pajo

Comments»

No comments yet — be the first.