Loot Table Problems

[trevius]

I have noticed this issue for a while now and figured it may be time to start looking into some possibilities to make loot tables work a little better. As it is now, it seems like the loot table system isn't nearly as random as it should be.

From what I can tell, the code pulls the loot tables and then it sorts the drops in the tables by the chance they are set to. After that, it then uses random 0 to 99 and goes down the list from top to bottom seeing if one of the items gets the right random needed for it to drop and then it stops. I think this creates a problem because having them sorted the same way each time means that the ones at the top of that sorted list are always more likely to be chosen than ones at the bottom of the list.

As an example, lets say we have 10 items all with a 10% chance to drop. It will then start at the first item in the sorted list and start randoming 0 to 99 and once it gets a number in the needed 10% range, it stops. So, even though it seems like it should average out to be random, it doesn't seem to be working that way. It is giving items at the top of the list a considerably larger preference than ones at the bottom of the list. Which means you will see the ones at the top of the list drop much more often than any others.

From everything I have seen so far while testing in game, it seems like it sorts the output alphabetically and so anything starting with lower letters in the alphabetical order is more likely to drop than others.

I marked the section that I think is responsible for the way that loot tables are currently created in RED in the code below.

loottables.cpp

// Queries the loottable: adds item & coin to the npc
void ZoneDatabase::AddLootTableToNPC(NPC* npc,int32 loottable_id, ItemList* itemlist, int32* copper, int32* silver, int32* gold, int32* plat) {
	_ZP(Database_AddLootTableToNPC);
//if (loottable_id == 178190)
//DebugBreak();
	const LootTable_Struct* lts = 0;
	*copper = 0;
	*silver = 0;
	*gold = 0;
	*plat = 0;

	lts = database.GetLootTable(loottable_id);
	if (!lts)
		return;

	// do coin
	if (lts->mincash > lts->maxcash) {
		cerr << "Error in loottable #" << loottable_id << ": mincash > maxcash" << endl;
	}
	else if (lts->maxcash != 0) {
		int32 cash = 0;
		if (lts->mincash == lts->maxcash)
			cash = lts->mincash;
		else
			cash = (rand() % (lts->maxcash - lts->mincash)) + lts->mincash;
		if (cash != 0) {
			if (lts->avgcoin != 0) {
				//this is some crazy ass stuff... and makes very little sense... dont use it, k?
				int32 mincoin = (int32) (lts->avgcoin * 0.75 + 1);
				int32 maxcoin = (int32) (lts->avgcoin * 1.25 + 1);
				*copper = (rand() % (maxcoin - mincoin)) + mincoin - 1;
				*silver = (rand() % (maxcoin - mincoin)) + mincoin - 1;
				*gold = (rand() % (maxcoin - mincoin)) + mincoin - 1;
				cash -= *copper;
				cash -= *silver * 10;
				cash -= *gold * 100;
			}
			*plat = cash / 1000;
			cash -= *plat * 1000;
			int32 gold2 = cash / 100;
			cash -= gold2 * 100;
			int32 silver2 = cash / 10;
			cash -= silver2 * 10;
			*gold += gold2;
			*silver += silver2;
			*copper += cash;
		}
	}

	// Do items
	for (int32 i=0; i<lts->NumEntries; i++) {
		for (int32 k = 1; k <= lts->Entries[i].multiplier; k++) {
			if ( MakeRandomInt(0,99) < lts->Entries[i].probability) {
				AddLootDropToNPC(npc,lts->Entries[i].lootdrop_id, itemlist);
			}
		}
	}
}

I definitely think that loot tables could be done much better than the way they currently are. Here are some suggestions:

1. Randomize the order of the list of loot drops each time before it starts going down the list to do the random 0 to 99. This should ensure that no item gets preference in a list of equal chance drop rates. To make sure this works to make the list as random as possible, you would also need to get the count of how many different percentages are set. So, if you have 3 set with 25% each and 1 with 15 and another with 10, the count would be 3 different percentage drop rates. Then the system would need to randomly select which percentage to use first instead of just always starting on either the highest or the lowest percentage.

If the order of the table was randomized first (maybe using a hash), you should be able to set all items to have 100% chance and it would give each item an equal chance of dropping, since it would randomize the list and then chose the first one on that randomized list.

