1/*
2 * LegacyClonk
3 *
4 * Copyright (c) RedWolf Design
5 * Copyright (c) 2007, Sven2
6 * Copyright (c) 2017-2021, The LegacyClonk Team and contributors
7 *
8 * Distributed under the terms of the ISC license; see accompanying file
9 * "COPYING" for details.
10 *
11 * "Clonk" is a registered trademark of Matthes Bender, used with permission.
12 * See accompanying file "TRADEMARK" for details.
13 *
14 * To redistribute this file separately, substitute the full license texts
15 * for the above references.
16 */
17
18// player info attribute conflict resolving
19// e.g., changing colors if two players have the same
20// "There must be some easier way to do it"(tm)
21
22#include <C4Include.h>
23#include <C4PlayerInfo.h>
24#include <C4GraphicsSystem.h>
25#include <C4Game.h>
26#include <C4Log.h>
27
28#include <C4Random.h>
29
30// number of times trying new player colors
31const int32_t C4MaxPlayerColorChangeTries = 100;
32const int32_t C4MaxPlayerNameChangeTries = 100;
33
34// *** Helpers
35
36uint32_t GenerateRandomPlayerColor(int32_t iTry) // generate a random player color for the iTry'th try
37{
38 // generate a random one biased towards max channel luminance
39 // (for greater color difference and less gray-ish colors)
40 return RGB(r: (std::min)(a: SafeRandom(range: 302), b: 256), g: (std::min)(a: SafeRandom(range: 302), b: 256), b: (std::min)(a: SafeRandom(range: 302), b: 256));
41}
42
43bool IsColorConflict(uint32_t dwClr1, uint32_t dwClr2) // return whether dwClr1 and dwClr2 are closely together
44{
45 // NEW COLOR CONFLICT METHOD: u'v'-distance
46 int R1 = 0xff & (dwClr1 >> 16);
47 int G1 = 0xff & (dwClr1 >> 8);
48 int B1 = 0xff & (dwClr1);
49 int R2 = 0xff & (dwClr2 >> 16);
50 int G2 = 0xff & (dwClr2 >> 8);
51 int B2 = 0xff & (dwClr2);
52 double r1 = 0, g1 = 0, b1 = 0, r2 = 0, g2 = 0, b2 = 0, x1 = 0, y1 = 0, Y1 = 0, x2 = 0, y2 = 0, Y2 = 0, u1 = 0, v1 = 0, u2 = 0, v2 = 0;
53 RGB2rgb(R: R1, G: G1, B: B1, pr: &r1, pg: &g1, pb: &b1);
54 RGB2rgb(R: R2, G: G2, B: B2, pr: &r2, pg: &g2, pb: &b2);
55 rgb2xyY(r: r1, g: g1, b: b1, px: &x1, py: &y1, pY: &Y1);
56 rgb2xyY(r: r2, g: g2, b: b2, px: &x2, py: &y2, pY: &Y2);
57 xy2upvp(x: x1, y: y1, pu: &u1, pv: &v1);
58 xy2upvp(x: x2, y: y2, pu: &u2, pv: &v2);
59 double Y = (Y1 + Y2) / 2.0;
60 double clrdiff = sqrt(x: (u2 - u1) * (u2 - u1) + (v2 - v1) * (v2 - v1)) * Y * Y * 150;
61 double lumdiff = (Abs<double>(val: Y2 - Y1) / std::max<double>(a: Y * Y * 5, b: 0.5)) / 0.10;
62 return clrdiff + lumdiff < 1.0;
63}
64
65// conflict resolver
66class C4PlayerInfoListAttributeConflictResolver
67{
68private:
69 // info packets that need to be checked yet
70 // info packets sorted by check priority, i.e. last ones checked first
71 C4ClientPlayerInfos **ppCheckInfos;
72 int32_t iCheckInfoCount;
73
74 // lists to be checked against
75 const C4PlayerInfoList &rPriCheckList, &rSecCheckList;
76 C4ClientPlayerInfos *pSecPacket;
77
78 // current attribute being checked
79 C4PlayerInfo::Attribute eAttr;
80
81 // handling of current packet to be adjusted
82 C4ClientPlayerInfos *pResolvePacket;
83 bool fAnyChange;
84
85 // handling of current info to be adjusted
86 C4PlayerInfo *pResolveInfo;
87 bool fCurrentConflict, fOriginalConflict, fAlternateConflict;
88 C4ClientPlayerInfos *pLowPrioOriginalConflictPacket, *pLowPrioAlternateConflictPacket;
89
90public:
91 C4PlayerInfoListAttributeConflictResolver(C4PlayerInfoList &rPriCheckList, const C4PlayerInfoList &rSecCheckList, C4ClientPlayerInfos *pSecPacket);
92 ~C4PlayerInfoListAttributeConflictResolver();
93
94private:
95 void ReaddInfoForCheck(C4ClientPlayerInfos *pCheckAdd); // temp readd info to be checked, because another packet reset its attribute with higher priority
96 int32_t GetAttributePriorityDifference(const C4PlayerInfo *pInfo1, const C4ClientPlayerInfos *pPck1, const C4PlayerInfo *pInfo2, const C4ClientPlayerInfos *pPck2);
97 bool IsAttributeConflict(const C4PlayerInfo *pInfo1, const C4PlayerInfo *pInfo2, C4PlayerInfo::AttributeLevel eLevel);
98 void MarkConflicts(C4ClientPlayerInfos &rCheckPacket, bool fTestOriginal);
99 void MarkConflicts(const C4PlayerInfoList &rCheckList, bool fTestOriginal);
100 void ResolveInInfo();
101 void ResolveInPacket();
102
103public:
104 void Resolve(); // action go!
105};
106
107// resolve function calling resolver
108void C4PlayerInfoList::ResolvePlayerAttributeConflicts(C4ClientPlayerInfos *pSecPacket)
109{
110 C4PlayerInfoListAttributeConflictResolver r(*this, Game.RestorePlayerInfos, pSecPacket);
111 r.Resolve();
112}
113
114// implementation of conflict resolver
115C4PlayerInfoListAttributeConflictResolver::C4PlayerInfoListAttributeConflictResolver(C4PlayerInfoList &rPriCheckList, const C4PlayerInfoList &rSecCheckList, C4ClientPlayerInfos *pSecPacket)
116 : ppCheckInfos(nullptr), iCheckInfoCount(0), rPriCheckList(rPriCheckList), rSecCheckList(rSecCheckList), pSecPacket(pSecPacket)
117{
118 // prepare check array
119 int32_t iMaxCheckCount = rPriCheckList.GetInfoCount() + !!pSecPacket;
120 if (!iMaxCheckCount) return;
121 ppCheckInfos = new C4ClientPlayerInfos *[iMaxCheckCount];
122 // resolve all primary packets in reverse order, so late clients have lower priority
123 for (int32_t i = 0; i < rPriCheckList.GetInfoCount(); ++i)
124 {
125 C4ClientPlayerInfos *pInfos = rPriCheckList.GetIndexedInfo(iIndex: i);
126 if (pInfos != pSecPacket) // skip packet if it was explicitly passed for update
127 ppCheckInfos[iCheckInfoCount++] = pInfos;
128 else
129 {
130 // if the additional packet is in the list already, it needn't be a check packed (only resolve packet)
131 this->pSecPacket = nullptr;
132 }
133 }
134 // must check sec packet first
135 if (pSecPacket) ppCheckInfos[iCheckInfoCount++] = pSecPacket;
136}
137
138C4PlayerInfoListAttributeConflictResolver::~C4PlayerInfoListAttributeConflictResolver()
139{
140 delete[] ppCheckInfos;
141}
142
143void C4PlayerInfoListAttributeConflictResolver::ReaddInfoForCheck(C4ClientPlayerInfos *pCheckAdd)
144{
145 // do not add twice<
146 for (int32_t i = 0; i < iCheckInfoCount; ++i) if (ppCheckInfos[i] == pCheckAdd) return;
147 // readd it - must have been in there before, so array is large enough
148 // and it must have been at the head of the list
149 ppCheckInfos[iCheckInfoCount++] = pCheckAdd;
150}
151
152int32_t C4PlayerInfoListAttributeConflictResolver::GetAttributePriorityDifference(const C4PlayerInfo *pInfo1, const C4ClientPlayerInfos *pPck1, const C4PlayerInfo *pInfo2, const C4ClientPlayerInfos *pPck2)
153{
154 // return info1.prio - info2.prio
155 // highest priority if joined already and attributes may not be changed
156 if (pInfo1->IsJoined())
157 return pInfo2->IsJoined() ? 0 : +1;
158 if (pInfo2->IsJoined())
159 return -1;
160 // Computer players lower priority than user players
161 int32_t iTypeDiff = int(pInfo2->GetType()) - int(pInfo1->GetType());
162 if (iTypeDiff) return iTypeDiff;
163 // All unjoined: Priority by score
164 int32_t iScoreDiff = pInfo1->getLeagueScore() - pInfo2->getLeagueScore();
165 if (iScoreDiff) return iScoreDiff;
166 // equal priority
167 return 0;
168}
169
170bool C4PlayerInfoListAttributeConflictResolver::IsAttributeConflict(const C4PlayerInfo *pInfo1, const C4PlayerInfo *pInfo2, C4PlayerInfo::AttributeLevel eLevel)
171{
172 // check for conflict of colors and names
173 if (eAttr == C4PlayerInfo::PLRATT_Color)
174 {
175 uint32_t dwClr1 = pInfo1->GetColor(), dwClr2 = 0;
176 switch (eLevel)
177 {
178 case C4PlayerInfo::PLRAL_Current: dwClr2 = pInfo2->GetColor(); break;
179 case C4PlayerInfo::PLRAL_Original: dwClr2 = pInfo2->GetOriginalColor(); break;
180 case C4PlayerInfo::PLRAL_Alternate: dwClr2 = pInfo2->GetAlternateColor(); break;
181 }
182 return IsColorConflict(dwClr1, dwClr2);
183 }
184 else if (eAttr == C4PlayerInfo::PLRATT_Name)
185 {
186 const char *szName1 = pInfo1->GetName(), *szName2 = "";
187 switch (eLevel)
188 {
189 case C4PlayerInfo::PLRAL_Current: szName2 = pInfo2->GetName(); break;
190 case C4PlayerInfo::PLRAL_Original: szName2 = pInfo2->GetOriginalName(); break;
191 case C4PlayerInfo::PLRAL_Alternate: break; // there is no definable alternate
192 }
193 return SEqualNoCase(szStr1: szName1, szStr2: szName2);
194 }
195 return false;
196}
197
198void C4PlayerInfoListAttributeConflictResolver::MarkConflicts(C4ClientPlayerInfos &rCheckPacket, bool fTestOriginal)
199{
200 C4PlayerInfo *pCheckAgainstInfo;
201 // check current and original attribute against all player infos
202 for (int32_t j = 0; pCheckAgainstInfo = rCheckPacket.GetPlayerInfo(iIndex: j); ++j)
203 {
204 if (pCheckAgainstInfo->IsUsingAttribute(eAttr)) if (!pResolveInfo->GetID() || pResolveInfo->GetID() != pCheckAgainstInfo->GetID()) if (pResolveInfo != pCheckAgainstInfo)
205 {
206 // current conflict is marked only if the checked packet has same of lower priority than the one compared to
207 // if the priority is higher, the attribute shall be changed in the other, low priority info instead!
208 bool fHasHigherPrio = (GetAttributePriorityDifference(pInfo1: pResolveInfo, pPck1: pResolvePacket, pInfo2: pCheckAgainstInfo, pPck2: &rCheckPacket) > 0);
209 if (!fHasHigherPrio)
210 if (IsAttributeConflict(pInfo1: pCheckAgainstInfo, pInfo2: pResolveInfo, eLevel: C4PlayerInfo::PLRAL_Current))
211 fCurrentConflict = true;
212 if (fTestOriginal)
213 {
214 if (IsAttributeConflict(pInfo1: pCheckAgainstInfo, pInfo2: pResolveInfo, eLevel: C4PlayerInfo::PLRAL_Original))
215 if (fHasHigherPrio && !fOriginalConflict && !pLowPrioOriginalConflictPacket)
216 {
217 // original attribute is taken by a low prio packet - do not mark an original conflict, but remember the packet
218 // that's blocking it
219 pLowPrioOriginalConflictPacket = &rCheckPacket;
220 }
221 else
222 {
223 // original attribute is taken by either one higher/equal priority by packet, or by two low prio packets
224 // in this case, don't revert to original
225 pLowPrioOriginalConflictPacket = nullptr;
226 fOriginalConflict = true;
227 }
228 if (IsAttributeConflict(pInfo1: pCheckAgainstInfo, pInfo2: pResolveInfo, eLevel: C4PlayerInfo::PLRAL_Alternate))
229 if (fHasHigherPrio && !fAlternateConflict && !pLowPrioAlternateConflictPacket)
230 pLowPrioAlternateConflictPacket = &rCheckPacket;
231 else
232 fAlternateConflict = true;
233 }
234 }
235 }
236}
237
238void C4PlayerInfoListAttributeConflictResolver::MarkConflicts(const C4PlayerInfoList &rCheckList, bool fTestOriginal)
239{
240 // mark in all infos of given list...
241 for (int32_t i = 0; i < rCheckList.GetInfoCount(); ++i)
242 MarkConflicts(rCheckPacket&: *rCheckList.GetIndexedInfo(iIndex: i), fTestOriginal);
243}
244
245void C4PlayerInfoListAttributeConflictResolver::ResolveInInfo()
246{
247 // trial-loop for assignment of new player colors/names
248 int32_t iTries = 0;
249 // original/alternate conflict evaluated once only
250 fOriginalConflict = false;
251 fAlternateConflict = (eAttr == C4PlayerInfo::PLRATT_Name) || !pResolveInfo->GetAlternateColor(); // mark as conflict if there is no alternate color/name
252 for (;;)
253 {
254 // check against all other player infos, and given info, too (may be redundant)
255 fCurrentConflict = false;
256 pLowPrioOriginalConflictPacket = pLowPrioAlternateConflictPacket = nullptr;
257 MarkConflicts(rCheckList: rPriCheckList, fTestOriginal: !iTries);
258 // check secondary list, too. But only for colors, not for names, because secondary list is Restore list
259 // and colors are retained in restore while names are always taken from new joins
260 if (eAttr != C4PlayerInfo::PLRATT_Name) MarkConflicts(rCheckList: rSecCheckList, fTestOriginal: !iTries);
261 // and mark conflicts in additional packet that' sbeen passed
262 if (pSecPacket) MarkConflicts(rCheckPacket&: *pSecPacket, fTestOriginal: !iTries);
263 // color conflict resolving
264 if (eAttr == C4PlayerInfo::PLRATT_Color)
265 {
266 // original color free but not used?
267 if (!iTries)
268 {
269 if (pResolveInfo->GetColor() != pResolveInfo->GetOriginalColor())
270 if (!fOriginalConflict)
271 {
272 // revert to original color!
273 pResolveInfo->SetColor(pResolveInfo->GetOriginalColor());
274 // in case a lower priority packet was blocking the attribute, re-check that packet
275 // note that the may readd the current resolve packet, but the conflict will occur with the
276 // lower priority packet in the next loop
277 if (pLowPrioOriginalConflictPacket) ReaddInfoForCheck(pCheckAdd: pLowPrioOriginalConflictPacket);
278 // done with this player (breaking the trial-loop)
279 break;
280 }
281 // neither original nor alternate color used but alternate color free?
282 else if (pResolveInfo->GetColor() != pResolveInfo->GetAlternateColor() && !fAlternateConflict)
283 {
284 // revert to alternate
285 pResolveInfo->SetColor(pResolveInfo->GetAlternateColor());
286 if (pLowPrioAlternateConflictPacket) ReaddInfoForCheck(pCheckAdd: pLowPrioAlternateConflictPacket);
287 // done with this player (breaking the trial-loop)
288 break;
289 }
290 }
291 // conflict found?
292 if (!fCurrentConflict)
293 // done with this player, then - break the trial-loop
294 break;
295 // try to get a new, unused player color
296 uint32_t dwNewClr;
297 if (++iTries > C4MaxPlayerColorChangeTries)
298 {
299 Log(id: C4ResStrTableKey::IDS_PRC_NOREPLPLRCLR, args: pResolveInfo->GetName() ? pResolveInfo->GetName() : "<NONAME>");
300 // since there's a conflict anyway, change to original
301 pResolveInfo->SetColor(pResolveInfo->GetOriginalColor());
302 break;
303 }
304 else
305 dwNewClr = GenerateRandomPlayerColor(iTry: iTries);
306 pResolveInfo->SetColor(dwNewClr);
307 }
308 else // if (eAttr == PLRATT_Name)
309 {
310 // name conflict resolving
311 // original name free but not used?
312 if (!SEqualNoCase(szStr1: pResolveInfo->GetName(), szStr2: pResolveInfo->GetOriginalName()))
313 if (!fOriginalConflict)
314 {
315 // revert to original name!
316 pResolveInfo->SetForcedName(nullptr);
317 if (pLowPrioOriginalConflictPacket) ReaddInfoForCheck(pCheckAdd: pLowPrioOriginalConflictPacket);
318 // done with this player (breaking the trial-loop)
319 break;
320 }
321 // conflict found?
322 if (!fCurrentConflict)
323 // done with this player, then - break the trial-loop
324 break;
325 // generate new name by appending an index
326 if (++iTries > C4MaxPlayerNameChangeTries) break;
327 pResolveInfo->SetForcedName(std::format(fmt: "{} ({})", args: pResolveInfo->GetOriginalName(), args: iTries + 1).c_str());
328 }
329 }
330}
331
332void C4PlayerInfoListAttributeConflictResolver::ResolveInPacket()
333{
334 // check all player infos
335 fAnyChange = false;
336 int32_t iCheck = 0;
337 while (pResolveInfo = pResolvePacket->GetPlayerInfo(iIndex: iCheck++))
338 {
339 // not already joined? Joined player must not change their attributes!
340 if (pResolveInfo->HasJoined()) continue;
341 uint32_t dwPrevColor = pResolveInfo->GetColor();
342 StdStrBuf sPrevForcedName; sPrevForcedName.Copy(pnData: pResolveInfo->GetForcedName());
343 // check attributes: Name and color
344 for (eAttr = C4PlayerInfo::PLRATT_Color; eAttr != C4PlayerInfo::PLRATT_Last; eAttr = static_cast<C4PlayerInfo::Attribute>(eAttr + 1))
345 {
346 if (eAttr == C4PlayerInfo::PLRATT_Color)
347 {
348 // no color change in savegame associations
349 if (pResolveInfo->GetAssociatedSavegamePlayerID()) continue;
350 // or forced team colors
351 if (Game.Teams.IsTeamColors() && Game.Teams.GetTeamByID(iID: pResolveInfo->GetTeam())) continue;
352 }
353 else if (eAttr == C4PlayerInfo::PLRATT_Name)
354 {
355 // no name change if a league name is used
356 if (pResolveInfo->getLeagueAccount() && *pResolveInfo->getLeagueAccount()) continue;
357 }
358 // not if attributes are otherwise fixed (e.g., for script players)
359 if (pResolveInfo->IsAttributesFixed()) continue;
360 // resolve in this info
361 ResolveInInfo();
362 }
363 // mark change for return value if anything was changed
364 if (pResolveInfo->GetColor() != dwPrevColor || (pResolveInfo->GetForcedName() != sPrevForcedName))
365 fAnyChange = true;
366 // next player info check
367 }
368 // mark update if anything was changed
369 if (fAnyChange) pResolvePacket->SetUpdated();
370}
371
372void C4PlayerInfoListAttributeConflictResolver::Resolve()
373{
374 // resolve in all packets in list until list is empty
375 // resolving in reverse order, because highest priority first in the list
376 while (iCheckInfoCount)
377 {
378 pResolvePacket = ppCheckInfos[--iCheckInfoCount];
379 ResolveInPacket();
380 }
381}
382