Randomization is something that is pretty much a staple in games. But the tricky part is randomizing in an expected way.
Some kinds of randomization, you don’t want to be truly random- just mostly random- and you do in fact want it to go through all the possibilities more frequently, though in a random way.
The best example I can think up is to imagine you have a Enemy that can shoot forwards, backwards, up, and down. Now, targeting the player notwithstanding, let’s assume you want them to shoot randomly. If you go with the approach of just choosing a direction completely at random, you will find that the code will often choose the same direction many times in a row. This is more or less the problem with trying to randomize small sets of data. Each selected element is more or less chosen without regard to those chosen before. This fits probability, of course, but can be a bit weird gameplay wise.
Enter ItemBucket
The solution is fundamentally to make sure that items are chosen at random, but also that every item get’s used. The best solution I could think of was one where you choose elements at random, but you make sure you don’t choose the same elements twice during any one run. The class I created for this purpose I called “CItemBucket”. It’s functionality is fairly simple: it is constructed with the items it will contain. This initializes two lists with those elements. The ItemBucket can “dispense” items; when an item is dispensed, it is removed from the list. if the list is empty, it is reset from the Original List. this makes sure that in any number of elements of size N, any element in that list will occur exactly once during N dispenses. My original idea was to return a randomly indexed element each call, but then I got to thinking that, in many ways, we are simply dealing with a “shuffled deck” of elements, and returning items from that “deck”. So, at the cost of making Adding a bit more expensive, I think I was able to make the retrieval method O(n) for the number of present elements (based on the Queue implementation, that is).
Here, the, is the C# Implementation for this class:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
public class ItemBucket<T> { private int _dispensed = 0; private Queue<T> _elements; private T[] _original; private readonly Random rgenerator = new Random(); public ItemBucket(Random rg, params T[] source) : this(rg, (IEnumerable<T>)source) { } private IEnumerable<T> Shuffle<T>(IEnumerable<T> source) { return source.OrderBy<T, int>((item) => rgenerator.Next()); } public ItemBucket(params T[] source) : this((IEnumerable<T>)source) { } public ItemBucket(Random rg, IEnumerable<T> source) : this(source) { rgenerator = rg; } public ItemBucket(IEnumerable<T> source) { _original = source.ToArray(); _elements = new Queue<T>(Shuffle(_original)); } public static T[] RepeatArray(T[] array, int count) { var resultarray = new List<T>(array); for (int i = 0; i < count; i++) { resultarray.AddRange(array); } return resultarray.ToArray(); } public ItemBucket<T> AddRange(IEnumerable<T> Elements) { foreach (var iterate in Elements) { _elements.Enqueue(iterate); var neworiginal = new List<T>(_original) { iterate }; _original = neworiginal.ToArray(); } _elements = new Queue<T>(Shuffle(_elements)); return this; } public ItemBucket<T> Add(T element) { _elements.Enqueue(element); _elements = new Queue<T>(Shuffle(_elements)); var neworiginal = new List<T>(_original) { element }; _original = neworiginal.ToArray(); return this; } private T DispenseSingle() { //dispense a single item. //get an index into the Elements array. T retrieved = _elements.Dequeue(); if (!_elements.Any()) { //no elements, so re-create from Original. Debug.Print("Bucket Empty!"); _elements = new Queue<T>(Shuffle(_original)); } return retrieved; } public T Dispense() { return DispenseSingle(); } public IEnumerable<T> Dispense(int count) { for (int i = 0; i < count; i++) { yield return DispenseSingle(); } } } |
Here is some code that consumes this implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Program { static void Main(string[] args) { ItemBucket<int> usebucket = new ItemBucket<int>(ItemBucket<int>.RepeatArray(Enumerable.Range(0, 12).ToArray(), 3)); Console.WriteLine(); for (int i = 0; i < 120;i++ ) { Console.Write(i + ":" + usebucket.Dispense() + ","); } Console.ReadKey(); } } |
Works quite well, as far as I can tell.
But wait, there’s more!
Perhaps because I like to think of myself as something of a polyglot, let’s go ahead and come up with an implementation of this for Java. Now, doing this in Java would be a bit more tricky- that is, directly. Unlike the C# implementation, we don’t have the convenience of lambda’s to make a ‘pure’ shuffle. Instead, we would have to write our own implementation. Instead of that, I went with the original concept- that is, to choose,remove, and return a random index, and re-create the Bucket contents when we’ve emptied it. Here is the Java version of this class:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
import java.lang.reflect.Array; import java.util.ArrayList; import java.util.List; import java.util.Random; public class ItemBucket<T> { private ArrayList<T> _Elements; private ArrayList<T> _Original; private Random rgen = new Random(); public ItemBucket(T... Source) { this(new Random(), Source); } public static <K> K[] RepeatArray(K[] tocopy, int copies, Class classtype) { if (copies < 0) throw new IllegalArgumentException("copies must be non-negative."); @SuppressWarnings("unchecked") K[] resultarray = (K[]) Array.newInstance(classtype, tocopy.length * copies); for (int copy = 1; copy < copies; copy++) { for (int index = 0; index < resultarray.length; index++) { resultarray[index] = tocopy[index % tocopy.length]; } } return resultarray; } public ItemBucket(Random rg, T... Source) { rgen = rg; _Original = new ArrayList<T>(); _Elements = new ArrayList<T>(); for (T addto : Source) { _Original.add(addto); _Elements.add(addto); } } private T DispenseSingle() { // dispense a single item. // use the Random instance to get a random index. int randompos = rgen.nextInt(_Elements.size()); // grab that element. T retrieved = _Elements.get(randompos); _Elements.remove(randompos); // if the Elements list is empty, 'refresh' it from the Original. if (_Elements.isEmpty()) { _Elements.addAll(_Original); } return retrieved; } public T Dispense() { return DispenseSingle(); } public List<T> Dispense(int Count) { ArrayList<T> buildlist = new ArrayList<T>(); for (int i = 0; i < Count; i++) buildlist.add(Dispense()); return buildlist; } } |
Test code for the above Java implementation:
|
1 2 3 4 5 6 7 8 9 10 |
public class testItemBucket{ public static void main(String[] args) { ItemBucket<Integer> bucket = new ItemBucket<Integer>(ItemBucket.RepeatArray(new Integer[]{1, 2, 3,4,5,6,7,8,9,10},3,Integer.class)); //choose 90 items. for(int i=0;i<90;i++){ int gotvalue = bucket.Dispense().intValue(); System.out.print(i + ":" + gotvalue + ","); } } } |
As far as I’m concerned, the most interesting thing in the Java implementation is the “RepeatArray” method. Java’s Generic limitations prevent us from creating Arrays of the Generic Type Parameter directly, so instead we need to use some reflection magic. unfortunately, as far as I can tell there is no way to get the class of the actual type parameter in Java, so I had to resort to accepting that class as a parameter. Also, because of the lack of Generators/Enumerable methods, I ended up simply having that method return a List of the generic type, rather than an Enumerable.
It’s not over yet!
You might think, “OK, he’s covered C# and Java implementations- can I please go home. Well, yes, you can. But then you’ll miss my Python implementation! I went with the same approach I chose for Java- that is, retrieving items randomly and removing them. It’s fully possible to use the same methodology I used for the C# approach- using Queues and sorting on randomized keys- but I found this approach a bit less verbose, and more straightforward. And, it is my opinion that ‘straightforward’ is sort of the “python way”, so I went with that.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import random class ItemBucket: def __init__(self,pelements): #copy the provided elements. self.elements=[] self.original=[] for iterate in pelements: self.original.append(iterate) #copy the original list into the elements list. self.elements=self.original[1:] def DispenseSingle(self): #select a random index. index = random.randrange(len(self.elements)) result=self.elements.pop(index) if not self.elements: #if list is empty, recreate from original. self.elements=self.original[1:] return result; def DispenseMulti(self,n=1): #select n items and return them x=0 while x < n: yield DispenseSingle(self) x+=1 |
And, of course, the Python code that uses it:
|
1 2 3 |
ib=ItemBucket([1,2,3,4,5,6,7,8,9]*3) for i in range(0,40): print str(i) + ":" + str(ib.DispenseSingle()) |
The first thing that stands out is just how much shorter this one is to either the Java or C# implementations. This is probably mostly due to the dynamic typing of Python, as well as a few syntactic shortcuts. The only “gotcha” I found was that Python didn’t really support overloaded methods. Technically, I could create one method and then verify what parameters were actually passed, but in this case I wanted one to be a Generator Method, and the other to simply return a single element. Only way I could figure out how to do that was to have separate DispenseSingle() and DispenseMulti() methods. It also doesn’t expose the innards like the other implementations, in that you cannot add Elements to an already constructed instance. In retrospect, I’m not really sure if it’s a good idea to make the design Mutable at all. The Most typical use-case would be to construct it with all the elements it will use, and not change it afterwards- that’s the use case I have in BASeBlock, and the use-case I’m considering using my Java implementation for. So having extra methods to add elements, and keep fields “fresh” and consistent adds implementation complexity for little gain.
Have something to say about this post? Comment!
One thought on “Kicking the ItemBucket”
Having read this I believed it was really informative.
I appreciate you taking the time and effort to put this
information together. I once again find myself spending way too much time both reading and leaving comments.
But so what, it was still worth it!