I compiled all of the damage into party pools when the monster died and then distributed based on that.
Map creation:
Code:
private final HashMap<Integer, AtomicInteger> takenDamage = new HashMap<>();
Left is character's ID and right is damage dealt.
Tracking portion in damage method:
Code:
int trueDamage = Math.min(hp, damage);
hp -= damage;
if (takenDamage.containsKey(from.getId())) {
takenDamage.get(from.getId()).addAndGet(trueDamage);
} else {
takenDamage.put(from.getId(), new AtomicInteger(trueDamage));
}
Actual calculation code after monster death (gets invoked by killBy later on) in a new method distributeExperience:
Code:
public void distributeExperience(int killerId) {
if (isAlive()) {
return;
}
int exp = getExp();
int totalHealth = getMaxHp();
Map<Integer, Integer> expDist = new HashMap<>();
Map<Integer, Integer> partyExp = new HashMap<>();
// 80% of pool is split amongst all the damagers
for (Entry<Integer, AtomicInteger> damage : takenDamage.entrySet()) {
expDist.put(damage.getKey(), (int) (0.80f * exp * damage.getValue().get() / totalHealth));
}
map.getCharacterReadLock().lock(); // avoid concurrent mod
try {
Collection<MapleCharacter> chrs = map.getCharacters();
for (MapleCharacter mc : chrs) {
if (expDist.containsKey(mc.getId())) {
boolean isKiller = mc.getId() == killerId;
int xp = expDist.get(mc.getId());
if (isKiller) {
xp += exp / 5;
}
MapleParty p = mc.getParty();
if (p != null) {
int pID = p.getId();
int pXP = xp + (partyExp.containsKey(pID) ? partyExp.get(pID) : 0);
partyExp.put(pID, pXP);
} else {
giveExpToCharacter(mc, xp, isKiller, 1);
}
}
}
} finally {
map.getCharacterReadLock().unlock();
}
for (Entry<Integer, Integer> party : partyExp.entrySet()) {
distributeExperienceToParty(party.getKey(), party.getValue(), killerId, expDist);
}
}
distributeExperienceToParty
Code:
private void distributeExperienceToParty(int pid, int exp, int killer, Map<Integer, Integer> expDist) {
LinkedList<MapleCharacter> members = new LinkedList<>();
map.getCharacterReadLock().lock();
Collection<MapleCharacter> chrs = map.getCharacters();
try {
for (MapleCharacter mc : chrs) {
if (mc.getPartyId() == pid) {
members.add(mc);
}
}
} finally {
map.getCharacterReadLock().unlock();
}
final int minLevel = getLevel() - 5;
int partyLevel = 0;
int leechMinLevel = 0;
for (MapleCharacter mc : members) {
if (mc.getLevel() >= minLevel) {
leechMinLevel = Math.min(mc.getLevel() - 5, minLevel);
}
}
int leechCount = 0;
for (MapleCharacter mc : members) {
if (mc.getLevel() >= leechMinLevel) {
partyLevel += mc.getLevel();
leechCount++;
}
}
for (MapleCharacter mc : members) {
int id = mc.getId();
int level = mc.getLevel();
if (expDist.containsKey(id)
|| level >= leechMinLevel) {
boolean isKiller = killer == id;
int xp = (int) (exp * 0.80f * level / partyLevel);
if (isKiller) {
xp += (exp * 0.20f);
}
giveExpToCharacter(mc, xp, isKiller, leechCount);
}
}
}
And giveExpToCharacter party distribution:
Code:
final int partyModifier = numExpSharers > 1 ? (110 + (5 * (numExpSharers - 2))) : 0;
...
if (partyModifier > 0) {
partyExp = (int) (personalExp * ServerConstants.PARTY_EXPERIENCE_MOD * partyModifier / 1000f);
}
And finally the code where it uses everything above in killBy(MapleCharacter)
Code:
distributeExperience(killer != null ? killer.getId() : 0);
That formula also changed later on to 80:20 which splits the experience 80% damage and 20% last hit between foreign parties. This is further split by local party as 80% of the gain by level and 20% by last hit (this may be most damage on the party level in the actual server, but I was lazy and various online sources weren't clear about this). Also, I think that the killer is supposed to get the full 20% of the EXP rather than 20% of the party pool which is added on primarily because your party can potentially get a larger piece of that 20% than maybe someone would expect.
I may be off in some details because I have not looked at your code in detail, just looking through it.
Let N = number of characters in map
Let M = number of parties in map
Let K = number of people who actually hit the monster
Let T = number of AttackerEntries in odinms
--
In your way, you go through every character in the map, even if they didn't hit the monster -- O(N) and populate a HashMap with all of the parties.
Then, for every party, you go through all the characters in the map again (?!) to check if they are in a party -- O(M * N)
I haven't stepped through your code too much, but it looks like you may not give bonus exp to party members who have not hit the monster, or are giving bonus exp to party members who aren't in the map. So your algorithm is O(M*N) for every monster, even if most players and parties in the map don't hit the monster, and MAY have a bug for an edge case.
Now compare to Odin's way.
At each hit, if an AttackerEntry doesn't exist, then it's made and added, else, it's gotten and added to (this can use a HashMap to be O(1) amortized) -- O(T).
The aggregation happens as damage is done, so all of the computation is O(1).
Then, when the monster dies, for all AttackerEntries, compute the damage ratio: O(T) (which is almost always <= O(N)). During computation for PartyAttackerEntry, the party is already known and the attackers are already known. This eliminates the O(M * N) computation.
Almost everything is done in constant time, except for the actual distribution of exp, which is Omega-bounded by K anyway.
You also use some janky external locking which I do not recommend at all. It's extremely error prone and is not worth just creating a new ImmutableSet or something in a threadsafe way. Also, unless you keep the Odin way of externally synchronizing on the monster during damage/kill (which I don't like), your code may not be threadsafe.
This isn't a jab at your code, but Odin's way is actually one of the most optimal ways to do this. Looking back at original OdinMS code, there is one class (OnePartyAttacker) which may be a little redundant. I didn't use it, but I was also implementing this like 4 years ago when I didn't know nearly as much as I do now, and if I was in this headspace again I might even use it.