2. Assign a number range to each item in the table at the time the loot table is created so that the total is from 99 and then random the 0 to 99 and pick whichever item is already set for the range that the random number landed in. So, if you have 4 items each with 25% drop rate, it would assign the first item from 0 to 24, second item from 25 to 49, 3rd item from 50 to 74 and the 4th item from 75 to 99. And if the random landed on 55 it would chose the 3rd item. This also works well for lists with multiple different chance drop rates. You could have 1 item with 50% chance, another with 25, another with 15 and 1 with 10 so that it totals 100%. In this scenario, it would assign 0 to 49 for the first item, 50 to 74 for the second, 75 to 89 for the 3rd and 90 to 99 for the 4th. Then, if the random landed on 78, it would chose the 3rd item in that list.

I think this would probably make the best solution, but I don't know how hard it would be for it to create the lists I described. Plus, if the total chance in the table didn't equal 100, it would cause problems and would need additional code to correct it. As long as it was less than 100%, it could just random again and again until it landed on the right percentage range. Or, it could just end there and not give any loot (might be good for setting extremely rare drop rates). But if the total was more than 100%, I am not sure exactly what the best way would be to deal with that other than totaling the chance drop rates and dividing them so that they total 100%. So, if you had 4 items all set to 100% chance then it would total it and see it equals 400%, so it would divide each drop chance by 4 so that the total was 100% as it should be and it turns each chance drop into 25% as they should be. If there was a way to make that work, it might be nice for loot tables that have multiple items that should all have equal chance to drop. Then instead of having to break out a calculator to figure out how to total 100 with 7 drops in the list, you could just set them all to 100 and let the loot code do it for you automatically.

If the code could figure out what to divide by to equal 100%, it should work in all scenarios. So, if you have an item with 75% chance, one with 50% chance, one with 25% chance, the total would be 150%, so the code would know to divide each chance by 1.5. So in this case, the first item would equal 50%, the second would be 33.3 and the 3rd would be 16.6 and the new total would be 100% as it should.

3. Another option might be to have it random once for every item in the table and then if more than 1 equals the random number, it would random again between the list of items that were selected by the randoming process. So, if you have 10 items each set to 10% drop chance, it would go down the full list and maybe 2 or 3 items would be selected due to the random number landing in their percentage range. Then it would randomly chose one of those 3 items. This way it should ensure that items at the top of the list don't get any special preference as all drops get a chance to be checked if they can be selected by the 0 to 99 random.

Also, I am not sure but I would think that it should be randoming from 1 to 100 instead of 0 to 99. Maybe I am missing something there, but I don't see how 0 would factor in on the randoms other than to make 0s a fail so that it moves on to check the next item.

Either way, I think the loot table code definitely could use some tweaks to make it work better. I will see if I can find anything to maybe help some, but as I have said before, my coding skills are not so great just yet. If anyone feels like chiming in or helping with this, it would be appreciated

[ChaosSlayer]

imho there is nothing inherently wrong with picking 0-99 random number as long as its... well random

if number do nto realy number oh have tendency to pile up in specific range, then the problem is with random number generator itself/seed

[KLS]

The code you pointed out doesn't do as you describe. That basically goes through the loot table entries and sees if we should trigger them. What you're describing would happen with loot drops which is done in AddLootDropToNPC(NPC* npc,int32 lootdrop_id, ItemList* itemlist).

[cavedude]

I will agree the randomness is off a bit. Often, I'll see the same rare item drop 4, 5, even 6 times in a row. Now obviously, this happened on Live as well but it nags me that it feels like it's a bit too common on Emu.

Now, unless the code has changed in the past year or so when I did my test, I have to disagree that the math is off. One weekend I had nothing to do, and so I killed and respawned 3 NPCs and recorded their drop rates. I did this exactly 200 times each. In the end, I wasn't surprised to see that the actual drop percentages were extremely close to the percentages in the DB. It was close enough that I was happy with it, and I bet if I kept going eventually those percentages would have became identical. If I remember, I used one NPC with 1 single short loottable, another with several medium length ones, and another with a table so long the rates were like 2 or 3% each. All of them were fine.

[ChaosSlayer]

well if on LIVE mob keeps droping same thing over and over LOGICLy its becasue its chance to drop it is much higher.

However if you have 5 items set up at 20% each and after 100 kills you get 90+ copies of item A - something wrong with the RND

[trevius]

The problem isn't that the random number generator is messed up, it is that it checks the chance of each drop down a static list. So, the list will be in the same order every time.

