Imperium

W jaskiniowym dziale znajduje się tabela z doświadczeniem potrzebnym bohaterowi do awansowania na następny poziom (http://h2.heroes.net.pl/mechanika/doswiadczenie). Miałem okazję zerknąć sobie dzisiaj na zdekompilowany kod dwójki (https://github.com/jkoppel/project-ironfist/tree/master/src/raw_decompiled) i naszło mnie na sprawdzenie, jak wygląda formuła na liczenie doświadczenia. Oto ona:

(Ze względu na błąd na forum nie mogę użyć dwóch podkreśleń obok siebie, bo wygląd postu się psuje, więc zamiast nich używam "_._". To samo tyczy się dwóch plusów, więc wstawiam między nimi spację + +).

W grze znajduje się składająca z trzynastu elementów tablica typu _._int16:

_._int16 experienceForLevelTable[] = { 63, 0, 1000, 2000, 3200, 4500, 6000, 7700, 9000, 11000, 13200, 15500, 18500 };

To doświadczenie potrzebne dla poziomów od 1-12 (nie pytajcie, co oznacza "63" dla poziomu 0, też nie wiem). Jak liczona jest reszta? Oto funkcja:

int _._stdcall hero::GetExperience(signed int level)
{
  int result;
  signed int i;
  int resultExp;
  signed int experience;

  if ( level > 12 )
  {
    i = 13;
    experience = (signed _._int64)((double)((signed int)experienceForLevelTable[12]
                                         - (signed int)experienceForLevelTable[11])
                                * 1.2);
    resultExp = experience + experienceForLevelTable[12];
    while ( i < level )
    {
      experience = (signed _._int64)((double)experience * 1.2);
      resultExp += experience;
      + +i;
    }
    result = resultExp;
  }
  else
  {
    result = experienceForLevelTable[level];
  }
  return result;
}

Jest dosyć prosta, ale ją objaśnię. Jeśli następny poziom (parametr level) jest mniejszy niż 13, to funkcja po prostu zwraca wartość z tabeli. W przeciwnym przypadku:

Tworzymy zmienną i o wartości 13 oraz zmienną experience, która wynosi 3600. Mimo tego, że jej wartość jest zawsze taka sama, funkcja liczy ją odejmując od siebie dwunastą wartość z tabeli experienceForLevelTable od wartości jedenastej (czyli 18500 - 15500, czyli 3000) i mnożąc wynik razy 1.2, co zawsze daje 3600. Tak, jest to zupełnie bezsensowne obliczenie, ale kto programistom z NWC zabroni:

i = 13;
experience = (signed _._int64)((double)((signed int)experienceForLevelTable[12]
                                         - (signed int)experienceForLevelTable[11])
                                * 1.2);

Następnie tworzona jest zmienna resultExp, a jej wartość to wyliczone wcześniej experience + ostatnia wartość z tabeli experienceForLevelTable (czyli 3600 + 18500):

resultExp = experience + experienceForLevelTable[12];

Następnie rozpoczynamy pętle, która wykonuje się następnyPoziom - 13 razy (czyli jeśli nasz następny poziom to 25, wykonamy ją 12 razy)

while ( i < level )
{
      [...]
      + +i;
}

W środku pętli wykonywane są dwa obliczenia:

experience = (signed _._int64)((double)experience * 1.2);

experience = experience * 1.2. Wynik zapisywany jest w zmiennej typu int, więc wszystkie wartości po przecinku zostają ucięte. Następnie zmienna resultExp zostaje zwiększana o aktualnie wykalkulowaną wartość zmiennej experience:

resultExp += experience;

Po całkowitym zakończeniu pętli zwracana jest ostateczna wartość resultExp.

Żeby było jaśniej, wyjaśnię to teraz na przykładzie. Załóżmy, że potrzebujemy wyliczyć doświadczenie potrzebne na 25 poziom.

i = 13;
experience = 3600;
resultExp = 22100;

dopóki i jest mniejsze niż 25:

experience = experience * 1.2 (utnij liczby po przecinku)
resultExp = resultExp + experience
i = i + 1

Wykonanie tego obliczenia dwanaście razy da nam wynik 193 044. Jeśli sprawdzimy tabelkę z doświadczeniem potrzebnym na następny poziom, którą zalinkowałem na początku, to jest to właśnie doświadczenie potrzebne na osiągnięcie 25 poziomu.

A zatem formułka to (pomijając zaokrąglenia):

22100 + 3600 * 1,2 (1 + 1,2 + (1,2)^2 + ... + (1,2)^(poz-14))

Sumę ciągu geometrycznego z nawiasu można zwinąć:

22100 + 3600 * 1,2 (((1,2)^(poz-13) - 1)) / (1,2 - 1))

