In my recent escapades with developing Ambience, I’ve spent several days (!!) adding over 50 new weapons to the game, each with its own strengths and weaknesses (and quirks). It’s been a big job, but now I get to reap the rewards and finally add them to the game.
— Rhombus Ragmuffin (@RhombusGameDev) February 11, 2018
Except… how do those items get generated in-game, anyway?
This was yet another system that I had implemented very early on and had all but forgotten about. So I decided to crack open my rusty old system to see if I could improve the way items were generated.
The Original System
When a dungeon is generated in Ambience, all the possible items for that dungeon are loaded into a grid data structure, along with their respective probabilities of appearance and the dungeon floors they should appear on. Then, an “evaluation” script looks at the grid and spits out the ID number of the item to be generated. This general idea remained unchanged, but what I did change was the way the evaluation system worked.
The original script used a long and rather dodgy iterative method. It would scroll through each item in the grid, and for each it would generate a random number from 0 to 1000 and compare this with the set probability of that item appearing. If the random number was less than the probability, that item was selected and the loop was terminated. Of course, this system had the potential to go on indefinitely without ever selecting an item, so a maximum number of trials (something like 2,000) was set to prevent this.
Even so, having to generate a random number for every item checked, as well as having to loop through the grid multiple times to find an item at all, made this system rather inefficient. In addition, if the probabilities of items was less than (or more than) 1000, some items would appear more or less often than specified. In other words, the system was just plain dodgy. So, off to work I went…
A Better Method
Getting rid of the iterations was top priority right from the start. I wanted to build a system that required the least computation time – that meant generating a single random number and scrolling through the data structure only once, while making sure that a valid item was produced every time. Here’s the solution I came up with:
- The first thing I did was sum all the probabilities to give a basis against which I could compare the relative probabilities of each item. (Much better than having to manually make sure that all the probability values added up to 1000!)
- I then selected a random number between zero and the probability total. That random number corresponded to the item I was going to choose.
- To find that item, I went through each item in the grid in turn. Each item’s probability was added to a cumulative sum variable keeping track of the cumulative sum of probability values. Then, I checked: was the cumulative sum, including the latest item, bigger than the random number I chose? If so, then the latest item was the one to generate.
Here’s a diagram which probably explains everything a lot more easily than the wall of text above:
But wait! What about items on different floors?
Ohhhh, that’s right… we also have to check if the item we’re making can actually appear on that floor before generating it!
There are two ways I found to approach this. One was to choose a random number at the start, then go through the grid and check if the chosen item can be made on that floor before “approving” it. If that item can’t be generated on this floor (an “invalid item”, so to speak), choose another random item from those remaining and keep going.
Even though this method only needed to go through the grid once, the contribution of these “invalid items” to the sum of probability values was problematic. Since new items were only chosen from the list of remaining possibilities, this meant that items earlier on in the list were more likely to be skipped over in the end result – thus skewing the true probabilities. Even worse, the final item in the list could itself be an invalid item for that floor, which when chosen would result in no valid item being generated!
In the alternative method, which I ended up using, the script skimmed through the grid once at the very start to find any invalid items and set their probability values to zero – thus effectively removing them from the grid. Only then did the script choose a random number and go through the grid a second time to find the corresponding item. Although this meant that the grid had to be checked twice, it guaranteed that all items and probability values were valid every time. In any case, this was much better than checking the grid indefinitely in an iterative method!
Here’s another nice diagram summarizing the above:
The Learning Curve
For me, the biggest takeaway from this was to make systems simple, but not too simple. It’s nice to have a clean, functional item generation system that doesn’t rely on iteration – but at the same time, my original aim to “go through the grid only once” turned out to create more problems than it solved. The final script, while perhaps not as efficient as I had originally hoped, was still good enough to get the job done.