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).

[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

[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

[ChaosSlayer]

I decided to bump this to see if there have been any progress on improving the RND code since?
thanks =)

[GeorgeS]

In .net and other programing languages you require to create a randomnumber seed, and most use a timer/current time to randomize to it, that way you don't get the same numbers each loop.

Then you would get a better gaussian looking distribution. It still requires quite a bit of sampling to get this however, as mentioned before.

In my D2 loot editor, (random loot) - quite a few people have asked me why specific items drop too often, and others hardly at all. I could not blame it on the loot order or the %drop either. Trev's argument seems likely, and may be an idiosyncrasy of this C++ compiler...

GeorgeS

[iggi]

Couldn't you do it like this:


while(number of drops > 0){
randnum % loottablesize = item picked
randnum % 10 = (actual)randnumber
if ((actual)randnumber <= (probability*10) ){ \\assuming probability is in decimal
drop(item picked);
}
number of drops--;
}

This would allow a weighted random drop with number of drops scaling with the number of items in the loot table (which generally correlates w/raid bosses) However you want to determine the number of drops though is up to you and can be removed. Also, the number of drops can be scaled by adding a multiplier to adjust as needed.

p.s.- Don't trust me, just ponder on it, I have little experience in programming, that's just how I was taught, poorly adapted that is.

[iggi]

EDIT- This got deleted in my previous post when editing:

randnum % loottablesize = number of drops
(optional)number of drops = number of drops * frequency modifier
while(number of drops > 0){
randnum % loottablesize = item picked
randnum % 10 = (actual)randnumber
if ((actual)randnumber <= (probability*10) ){ \\assuming probability is in decimal
drop(item picked);
}
number of drops--;
}

If you wanted to add a weight to number of drops, you can always use this pseudo code again accounting for the weighted drops instead of probability of drops.

[trevius]

After looking at this again, maybe trying a slight modification like this would work.

Change the part in Red here from zone/loottables.cpp:

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

Into the part in blue here:

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;
	
	k = MakeRandomInt(0, lds->NumEntries-1);

	while(!found) {
		if (k > (lds->NumEntries - 1)) {
			k = 0;
		}

		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
		k++;
	}	//end loop
#endif

Basically, what that will do is to make it so it only runs the RNG 1 time to decide the starting point to loop through the table entries. That is apposed to using the RNG every time it loops to chose a random entry to check if it will drop or not.

If there is an issue with the loot drop system, as far as I can tell, it would have to be due to the RNG itself. I think it is pretty well-known that the RNG is never as random as it really should be. This will at least prevent the RNG from repeatedly hitting the same drop over and over as it decides loot. There will still be RNG involved, but this should at least force it to continue down the list after it selects the random starting entry to check first.

I have personally seen some drop issues that point to there being a definite problem with drop rates. I think that it may work fine when repopping the same NPC over and over as in the example Cavedude gave. But, my theory is that the problem is something to do with server or zone restarts that cause it to give preference to certain drops for the first time a NPC spawns after a zone/server restart. I don't know why that would be the case, but that is just my best guess.

Either way, it might be worth giving this a long test to see if there is any improvement through feedback of players and testing and such.

[trevius]

Well, I got this change added to run on Storm Haven currently for the past week and it seems to be working at least as well as the original way. I won't put this change on the SVN without approval from KLS or Derision or someone like that, though. I want them to see what they think first before changing something this essential that has the potential to cause issues with players.

I think that this might be a better way to handle doing loot tables. Instead of the previous way, where it used the RNG every time to select which item to check if it will drop, it would now only RNG to pick the item in the list to start checking at and then continue down the list and cycle through it until one of them is successfully picked. This just takes 1 step of the RNG out of the picture and since the RNG is known to not truely be as random as it should be, I think that would be a good thing to help make drop rates closer to being exactly what they should be.

While discussing this on my own forums, I came up with an idea that might be useful. The idea would be to write a new quest command that will let you get a list of all of the items currently on an NPC at any particular time. So, you could use it to get a list of items on an NPC at the time it is killed and then use quest::write() to write the list to a file. By doing this, you could log certain NPCs that are killed regularly and then over time you could get enough data to have a pretty clear picture on if drop rates are actually what they should be. Another use of being able to get the list of loot on an NPC would be to keep track of what drops were on an NPC when it was killed, for certain high end bosses. I know I have had cases where zone crashes were occurring due to certain issues and people wouldn't get to loot items. At least with this, I would have been able to confirm which items actually dropped or should have dropped before the crash occurred.

Now, I just gotta think of a way to get that list and make it into something that can be used in perl. Maybe exporting them to an array would work, or even just set them all into string or something.