Czyli:

22100 + 21600 * ((1,2)^(poz - 13) - 1)

Co upraszcza się do:

500 + 21600 * (1,2)^(poz - 13)

(Co, jak można sprawdzić, pokrywa się z grubsza z tabelką - im wyższy poziom, tym mocniej będą się rozjeżdżać wyniki przez różnice w zaokrągleniach; na poziomach 13-14 wyniki są dokładne dzięki podzielności liczby 3600 przez 25 (dzięki której wyniki mnożenia przez 1,2 są całkowite), ale już np. na 25. poziomie formuła daje 193087.769682).

Taki wzór da się zaimplementować asymptotycznie optymalniej niż w oryginalnym kodzie (zamiast poz - 13 obrotów pętli wystarczyłby logarytm z tej liczby przy użyciu algorytmu szybkiego potęgowania), ale jako że poziom sam w sobie jest i tak bardzo niską liczbą, nie miałoby to żadnego znaczenia dla wydajności.

Tak, jest to zupełnie bezsensowne obliczenie, ale kto programistom z NWC zabroni

Czy NWC pisało H2 w asemblerze? Zdekompilowany kod może mieć różne dziwactwa wynikające z optymalizacji kompilatora (który mógł na przykład uznać, że lepiej wyliczyć stałą wartość do inicjalizacji zmiennej z dwóch znanych stałych wartości niż stworzyć dodatkową stałą). A może to ktoś z NWC zdecydował, że tak to trzeba optymalizować...? Nie wiem. Nie wydaje mi się, żeby to była ta epoka, żeby nie można było wydzielić czterech bajtów na dodatkową stałą, ale kto wie...

A może też kombinowali z różnymi wartościami w tabeli i zaimplementowali tę linijkę tak a nie inaczej, żeby w razie zmiany modyfikacji trzeba było dokonywać tylko w jednym miejscu (rozsądna praktyka!).

Swoją drogą, czy nie ma szans na to, że ten kod był żywcem skopiowany z H1? Progi wyglądają prawie identycznie, tylko według tabelki z Groty progi po 13. poziomie są przesunięte o 1 punkt.

nie pytajcie, co oznacza "63" dla poziomu 0, też nie wiem

Ja też nie wiem, ale 63 nie wygląda jak losowa liczba (bo to 2^8 -1, czyli 11111111 w zapisie dwójkowym) :)

Dzięki za napisanie wzoru, ja nie jestem dobry z matematyki (planuję to w przyszłości zmienić), to sobie odpuściłem próbowanie.

Hayven

Czy NWC pisało H2 w asemblerze?

Raczej nie. Już Might and Magic 1 chyba było pisane w C (bo C+ + chyba jeszcze wtedy nie było, nie wiem jak z C z Klasami), bo Caneghem mówił w wywiadzie u Matta Bartona, że w asemblerze pisane były tylko nieliczne fragmenty. Więc zgaduję, że gdy pojawił i upowszechnił się C+ +, to korzystali tylko z niego.

Hayven

A może też kombinowali z różnymi wartościami w tabeli i zaimplementowali tę linijkę tak a nie inaczej, żeby w razie zmiany modyfikacji trzeba było dokonywać tylko w jednym miejscu (rozsądna praktyka!).

Ja mam teorię, że na pewnym etapie mogli chcieć, żeby różne klasy bohaterów potrzebowały różnej ilości doświadczenia na awans. Np. łatwiej by było awansować słabego Rycerza lub Czarodziejkę, a trudniej silnego Barbarzyńcę i Czarnoksiężnika. Tak było np. w Might and Magic I, gdzie klasy magiczne awansowały później.

Hayven

Swoją drogą, czy nie ma szans na to, że ten kod był żywcem skopiowany z H1?

Jest bardzo spora, bo w H2 np. dalej jest stara struktura z pięcioma podstawowymi umiejętnościami (https://github.com/jkoppel/project-ironfist/blob/4df6ab5bfe5f5f26ed4f9a911b2082329bc7f789/src/raw_decompiled/HEROES2W.h#L839): Atakiem, Obroną, Mocą, Wiedzą i... Oblężeniem, tak jak było w H1 (ale oblężenie jest niewidoczne). Ale zdekompilowany kod jedynki mają tylko Rosjanie, a ci się prędzej zes... niż ci coś publicznie udostępnią. A samemu nie mam czasu na takie zabawy, więc nie potwierdzę.