03-01-2004, 09:37 PM
(This post was last modified: 03-01-2004, 09:41 PM by hakai_no_tenshi.)
Jarulf,Feb 27 2004, 12:53 PM Wrote:What is your actual algorithm for going through TCs calculting the probabilities? (If you want to keep it generally secret, perhaps discussions with PM would be OK). I think the recursive way I have done it is good, simple and works. For the negative pick AND going above 6 items, it need to be adjusted (I think it handle all other cases except possibly handling quality determination if it various with how you get to an item).I have no problem sharing the code but I use some rather intense algorithms/data structures as well as lots of C++ subclassing to deal with all the various versions. I also use recursive function calls although I originally planned on using an alternate heap structure in case the function stack was too deep for older machines. The basics here is that I construct a tree graph for the entire TC system where the terminating leaves of the tree are atomic TCs, regular items or named items e.g uniques/sets. At the end of the calculations, the atomic TCs are expanded.
Negative picks are branch points so I construct alternate pathways for these. The core code to do the computation is below but there are so many auxillary functions and data structures involved that you would need to get the code from me if you are interested. It is within the Drop Calculator GUI that calls are made to compute final chances of an item being of a specific quality.
--T
Code:
int DropCalc::NoDrop(int baseNoDrop, int remainingTC, int players)
{
if((players == 1) || (baseNoDrop == 0))
return baseNoDrop;
double nodropfrac = (double)baseNoDrop / (baseNoDrop + remainingTC); // p1 nodrop fraction
double newnodropfrac = pow(nodropfrac, 1.0*players); // raise to power of players
int newnodrop = int(remainingTC * newnodropfrac / (1.0 - newnodropfrac));
return newnodrop;
}
void DropCalc::ComputeBaseDrops(int players, BOOL xp_armo, BOOL xp_weap, BOOL xp_mele, BOOL xp_bow)
{
// Compute the base item probabilities
std::map<CString, TreasureClass *>::iterator iter;
std::map<CString, TreasureClass *>::iterator end = m_tcMap.end();
for (iter=m_tcMap.begin(); iter != end; iter++)
{
TreasureClass *tc = iter->second;
// Don't bother if no-one drops directly from this
if(tc->GetMonsterSize() == 0)
continue;
tc_entry_t dummy;
dummy.atom = NULL;
dummy.item = NULL;
dummy.name = tc->Name();
dummy.prob = 1;
dummy.tc = tc;
ProbabilityDrop(1, tc, &dummy, 1.0, players);
}
m_Compute = TRUE;
if(xp_armo && (m_expandedArmor == FALSE))
{
// Expand the armor atomic TC
ExpandAtomicTC(armo, 30);
m_expandedArmor = TRUE;
}
if(xp_weap && (m_expandedWeapon == FALSE))
{
// Expand the weapon atomic TC
ExpandAtomicTC(weap, 30);
m_expandedWeapon = TRUE;
}
if(xp_mele && (m_expandedMelee == FALSE))
{
// Expand the melee atomic TC
ExpandAtomicTC(mele, 30);
m_expandedMelee = TRUE;
}
if(xp_bow && (m_expandedBow == FALSE))
{
// Expand the bow atomic TC
ExpandAtomicTC(bow, 30);
m_expandedBow = TRUE;
}
}
void DropCalc::ProbabilityDrop(int base_pick, TreasureClass *base_tc, tc_entry_t *tcent, double base_prob, int players)
{
// Can do various things here depending on what it is
TreasureClass *tc = tcent->tc;
AtomicTC *atom = tcent->atom;
item_entry_t *item = tcent->item;
if(tc != NULL)
{
// This is a link to a TC
// Update bonuses
int unique = tc->Unique();
int set = tc->Set();
int rare = tc->Rare();
int magic = tc->Magic();
if(unique > base_tc->Unique())
base_tc->Unique(unique);
if(set > base_tc->Set())
base_tc->Set(set);
if(rare > base_tc->Rare())
base_tc->Rare(rare);
if(magic > base_tc->Magic())
base_tc->Magic(magic);
int i, j, npicks, len;
double prob = 1.0;
if(tc->Picks() < 0)
{
// Special case
npicks = -(tc->Picks());
if(npicks > 6)
npicks = 6;
len = tc->GetTCSize();
for(i=0; i<len; i++)
{
tc_entry_t *tc_entry = tc->GetTCEntry(i);
for(j=0; (npicks > 0) && (j < tc_entry->prob); j++, npicks--);
TreasureClass *new_base_tc = base_tc;
if(tc_entry->tc != NULL)
{
// Make switch
new_base_tc = tc_entry->tc;
}
prob = base_prob;
ProbabilityDrop(j*base_pick, new_base_tc, tc_entry, prob, players);
}
}
else
{
npicks = tc->Picks();
if(npicks > 6)
npicks = 6;
int adj_no_drop = NoDrop(tc->NoDrop(), tc->DropSum(), players);
double denom = 1.0 / (adj_no_drop + tc->DropSum());
len = tc->GetTCSize();
for(i=0; i<len; i++)
{
tc_entry_t *tc_entry = tc->GetTCEntry(i);
prob = (tc_entry->prob*denom)*base_prob;
ProbabilityDrop(npicks*base_pick, base_tc, tc_entry, prob, players);
}
}
}
else if(atom != NULL)
{
// Terminating TC which is an atomic TC
// Look for the TC in the drop map
CString name = base_tc->Name();
std::map< pair<CString, int> , drop_prob_t> &drop = atom->DropList();
pair<CString, int> p(name, base_pick);
std::map< pair<CString,int> , drop_prob_t>::iterator i_drop = drop.find(p);
drop_prob_t item_drop;
if(i_drop == drop.end())
{
// Create new entry
item_drop.prob = base_prob;
item_drop.tc = base_tc;
item_drop.npick = base_pick;
drop.insert(std::pair< pair<CString,int> , drop_prob_t> (p, item_drop));
}
else
{
// Add on probability
i_drop->second.prob += base_prob;
}
}
else if(item != NULL)
{
// Terminating TC which is an item
// Look for the TC in the drop map
CString name = base_tc->Name();
pair<CString, int> p(name, base_pick);
std::map< pair<CString,int> , drop_prob_t>::iterator i_drop = item->drop.find(p);
drop_prob_t item_drop;
if(i_drop == item->drop.end())
{
// Create new entry
item_drop.prob = base_prob;
item_drop.tc = base_tc;
item_drop.npick = base_pick;
item->drop.insert(std::pair< pair<CString,int> , drop_prob_t> (p, item_drop));
}
else
{
// Add on probability
i_drop->second.prob += base_prob;
}
}
}