If you have 10 items all set to 10% chance to drop, it will start at the first item and random to 99 and if the output is less than 9, it will use that item. If the output is greater than 9, it moves onto the next item and randoms to 99 for that item. So, for it to select the last items on the list, it must first fail to select any previous items on the list.

I don't know about you, but it seems to me that using that system it would prefer items earlier in the list than later in it. I think the problem is that this system sounds like it should be giving fair odds to all of the loot pieces in the table, but I think it is one of those tricky math problems that looks correct at first glance, but for some reason it is wrong.

Here is an example of how it currently works and why I think it is wrong:

Let's say we have a contest with 10 people and each person is told to write a number from 1 to 10 on a piece of paper. All 10 people are told to show their numbers at the same time. Let's say that the first person and the last person both chose the correct number. But, since the first person is first in the list of people, they are the one that wins even though the last person also selected the same number with the same odds of getting the correct number. Of course this example is slightly wrong because once a winner is chosen with the current loot system, it doesn't even bother to check if anyone else would have "won" as well. But, the concept is the same. It's almost like playing blackjack against the casino, the house always wins if they get blackjack. It means that the odds are slightly in favor, which they definitely should not be in the case of loot tables.

[ChaosSlayer]

. So, for it to select the last items on the list, it must first fail to select any previous items on the list.

well thats at least unnessesary complicated.

i was writing a simple RND function for one of my quests it worked like this:

table:
1-50 A
51-65 B
66-90 C
91-100 D


-select a number 1 to 100
-check the number vs the limit boundaries:

if x<50 then A
if x>50 and x<66 then B
if x>65 and x<91 then C
if x>90 and x<101 then D


i think this is simple and reliable enough

[trevius]

That is exactly one of the solutions I suggested above and I think it would make loot tables perfectly random with the proper drop rates chances.

[ChaosSlayer]

Trev after thinking about it I don't think anything is wrong with current approach.

you roll a number
you check number of vs first item range, if satisfied- number is applied, if it fails you move to next number, etc
as long as you do not reroll, this system is prety mcuh identical to my if statements, you jsut have apply diffirent mechanics.

taking my table from above.
you go like this

rolled X (let say 96)

if X<51 then A else
If X <66 then B else
IF X<91 then C, else
if X< 101 then D
end if
end if
end if
end if


and yes you ONLY move to next value IF first comparsen has fail- but that oen kind of obvious. If first range is 1-10 and you roll 9 - thats a valid number for the range. If you roll more than 10 - then you failed the comparecen and compare vs next range etc


in SHORT the system works AS LONG AS NUMBER IS NOT REROLLED!! - thats the part which MAY BE BROKEN

[trevius]

Yes, that way works too, which is basically exactly the same as what you already posted.

The thing I think you aren't understanding is that the current system works like this as far as I can tell:

X = $random 0,99
If X > 9 then A else
Y = $random 0,99
If Y > 9 then B else
Z = $random 0,99
If Z > 9 then C else
X2 = $random 0,99
If X2 > 9 then D else
Y2 = $random 0,99
If Y2 > 9 then E else
Z2 = $random 0,99
If Z2 > 9 then F else
X3 = $random 0,99
If X3 > 9 then G else
Y3 = $random 0,99
If Y3 > 9 then H else
Z3 = $random 0,99
If Z3 > 9 then I else
X4 = $random 0,99
If X4 > 9 then J else

So, it randoms each time and if it doesn't equal less than that percent, then it randoms the next on the list and so on. So even if the last 5 on the list would have randomed less than the percentage setting, it would always only select the first item in the list as the drop and ignore anything after that. If I was betting money each time this was happening, I would want to be first on that list because the lower on that list you are, the greater the chance is that someone else will "win" before you and block your chance at winning.

[cavedude]

Your A-J example is a perfectly acceptable way of fairly picking a value. Assuming each of the 10 values have an equal chance of being picked, then they each have a 90% chance to fail their roll. The odds are strongly against any of them from being picked, that's what makes it fair. Provided the order of the values always remains the same, the "magic number" that needs to be rolled for a winner to occur is the same for each value, and finally and most importantly failed rolls are not removed from the pool then this system will work fine. In a way actually, the last value has a bit of an advantage in situations where a winner must be picked, because if nothing was picked above it, it has to be picked even if it was going to fail its roll. After all, odds are we'll get to that last number every 10th try

