Neat. I actually just did this for a game a couple of weeks ago. My approach was just slightly different, though. Instead of adding up the total odds in it's own variable, I just looped through the items, adding the last items odds to its own. So if I have item weights of [1, 2, 3] it becomes [1, 3, 6]. This makes it so that the last index is the total odds and removes the need to subtract anything from "n" because that's all precomputed. Would it make a difference? Probably not, but I thought it might be interesting to share
I've seen that in the wild once or twice, the math turns out the same but I think pre-adjusting the weights like this makes debugging a little harder if you (for example) print out the table and see (1, 3, 6) when you initialized it to (1, 2, 3)
@@DragoniteSpam Well, the benefit is no subtraction inside the loop, but realistically this will make no measurable difference unless you have extremely large lists
Was expecting animation curves, but leaving disappointed. Regardless, great video! Always nice to have videos that answer common discord server questions.
I guess if you have large list of items, you could transform linear search to binary search 🤔 Give items prefix sum, then find location for random value. Doing this only makes sense when same weights are used multiple times, as creating prefix sum takes some time (required to be done once, so good if reused).
@@DragoniteSpam Yeah, for less than 10 items linear search is more than sufficient. I would imagine binary search would be useful for runtime generated lists, not specifically crafted ones. Like you have a large quantity of instances, and you want to pick a handful of them based on some attribute as the weight.
