Upgrading a probability selection tree to a binary indexed array for dynamic probability changes
I'm focusing here on using C# as the primary language, so there are certain assertions I won't be able to make because of the way the language works. For instance, a binary indexed array is almost always faster in C/C++ than a tree structure, but in C# the tree structure, in terms of shear access speed is a bit faster than the binary indexed array. Even though the shear access speed isn't ideal for a fixed probability selection tree, there are many other benefits to the structure that we'll examine. If you didn't read the first posting it would be helpful since we'll be mirroring the existing code and only changing the underlying data structure, "Probability selection using a chance tree. Solutions for standard and loaded dice. ".
When working with a tree structure, our nodes had to be capable of storing information about connections. That meant pointers to the leaf nodes. If you were given a child node and needed access to the parent, you may also need to store a parent node pointer as well. That means three connection pointers altogether if we want to solve every scenario. We can get rid of all the connection information on the nodes we store, since binary indexed arrays use basic computations to gain access to children or parent indexes. We'll call the new structure Chance and it will only store probability information, no connection information whatsoever.
public class Chance {
public int GrowthWeight;
public int CurrentWeight;
public object Item;
public Chance(int growthWeight, int currentWeight, object item) {
this.GrowthWeight = growthWeight;
this.CurrentWeight = currentWeight;
this.Item = item;
}
}
Without the tree in place, adding nodes is going to be quite a bit different. We are now storing the chances in an array, and then treating the array like a tree. How? Well, you'll see. For now, since we are using an array, we have to eat the cost of dynamically resizing it as we grow. Note, we get a hit when building our probability tree and if we grow beyond it's extents, but we get removal and look-ups without any additional overhead. This is the basic array-grow and copy algorithm.
/* EnsureCapacity */
if ( count == chances.Length ) {
Chance[] newChances = new Chance[chances.Length << 1];
Array.Copy(chances, 0, newChances, 0, count);
chances = newChances;
}
Obviously allocating arrays is going to cause some speed issues compared to the previous tree version. We save a small amount of space to make up for this speed loss, and we only eat the speed cost at initialization (as long as we don't add a bunch of dynamic probabilities later). We can also preallocate the array to be the appropriate size the first time through.
You'll be surprised how easy it is to add an item. We simply pop it on the end of the array. We don't bother searching for a slot or finding an empty space, we just place it right on the end of the array, and it becomes a new element. A count variable always points to our last element. Once the element is placed, we use it's index to walk up and add the chance value to all of it's parents. We do this through bit shifting. If you take the index of an element, subtract 1, and then right shift 1 bit, you get the elements parent. We do this until we've walked all the way back up to the 0th element.
int index = count++;
chances[index] = new Chance(chance, chance, item);
while(index > 0) {
index = (index - 1) >> 1;
chances[index].GrowthWeight += chance;
}
Done with adding elements. Our FindNode implementation is going to be a bit different. Previously we used the concepts of left and right nodes in order to recurse into our tree. Given the index of the parent, we need and algorithm to find the children and where they are located in the array. Then we have to access those indexes and treat them like left and right nodes. Thankfully this process is another bit shifting operation. You can get the left node by shifting the parent index right one bit and then adding one. Left and right nodes appear next to one another in the array and so you add two instead of one for the right node.
private int FindNode(int chance) {
int index = 0;
int prior = 0;
while(true) {
prior += chances[index].CurrentWeight;
if ( chance < prior ) {
return index;
}
index = (index << 1) + 1;
if ( chance >= (prior + chances[index].GrowthWeight) ) {
prior += chances[index].GrowthWeight;
index++;
}
}
}
Looks simple because it is simple. This change is made for the sole purpose of allowing two things, faster insertion times for new probabilities, and faster removal times for consumed probabilities. In the case of ammo selection, we can now remove spent ammo, and add it back in when the user gets some more without running all over the tree. In the case of the dice, if we want to disallow two in a row, we can remove the item, pull the next value, then add our item back in. We can even implement a swap command for dice so that as we pull out our one value, we insert our other value. If the weight values are the same during replacement, we can even avoid recursion (yet another small performance feature). Next post we'll start looking solely at additions to this class to support various possibility situations that arise in gaming, and start to flush out the API a bit more and add dynamic removal and swapping APIs.