Now, this system works best if each value has an equal chance of being picked. If not, then the values must be listed in order from lowest probability to highest. If EQEmu does not do that, then we have an issue.

[ChaosSlayer]

Trev: ok I see what you mean

Cavedude, IMHO to avoid unnesesary complication why not substitute current system with something with more straight forward which does not depend on which order items listed in?

the value X should only be randomed ONCE, the all ranges can be put in a list ANY order (default so to speak) and made correspand to a range value in the list.

let say you have 5 items on the list: 10%, 25%, 5%, 20%, 40% (no need to sort)

the list then woudl look like this:
A(10)
B (A+25=35)
C (B+5=40)
D(C+20=60)
E(D+40=100)

now you roll your X 0 to 99, and let say you end up with 77.
Now you go into the list and see which range 77 falls into, lookign at gaps in manner of:
is X < A? if yes then A is true, else :
.......is X<B if yes then B is true else:
ETC

this looks way more straigth forward to me not to mention you save CPU time by only rolling ONCE

[KLS]

Assuming each step is required to fail before the next step then yes those at the final steps will have a lower chance to be triggered.

If you have an item list of 10 items all at 10% drop rate assuming trev's situation as described:

Item# | % chance to get to this step
1 | 100%
2 | 90%
3 | 81%
4 | 72.9%
5 | 65.61%
6 | 59.05%
7 | 53.14%
8 | 47.63%
9 | 43.05%
10 | 38.05%
No item | 34.87%

If you're item 10 and you're only getting to even roll 38% of the time even though you have 10% chance to roll just like item one. You're only getting the opportunity less than half as much. Clearly you wont drop as much, and also despite having 10 items at 10% drop rate on the slot you would not actually ever get 100% drop unless the last one was 100%.

Of course this is with how Trev describes it, I haven't taken the time to actually look at how it's implemented.

That said if it isn't currently a single roll system for items that share probabilities it should be.

[trevius]

Here is the code that KLS was mentioning where the loot is actually being picked to be added.

void ZoneDatabase::AddLootDropToNPC(NPC* npc,int32 lootdrop_id, ItemList* itemlist) {
	const LootDrop_Struct* lds = GetLootDrop(lootdrop_id);
	if (!lds) {
	 //   LogFile->write(EQEMuLog::Error, "Database Or Memory error GetLootDrop(%i) == 0, npc:%s", lootdrop_id, npc->GetName());
		return;
	}
	if(lds->NumEntries == 0)	//nothing possible to add
		return;

//Removed code for pool looting which isn't applicable to this example

#else
	//non-pool based looting

	int32 r;
	int32 totalchance = 0;
	for (r = 0; r < lds->NumEntries; r++) {
		totalchance += lds->Entries[r].chance;
	}
	uint32 thischance = 0;
	unsigned short k;
	bool found = false;
	
	while(!found) {
		k = MakeRandomInt(0, lds->NumEntries-1);
		
		thischance = lds->Entries[k].chance;
		unsigned int drop_chance = rand() % totalchance;
#if EQDEBUG>=11
			LogFile->write(EQEMuLog::Debug, "Drop chance for npc: %s, total chance:%i this chance:%i, drop roll:%i", npc->GetName(), totalchance, thischance, drop_chance);
#endif
		if (   totalchance == 0 
			|| thischance == 100
			|| thischance == totalchance // only droppable item in loot table
			|| drop_chance < thischance	//can never be true if thischance is 0
			) {
			found = true;
			int32 itemid = lds->Entries[k].item_id;
			
			const Item_Struct* dbitem = GetItem(itemid);
			npc->AddLootDrop(dbitem, itemlist, lds->Entries[k].item_charges, lds->Entries[k].equip_item, false);
			
			break;
			//continue;
		}	//end if it will drop
	}	//end loop
#endif

I am going to read this one over a few more times and see if I can figure out a better explanation of what I think is going wrong and hopefully a fix for it. I don't mean to stir up issues about this, but I do think something seems to be off. I am almost postitive that certain things will have a much higher drop rate even if all items in the table are equal. The way that I stated that KLS cleared up is how I currently am thinking it works. But I will read it over again to make sure. This was my guess as to how it worked even before checking the actual code, but looking at what I have posted here I think that might be correct.

[ChaosSlayer]

well yeah, i don't mind some items droping less than the others but only if they suppose to be more rare than the others =)
otherwise setting up % is complitly pointless =)