Balansowanie podstawowych statystyk w grze fabularnej

Ze dwie notki temu wspominałem coś o rozmyślaniach na temat balansowania parametrów potworów i nie tylko w grach typu cRPG. Chciałem jednak zastrzec, że rozważania te nie są raczej materiałem na większy artykuł – stanowią one pewny punkt podparcia, ideę, ale nie wiem, jakby wyglądała rozgrywka, gdybyśmy trzymali się tych zasad w stu procentach.

Już wcześniej wspominałem, że całość będzie się opierała na tzw. matchingu, czyli po swojsku – dopasowywaniu. Najpierw wersja bardziej naukowo brzmiąca.

Niech będzie dany zbiór W broni dostępnych w grze, zbiór L poziomów doświadczenia, które postać może zdobyć, zbiór M potworów, które można napotkać i zbiór WisiMiTo, który nie jest nam potrzebny, ale fajnie wygląda. Dopasowanie (dokonywane przed późniejszymi transformacjami) polega na znalezieniu takich podzbiorów A1, A2,…, An, z których każdy zawierałby od 1 do |M| elementów ze zbioru M, od 1 do |L| elementów ze zbioru L i 1 element ze zbioru W. Nie, elementów ze zbioru WisiMiTo nie używamy.

Zrozumiałe? Dla mnie nie bardzo, przynajmniej na pierwszy rzut oka. Dlatego podaję bardziej ludzką wersję.

Wybieramy jedną sztukę broni (logicznie rzecz biorąc, ilość dostępnego oręża będzie większa niż przeciwników do eksterminowania), oznaczamy ją X i teraz mniej więcej projektujemy, przewidujemy czy wręcz strzelamy, jakie potworki powszechnie będą napotykały gracza w momencie, kiedy będzie on używał głównie broni X. Mało tego – powinniśmy ustalić, jakie, przy standardowym sposobie prowadzenia rozgrywki, poziomy doświadczenia będzie mógł uzyskać gracz na tym etapie gry. Pod pojęciem “standardowy sposób prowadzenia rozgrywki” rozumiem normalne przechodzenie głównego wątku z normalną (średnią) dozą wykonywanych zadań dodatkowych. Nie zajmujemy się sytuacjami, kiedy gracz w Diablo II wpisuje “Players 8” i zagląda do każdego zakątka krainy. Wiem, bo sam tak robię, a ostatnio powróciłem do Diabełka – mówcie co chcecie, ale piękna gra.

Prawdopodobnie nadal dla niektórych to tłumaczenie będzie czarną magią, choć może nieco rozjaśnić sytuację. Dlatego przygotowałem przykład. W grze mamy do czynienia z kreaturami takimi jak (uszeregowane w kolejności od najsłabszego do najsilniejszego): Imp, Diablik, Gog, Ogar, Cerver, Demon, Czart, Ifryt, Miryd, Diabeł. Swoją drogą, pewnie niektórzy już wiedzą, z jakiej gry czerpałem inspirację na taki zestaw, ale mniejsza o to. Walka z tymi przyjemniaczkami będzie dla gracza łatwiejsza dzięki czterem rodzajom oręża: sztylet, miecz, topór, Święty Granat Ręczny Alleluja. Jakaś żywiołowo zdobyta wena twórcza podpowiada nam również, iż możliwe poziomy doświadczenia mieszczą się w przedziale [0, 8], gdzie poziom 0. jest startowy.

Oto przykładowe dopasowanie przy takich danych, a poniżej analiza, która powinna wyjaśnić to, co jest niewyjaśnione. W dalszej części będę często stosował termin “etap” dla określenia paru potworów przypisanych do jednej sztuki broni i paru poziomów doświadczenia (zatem poniżej mamy cztery etapy).

Należy to rozumieć następująco:

• Imp, Diablik i Gog to najsłabsze potwory (aczkolwiek Gog wykazuje już pewne tendencje do ukatrupienia gracza). Na etapie, w którym spotykamy te kreatury, mamy do dyspozycji głównie sztylet (ewentualnie coś innego, jeżeli nam się poszczęściło). Operując w tych rejonach, jesteśmy w stanie osiągnąć aż poziom trzeci.
• Schodzimy głębiej w lochach. Ogar, Cerber i Demon to już solidniejsze potwory – w momencie, kiedy je masowo napotykamy, gra zsyła nam w jakiś sposób miecz, dzięki czemu mamy jakiekolwiek szanse w starciu. Tak uzbrojeni, średnio uzdolniony gracz jest w stanie osiągnąć poziom piąty.
• Czart i Ifryt to już poważni przeciwnicy – w momencie, kiedy zaczniemy powszechnie je spotykać (na przykład w głębiej położonych podziemiach), możemy używać toporu, który umożliwia jako takie pozbywanie się utrudnień stawianych przez grę. Zajmując się czartami i ifrytami gracz o przeciętnych umiejętnościach bez gigantycznych problemów osiągnie poziom siódmy.
• Miryd i Diabeł to najgroźniejsi przeciwnicy w całej grze – spotykani są tylko w najgłębszych zakamarkach katakumb i nawet najodważniejsi czują strach. W związku z tym, w magicznych paczkach można znaleźć Święty Granat Ręczny Alleluja, który jest jedyną szansą na w miarę szybkie kończenie walki z wyżej wymienionymi istotami. Dzięki wysiłkowi, gracz będzie mógł wejść na upragniony poziom ósmy i odtańczyć macarenę.

Pozostały jeszcze dwie sprawy do wyjaśnienia. Pierwsza jest widoczna na wykresie – liczba poziomów na jeden etap nie musi się równać liczbie potworów. W miarę możliwości należy się też postarać, aby ich ilość stopniowo malała – stymuluje to pożądany efekt Cięższego Ubijania Coraz Wyższego Levelu (w skrócie CUCWL). Druga sprawa natomiast mówi nam o tym, że jeden potwór (czy poziom) może być przypisany do jednego, dwóch, a nawet i więcej rodzajów broni – może to nawet w ładniejszy sposób balansować statystyki.

Widać zatem, że odpowiednie dobranie etapów (czyli narysowanie diagramu podobnego do powyższego, ale dużo ładniejszego) jest kluczowe. Rzeczywiście, tak jest – poniższe pomysły opierają się na tych słynnych (w lokalnej czasoprzestrzeni) etapach.

Są oczywiście parametry, które należy ustalić na samym początku – należy mieć jakiś punkt zaczepienia. W naszym przypadku będzie to chociażby zakres obrażeń, jakie zadają kolejne sztuki broni. Weźmy dla naszego przykładu:

Nazwa	Obrażenia minimalne	Obrażenia maksymalne	Obrażenia średnie
Sztylet	2	4	3
Miecz	2	8	5
Topór	7	15	11
Święty Granat Ręczny Alleluja (po co taką długą nazwę wziąłem, to nie wiem)	10	30	20

 

Zdaję sobie sprawę, iż te numerki są źle dobrane (wygenerowanie ich zajęło mi 10 sekund), ale tym lepiej dla przykładu. To znaczy, nie wiem czy tym lepiej, ale w celach edukacyjnych się sprawdzi. W czwartej kolumnie mamy bardzo ważną sprawę – obrażenia średnie. Generalnie, oprócz idei dopasowywania i łączenia w etapy, korzystać będziemy nie z zakresu wartości, ale ze średniej. Jej pochodzenia nie trzeba tłumaczyć ([obr. min. + obr.max] / 2), a znacząco ułatwiają dalsze obliczenia. Potem będziemy to i tak musieli przerobić na przedział, ale to będzie równie proste co konstrukcja Yesty.

Zabieramy się teraz za liczenie maksymalnych punktów życia potworków. Tutaj trzeba zrobić kolejne założenie – średnia ilość uderzeń bronią-która-jest-przypisana-do-danego-etapu potrzebna do zabicia potworka-który-jest-przypisany-do-danego-etapu. Jednakże,  mimo iż na przykład Imp, Diablik i Gog są na jednym etapie, Gog będzie “trochę” silniejszy od Impa. Z tego też powodu, nie możemy ustalić jednej średniej ilości potrzebnych uderzeń sztyletu, ale należy ustalić przedział np. 2-5 – przeczuwamy, że gracz będzie musiał od dwóch do pięciu razy trzepnąć kreaturę, aby ta padła. Powiedzmy, dwa uderzenia potrzebne do wysłania Impa do KWŁ (Kraina Wiecznych Łowów), trzy dla Diablika i pięć dla Goga. Korzystając z obrażeń średnich sztyletu (wartość ustalona na 3), można obliczyć wartość HP (ang. hit points) tych trzech potworków.

 

Potwór	Średnia ilość potrzebnych uderzeń	Średnie obrażenia sztyletu	Obliczenie HP potwora
Imp	2	3	2 * 3 = 6
Diablik	3	3	3 * 3 = 9
Gog	5	3	5 * 3 = 15

 

Nie wiem, czy to dobrze wytłumaczyłem, ale idea jest taka, aby wczuć się w gracza i ustalić, że np. wystarczą dwa dźgnięcia sztyletem, aby powalić takiego Impa. Oczywiście, cały czas bierzemy przypadki standardowe – bez jakiś bonusów czy aur zadawania obrażeń.

Zaznaczę też, że od tej pory wszelkie przykładowe obliczenia będę wystostowywał dla pierwszego grupy stworów – wyliczenie statystyk dla kolejnych etapów można potraktować sobie jako testowanie własnej inwencji twórczej. Nie jest to “olewanie” sprawy z mojej strony, tylko nie ma chyba sensu, abym wymyślał statystyki dla każdego przykładu, zwłaszcza, że zasada jest taka sama.

Dobrze, mamy zatem HP potworków. Przechodzimy do drugiej kwestii – zadawane przez ich obrażenia. Nie da się ukryć, że aby gra była grywalna, gracz powinien być atakowany przez przeciwników, a nie tylko w nich uderzać. Dlatego teraz policzmy średnie obrażenia zadawane przez przeciwnika.

Mamy tutaj dwie możliwości, które zależą od konwencji naszej gry. Pierwsza metoda obowiązuje, gdy maksymalne punkty życia naszej postaci są na stałym poziomie (lub mogą się zmieniać o niewielką wartość – patrz Wielki Mistrz, Quake). Należy wtedy (podobnie jak było w przypadku liczenia HP) założyć, o jaki mniej więcej procent życia poszczególne potwory będą nam zabierały. Na przykład, Imp jednym uderzeniem zabierze nam średnio 2% życia, Diablik 4%, a Gog 6%. Druga metoda zakłada z kolei, że maksymalna ilość punktów życia gracza sukcesywnie się zwiększa (jak w Diablo, Baldur’s Gate). Wtedy sytuacja robi się troszkę bardziej skomplikowana, bowiem do każdego etapu należy dopisać ilość punktów życia, jaką przewidujemy, a następnie liczyć stały (w jakimś małym przedziale) procent od tej wartości dla potworów z danego etapu. Brzmi skomplikowanie, dlatego pozwolicie, że pokażę przykład dla stałej wartości HP gracza na podstawie statystyk przytoczonych powyżej.

Potwór	Ilość HP gracza	Procent obrażeń potwora względem HP gracza	Obliczenie  średnich obrażeń potwora
Imp	115	2	0,02 * 115 = 2
Diablik	115	4	0,04 * 115 = 5
Gog	115	6	0,06 * 115 = 7

Jak widać, po obliczeniach uzyskaliśmy średnią wartość obrażeń. Z pewnością chcielibyśmy teraz uzyskać z tej wartości zakres minimalnych i maksymalnych obrażeń dla potworka. Można to zrobić “na oko”, albo użyć przykładowego algorytmu pseudolosowego zapisanego poniżej w prawie-że-pseudokodzie.

Mając średnią wartość average_value, losujemy liczbę z przedziału [1, average_value-1], co stanowi minimalne obrażenia zadawane przez danego przeciwnika. Aby obliczyć maksymalne, wystarczy od podwojonej wartości średniej odjąc obliczone przed chwilą min.

Nie ukrywam, ta metoda może być lekko zgubna – jeśli źle podamy procenty, to może się okazać, że najsilniejsze potwory zabiorą nam 100% życia jednym ciosem. Zakładam jednak, że ilość punktów życia gracza może się w małym stopniu powiększać, a poza tym możliwe są wszelkiego rodzaju pancerze, czary protekcyjne i podobne wynalazki.

Ostatnią rzeczą, jaką bym chciał się zająć, to ilość punktów doświadczenia, jakie trzeba uzyskać, aby wchodzić na kolejne poziomy doświadczenia. Tutaj należy założyć, że wybraliśmy już jakieś wartości “expa” za poszczególne potwory. Dla uproszczenia, zastosuję tutaj cyferki z obliczeń HP, czyli 2 za Impa, 3 za Diablika i 5 za Goga.

Wiadomo, że zdobywanie kolejnych poziomów doświadczenia powinno stanowić coraz większy problem i wymagać więcej wysiłku. I tak należy pamiętać, że w chwili obecnej uwzględniam tylko zabijanie potworów – wykonywanie zadań również powinno być nagradzane doświadczeniem, aczkolwiek można zastosować pewną sztuczkę i… potraktować je jako potwory i przypisać do poszczególnych etapów. Istnieje jednak groźba, że liczba punktów doświadczenia za takie zadanie znacznie zawyży nam średnią (o czym poniżej) i dostaniemy niewspółmierny próg na kolejny poziom. Nie ukrywam, że pomijam tutaj ten aspekt ze względu na uproszczenie sobie sprawy.

Zatem, zabijanie potworków w celu zdobycia poziomu można sprowadzić do następującego problemu: ilu przeciwników więcej należy się pozbyć, aby zdobyć kolejny poziom (cały czas jesteśmy na płaszczyźnie jednego etapu). Ja przyjąłem taką konwencję:

Poziom doświadczenia (n)	Ilość zabitych potworów (pn)
1.	10
2.	15
3.	20

 

Nie jest zbyt wyrafinowana, ale ponownie – w celach edukacyjnych wystarczy. Teraz należy policzyć wcześniej napomnianą wartość średniej ilości punktów doświadczenia za zabicie potwora z danego etapu. W naszym przypadku, skoro za Impa są 2 punkty, za Diablika 3, a za Goga – 5, nie pozostaje nic innego jak zrobić to następująco:

Jest to “podłoga” (zaokrąglenie w dół) z średniej arytmetycznej punktów doświadczenia poszczególnych przeciwników na danym etapie. Uzbrojeni w trzy parametry (n, p_n i avg_exp), możemy zdefiniować rekurencyjną funkcję f(n), czyli ilość punktów doświadczenia potrzebnych do awansowania na dany poziom.

Mamy już wszystko – wystarczy tylko obliczyć. Co też niniejszym czynię w poniższej tabelce.

Poziom	pn	avgexp	f(n)
1.	10	3	10 * 3+ 0 = 30
2.	15	3	15 * 3 + 30 = 75
3.	20	3	20 * 3 + 75 = 135

 

Nie do pominięcia jest wątpliwość przeskakiwania pomiędzy poszczególnymi dwoma etapami. Pewnym pomysłem jest tutaj liczenie średniej dla potworków z obu etapów (argumentując to tym, że będziemy wszystkie spotykać w miarę równolegle). Rodzi to jednak pewne komplikacje w obliczeniach.

Tak czy inaczej, jedna zasada zobowiązuje – wszystkie powyższe pomysły można wyrzucić do kosza, jeśli nie będą poparte dość dużą dozą testów. Nie chcę, abyście myśleli, że są to jakieś metody poparte matematycznymi dowodami i jedyne słuszne, które stosują znani deweloperzy. Są to jedynie moje rozważania i idee, które można wypróbować, wcielić w życie i ponarzekać. W końcu nie uwzględniam tutaj wielu faktów, jak czary, rodzaje ataków potworków czy bonusy. Co do czarów ofensywnych kreatur (np. Gog oprócz ataku szponami może puścić ognistą kulę), można liczyć wskaźnik potencjalnych obrażeń na minutę i odpowiednio wyrównywać moc szponu i ognistej kuli.

Byłbym bardzo wdzięczny, jeżeli ktoś również ma jakieś przemyślenia na ten temat i chciałby się nimi podzielić – być może powstanie kolejna notka na ten temat albo powstanie ciekawa dyskusja w komentarzach.

Także, zachęcam do prób i dziękuję za dotarcie aż do tego miejsca – zdaję sobie sprawę, że to nie było łatwe.

Pozdrawiam i dziękuję – SceNtriC.

Wielki Mistrz – Heretic Demo

Przyszła kolej na czwarte już demo Wielkiego Mistrza opatrzone tym razem kryptonimem “Heretic”. Dlaczego tak? Wstępne projekty walki były wzorowane na grach Heretic i Hexen, czyli starych dobrych naparzankach FPP. Z tej części można wywnioskować, jaką funkcjonalność pokazujemy w tej wersji. Tak jest – moduł walki.

To jest to, czego dopominało się wielu z Was, a nad czym pracowaliśmy od prawie dwóch miesięcy. Wreszcie można wziąć prawdziwy miecz w dłoń, posiekać parę latających bydlątek, wysłać kulę ognistą w tabun wrogów i pokazać Głównemu Złemu, kto tu jest Wielkim Mistrzem. Nie da się jednak ukryć, że warstwa fabularna jest uboga – ratujemy Myrvandel przed paraliżem internetowym, który powstaje po porwaniu Głównego Administratora Sieci Myrvandelskiej. Straszna trwoga ogarnęła mieszkańców (gdyż nie mogą chwalić się zdobytymi odznaczeniami w ET), a my przegraliśmy w “papier-kamień-nożyce” i teraz znajdujemy się w lochach.

Standardowo – linki pod którymi można znaleźć grę oraz dyskusję o niej:

• Wersja dla Windowsa
• Wersja dla Linuxa
• Wątek na forum Warsztatu

Oraz wykaz najważniejszych zmian:

• Oczywiście – walka, moduł walki, obrażenia, życie, pancerz, potwory, aaa….
• Osiem dosyć dużych poziomów podziemi – narastający stopień trudności
• Parę sztuk oręża wszelakiego
• Czary
• …Mary
• Eliksiry
• Potwory chcące zjeść gracza
• I popić miksturami
• System czegoś w rodzaju punktów doświadczenia, poziomy, talenty
• Nowy mechanizm renderowania lochów (kaflobloczki)
• Około czterech godzin zabawy

Jak widać, punktów jest może mniej niż przy poprzednich wydaniach, ale za to swoją wagą stanowią znaczny postęp. Wreszcie można komuś przyłożyć i to zarówno z broni białej jak i magicznego pocisku. Wszystko zostało zgrabnie oskryptowane i wyparameteryzowane, zatem można rzec, iż udało nam się stworzyć system w dużej mierze podobny do miłych, “oldschoolowych” gier cRPG z widokiem z perspektywy pierwszej osoby. Tutaj nie ma za bardzo o czym się rozpisywać, gdyż to czuje się dopiero grając. Walkę toczymy na ośmiu poziomach podziemi i muszę przyznać, że podczas testowania wiele razy się gubiłem. Lochy są dosyć duże, korytarze często się rozgałęziają i często nie zwiedzimy wszystkiego tak szybko. Jest to jednak plus – gra szybko nam się nie znudzi i możemy podbudować nasz poziom doświadczenia.

Pacyfikować wrogów możemy siedmioma rodzajami broni – na początku jesteśmy uzbrojeni tylko w pięść, ale bardzo szybko możemy w skrzyni znaleźć sztylet. Podczas wędrówki znajdziemy też wiele mikstur, które w większości leczą nasze zdrowie, ale mogą również przyspieszyć nasza postać czy zapewnić barierę ochronną na jakiś czas. Oprócz “potionków” można doszukać się również pergaminów, które służą głównie do rzucania czarów ofensywnych.

Same stwory mają jeden cel – dopaść gracza i wyrządzić mu jak najwięcej krzywdy. Z racji braku potrzebnej ilości grafików skorzystaliśmy z modeli stworzonych na potrzeby poprzedniej produkcji zespołu SystemSzok – Shadow Clones. Nie jest to może wymarzone rozwiązanie, ale w praktyce prezentuje się bardzo dobrze – kreatury są zróżnicowane, niektóre są słabe, inne bardzo mocne, potrafią atakować wręcz, ale też z dystansu. Tak czy inaczej – nie sądzę, abyście się nudzili.

Wspominałem coś o punktach doświadczenia. Prawdę mówiąc, nie powinny one być tak nazywane – za te punkty można bowiem podstawić zarówno doświadczenie za potwory jak i kosztowności znalezione podczas gry. Tak czy inaczej, przekładają się one na kolejne poziomy doświadczenia, które można uzyskać podczas rozgrywki. A te z kolei wiążą się z tzw. talentami czyli “skillami”, które dobierane w odpowiedni sposób pozwalają na silniejsze ciosy, szybsze bieganie czy większą ilość punktów życia. Dzięki talentom (i odrobinie szczęścia) można uzyskać najsilniejszą broń w grze już po wejściu na pierwszy poziom – tego typu smaczki pozostawiam Wam do odkrycia. Parę easter eggów również by się pewnie znalazło (ja odkryłem jeden ukryty przez Toxica), choć tak naprawdę fabułą również jest jednym wielkim jajkiem wielkanocnym.

Ale nie samą walką człowiek żyje – do naszego składu dołączył Voytech, który w świetny sposób upiększył lochy, stosując mechanizm tzw. “kaflobloczków”. Jest to nic innego, jak zastosowanie modeli (wykonanych akurat w Blenderze) jako cegiełek, z których buduje się całe podziemia. Dlaczego jest to zabieg upiększający? Z tego powodu, iż sklepienia i wierzchołki są teraz półkoliste. Na prostokątność lochów narzekało całkiem sporo osób – jak Wam się teraz podoba?

Jak zatem widać, poprzednie demko (Brengir – tu i tu) było nastawione na zadania, fabułę, dialogi, tak w Hereticu mamy do czynienia z czystym hack’n’slashem. Można wręcz powiedzieć, że są to prawie osobne gry. Miejmy nadzieję, że uda się coś z tym dalej zrobić.

Oczywiście, zachęcam do komentowania, zgłaszania swoich uwag, propozycji oraz innych wskazówek. Każdy głos jest bardzo pomocny i brany pod rozwagę. Wiadomo, że Wielki Mistrz nie jest Oblivionem, Morrowindem czy Neverwinterem, ale powiem Wam jedno – to przyjemne uczucie uczestniczyć w nieco większym projekcie, który cieszy się sympatią więcej niż 10 ludzi.

Zatem ściągajcie demko i bawcie się dobrze. Jeśli Wam się znudzi – zapisujcie grę, wyłączcie, zastanówcie się co jest niedobre, w miarę możliwości napiszcie i grajcie znowu. O ile większość preferuje czyste produkcje cRPG, tak nie da się ukryć, że ogromnę frajdę zapewnia wyrzynanie hord wrogów i zdobywanie poziomów.

Pozdrawiam i dziękuję – SceNtriC.

Sesja, statystyki i brak notek na blogu

Ech, tak jakoś wyszło, że od końca maja nic nie napisałem na blogu. Wiąże się to bezpośrednio z Gorącym Czerwcem wraz z kulminacyjnym momentem w trakcie każdego semestru, czyli słynną Sesją. Jakoś tak się dzieje, że Politechnika Poznańska sesję zaczyna wtedy, kiedy inne poznańskie uczelnie mają już ją za sobą (lub są w trakcie). Cóż, trzeba to przeżyć i tak.

Równolegle jednakże trwają prace nad kolejną funkcjonalnością Wielkiego Mistrza. Mogę jednak już zapowiedzieć, że prawdopodobnie będę miał kolejny materiał na artykulik (tudzież felietonik), a dotyczyć on będzie prawdopodobnie harmonizowania parametrów potworów, broni i gracza w grze cRPG. A konkretnie – jak dobrać te wszystkie wartości, aby to razem współgrało, nie nudziło i nie było za trudne. Wbrew pozorom, nie jest to takie proste i cały czas trwają prace nad odpowiednią stabilizacją tej części WM. Myślę, że parę przemyśleń, które pojawiły się podczas prac znajdzie swoje zwięczenie na tej stronce w postaci jakieś notki. Tak czy inaczej, główna idea polega na “matchingu”, czyli dopasowywaniu i sprowadzaniu pewnych podzbiorów potworów, oręża i poziomów doświadczenia do jednego etapu, a następnie liczenie wielu dziwnych rzeczy (brzmi jak dowodzenie NP-zupełności, brrr). Metoda ta nie uwzględnia wielu skomplikowanych czynników, które zwykle występują w grach fabularnych, ale może stanowić pewną podstawę.

Chociaż muszę przyznać, że jak wstępnie parametryzowałem stworki (przed sesją), to robiłem to na “oko”. Tyle z matchingu. Teraz biedny Toxic musi poprawiać (pozdrawiam [a także cały zespół SystemSzok]).

Mam nadzieję, że będę miał wkrótce troszkę czasu, aby o tym napisać. Powodzenia wszystkim współnieszczęśnikom sesyjnym.

Pozdrawiam – SceNtriC.

PDF-owy hashing i szablon aplikacji yestowej

Dosyć tajemniczy tytuł notki, która w gruncie rzeczy będzie dosyć krótka i może niezbyt ciekawa. Pierwsza rzecz – fatalne formatowanie artykułu umieszczonego w poprzedniej notce. Chciałem za to przeprosić, ale przyznać jednocześnie, że od jakiegoś czasu mam potężne problemy z “kodoźródłowym” pluginem do Windows Live Writera nazwanego Code Snippet, który wycina połowę kodu lub nadpisuje to tak, że nic nie wiadomo. Dlatego też postanowiłem się troszkę pobawić i przepisać artykuł do LaTeXa (o czym prawdę mówiąc myślałem już wcześniej). W takim wypadku, haszowanie jest dostępne teraz w formacie PDF pod tym linkiem:

Link do artykułu “Jak używać kluczy, czyli haszujemy wokoło i wesoło”

Jeśli hiperłącze wygaśnie, proszę o kontakt – chętnie wyślę plik.

Druga sprawa jest w sumie dosyć dziwna. Otóż, mimo iż czeka mnie czerwcowa batalia z zaliczeniami na uczelni, powolutku będę się brał za próby losowego generowania terenu. Nie każdy punkt z tamtego tutoriala przerobię, ale coś postaram się wyciągnąć. Jeśli to się uda i będę miał wolne (w końcu jeszcze Wielki Mistrz czeka) – prawpodobnie przez jakiś czas nie będę się zajmował dodawaniem nowej funkcjonalności tylko w końcu zacznę projektować i pisać silnik w oparciu o framework Yesta. Jednak jest to plan na tyle pokrętny i nieprzewidywalny, że póki co nie chcę o tym mówić. Tak czy inaczej, opisami kolejnych procesów rozwoju i projektowania będę Was zanudzał na devblogu, bądźcie tego pewni.

Ale wracając do generowania terenu, a tak naprawdę pisania programu z użyciem tego, co sobie wytworzyłem do tej pory. Zastanawialiście się może kiedyś jak wygląda najmniejszy szablonik przykładowej aplikacji?

http://nopaste.gamedev.pl/?id=3896

Przestrzeń nazw CGems jest wynikiem bezsensownej (znaczy - nieplanowanej) ewolucji frameworka we wszystkich możliwych kierunkach. Dlatego też w silniku raczej jej nie będzie i większość funkcjonalności będzie przeniesiona do klasy kamery czy innych.

Można powiedzieć, że kod jest bezsensowny – wyświetla tylko czarny ekran, który można zamknąć klawiszem [ESC], a Init chwilowo nic nie robi poza zwróceniem wartości “Sir, yes Sir!”. Tak jednak wygląda każdy początek pisania testowych aplikacji frameworka Yesta. Przeglądając tutoriale Ogre’a czy nGene Techa, a następnie kod powyżej można wręcz rzec, iż Yesta przypomina bardziej bibliotekę GLUT aniżeli coś porządnego. Trochę w tym prawdy jest, aczkolwiek stworzyłem to ze względu na swoją wygodę, gdyż w jakimś minimalnym stopniu znam OpenGL, natomiast nie orientuję się w gotowych silnikach. Które podejście jest według Was dogodniejsze dla początkującego – oparte na wskaźnikach na funkcje (callback) czy dziedziczenie po wbudowanej klasie bazowej w silniku? Sam się zastanawiam, na co postawić przy pisaniu silnika, a lubię stosować poznane nowe konstrukcje. Pytanie tylko, co i dla kogo jest lepsze.

Pozdrawiam – SceNtriC.

Jak używać kluczy, czyli haszujemy wokoło i wesoło

Jakiś czas temu wspomniałem o chęci napisania miniartykułu dotyczącego haszowania. Z góry mówię, że moim celem nie jest przedstawienie wszystkich możliwości rozwiązania problemu transformacji kluczowej, tylko przybliżenie samej idei i korzyści, jakie mogą z tego płynąć. Nie będę również próbował udawać, że rozumiem wszystkie matematyczne zależności wyprowadzone we Wprowadzeniu do Algorytmów Cormena (i nie tylko), bo musiałbym wznieść się na wyżyny aktorstwa.

Z góry też przepraszam, jeśli kogoś będzie raził niezbyt formalny ton w jakim będę pisał – to nie ma być rozprawa naukowa na którą człowiek patrzy i modli się, aby to samo było na wikipedii albo w jakimś tutorialu (i to najlepiej przed sesją). Ten artykuł to swoisty pamiętnik początkującego dla początkujących, zawierający potrzebną teorię oraz przykład implementacji.

Haszowanie (lub transformacja kluczowa – nie tak często spotykana nazwa, ale moim zdaniem odpowiednia) może być równeż przetłumaczone jako mieszanie, rozpraszanie. Dość dobrze oddaje to charakterystykę całego mechanizmu – tablica haszująca to struktura, w której przechowujemy dane na takiej samej zasadzie jak w normalnej tablicy (czy innym kontenerze). Różnica jest taka, iż wkładając dany element, opisujemy go określonym kluczem, który jest łańcuchem znaków. Aby odczytać element z tablicy haszującej, należy ponownie podać ten klucz. Nie operujemy na indeksach liczbowych – od tego jest cały mechanizm haszowania, aby obliczać sobie gdzie trzyma dane. Wprowadza to oczywiście wygodę w obsługiwaniu takiej tablicy. O ile dla struktury 10-elementowej można zapamiętać co jest pod każdym indeksem, tak np. w grze cRPG, gdzie wartości, parametrów, atrybutów jest od groma i ciut ciut… Oczywiście, dzięki obiektowości można to jakoś porozrzucać po klasach. Jednakże często w wielu miejscach kodu musimy odwoływać się do tych samych zmiennych. Jako że osobiście uważam nadmierne “includowanie” plików nagłówkowych za dosyć męczące, warto mieć jedną sporą strukturę, gdzie mamy wszystkie wartości.

Z takim rozwiązaniem wiąże się również inna rzecz – ilość permutacji kluczy nie musi się równać wielkości tablicy. Nie sposób bowiem przewidzieć wszystkich możliwych łańcuchów. Z tego też powodu haszowanie umożliwia reprezentowanie większej struktury za pomocą mniejszej. Z tym (i nie tylko) wiąże się problem kolizji – ale do tego dojdziemy później.

Rysunek poglądowy – po lewej mamy klucze, którymi się posługujemy operując na danych, a po prawej tablicę haszującą:

Dobrze widać tutaj, dlaczego haszowanie jest nazywane rozpraszaniem – nie możemy się spodziewać, że pierwsza wartość wpisana do tablicy będzie pod pierwszym indeksem. W gruncie rzeczy nie jest to nam do niczego potrzebne – i tak się odwołujemy korzystając jedynie z kluczy. Tak czy inaczej, wypadałoby jednak zająć się algorytmów rozmieszczającym wartości w tablicy właśnie na podstawie klucza-identyfikatora. Czynimy to poprzez funkcję haszującą, którą umownie sobie oznaczymy h(k), gdzie k jest kluczem, a wartością zwracaną – numer indeksu. Właśnie ta funkcja jest pierwszym krytycznym punktem całego mechanizmu. Oczywiście, z tej racji nie poświęciłem jej zbyt wiele uwagi przy implementacji – zgodnie z prawem Murphy’ego (paragraf 1., ustęp 7.) im więcej czasu poświęcimy na dopracowanie elementu krytycznego algorytmu, tym błąd w programie będzie bardziej spektakularny.

Szukanie odpowiedniej funkcji haszującej to zajęcie, któremu oddawali się najwybitniejsi z najwybitniejszych. Cała zasada opiera się na nadaniu znakom wartości liczbowych – najczęściej w oparciu o tablicę ASCII. Założenie jest takie, że dobra funkcja h(k) musi rozkładać elementy w taki sposób, aby chociaż w przybliżeniu było spełnione założenie prostego równomiernego haszowania, czyli “rozkładanie” danych niezależnie od siebie nawzajem.

Praktykowanych jest parę różnych wariantów funkcji haszującej. Dla poniższych przykładów przyjmijmy, że K oznacza sumę wartości ASCII kolejnych znaków klucza (np. “kot” to 107 + 111 + 116 = 334), a N to wielkość tablicy haszującej. Oczywiście, zliczanie sumy łańcucha może się odbywać różnymi sposobami – parę pomysłów (wraz z implementacjami) zostało przedstawione na stronie [5] (w ogóle pod koniec notki umieszczę parę pozycji książkowych i internetowych, gdzie można szukać informacji znacznie dokładniejszych niż tutaj).

• Haszowanie modularne – chyba najprostsza możliwość. Dzielimy K przez N i bierzemy resztę z dzielenia. Zatem h(k) = K mod N.
• Haszowanie przez mnożenie – równie proste rozwiązanie, ale bardziej wyrafinowane (trudno o mniej wyrafinowane od haszowania modularnego – cóż, zawsze można wszystko układać po kolei, a potem przeszukiwać każdą przegródkę słowami “Przepraszam, czy jest tu jakiś portfel?”). Wykorzystujemy stałą A zawierającą się w przedziale (0, 1). Mnożymy K i A, bierzemy z tego część ułamkową i mnożymy razy N, zaokrąglając cały wynik w dół. Wynika zatem, iż h(k) = floor(N * (K * A mod 1)). Od Donalda Knutha dodatkowo mamy optymalne wartości stałej A – wynoszą one 0,6180339887 oraz 0,3819660113.
• Haszowanie uniwersalne – ta kategoria została wymyślona po to, aby zapobiec dosyć przykremu przypadkowi, który może mieć miejsce przy wyborze standardowych (ustalonych) funkcji haszujących – odwzorowanie wszystkich kluczy na jedną pozycję w tablicy, w wyniku czego czas wyszukiwania elementu wynosi O(m), gdzie m to ilość dotychczas wykorzystanych kluczy. Nieprawdopodobne, ale może się zdarzyć. Dlatego też, posiadając pewny skończony zbiór funkcji haszujących H, dokonowywane jest losowe wybranie funkcji h(k), którą potraktujemy nasz klucz. Przyznam, że nie wgłębiałem się w tą metodę, ale podaję ją po to, abyście mieli pełny obraz, że haszowanie ma wiele twarzy.

To są te najbardziej znane rodzaje funkcji haszujących. Oczywiście, nie jest powiedziane, że jedyne – na pewno wielu osobom przychodzą do głowy różne pomysły na ten algorytm (na przykład “weź K, podziel go przez N, zróżniczkuj, spierwiastkuj, scałkuj w granicach e i pi, a następnie wyznacz miejsca zerowe takiej funkcji i losowo wybierz jeden indeks, a potem płacz, że nie wiesz gdzie co jest”). Trzeba jednak przyznać, iż wyżej wymienione sprawdzają się bardzo dobrze i dla naszych zastosowań nie ma sensu wymyślać czegoś niezwykłego.

Przy haszowaniu uniwersalnym wspomniałem o możliwej niedogodności, iż jakimś cudem wszystkie klucze zostaną odwzorowane na ten sam indeks. W praktyce często się zdarza, że w tablicy haszującej w tej samej pozycji trzymana jest informacja o dwóch lub więcej wartościach – tego raczej nie unikniemy, warto zatem przyswoić sobie sposoby radzenia sobie z kolizjami. To drugi krytyczny punkt naszego algorytmu i moim zdaniem wymagający więcej zaangażowania (ale też nie ponad siły – patrz prawa Murphy’ego, paragraf 1., ustęp 7.).

• Metoda łańcuchowa (ang. chaining) – chyba najprostsze rozwiązanie, z którego zresztą skorzystałem (tak, właśnie dlatego, że jest najprostsze). Polega na stworzeniu listy jednokierunkowej na każdej pozycji w tablicy i w momencie, kiedy dwie wartości zostaną odwzorowane na ten sam indeks, umieszczane są na tej liście. Metoda nieskomplikowana, aczkolwiek wydaje mi się mało efektywna, co akurat nie szkodzi przy naszych potrzebach.
• Dwie strefy tablicy – jest to metoda polegająca na dzieleniu całej tablicy na dwie podtablice – właściwą i przepełnioną. Uzyskanie od funkcji haszującej dla danego klucza k1 indeksu w tablicy, który został już przydzielony kluczowi k2 powoduje, że wartość opisana kluczem k1 jest wpisywana na pierwszą wolną pozycję w strefie przepełnienia. Niezbyt jednak wiadomo, co zrobić, gdy przepełni się strefę przepełnienia. Prawdę mówiąc – nie zajmowałem się tym długo (ok. 2 minuty).
• Adresowanie otwarte – jest bardzo podobne do poprzedniej metody i też opiera się na zapisywaniu wszystkiego w jednej tablicy bez użycia jakichkolwiek list. W przypadku adresowania otwartego, jeżeli dany indeks już jest zajęty, wartość nowego klucza jest umieszczana w następnej (jednej z następnych) wolnej pozycji, która wynika z tzw. funkcji przyrostu p(i), której wartość jest dodawana do funkcji h(k). I tutaj mamy trzy możliwości (jako c, c1,… będę oznaczał jakiś współczynnik, który w szczególności wynosi 1 (lub 0)):

1. Adresowanie liniowe – p(i) = c * i, czyli po prostu następny wolny indeks. Występuje tutaj silna tendencja do grupowania się kluczy i tworzeniu sobie obozu w pobliżu zajętego indeksu. Pewnie chcą mu coś zrobić. Tak czy inaczej – może wystąpić sytuacja, że jedna część tablicy będzie wypełniona po brzegi, a druga zupełnie pusta.
2. Adresowanie kwadratowe – p(i) = c1 * i² + c2 * i, czyli funkcja kwadratowa. Znacznie redukuje problem grupowania kluczy, ale nie eliminuje go całkowicie.
3. Haszowanie dwukrotne – p(i) = i * h1(k) lub p(i) = i * h1(k) + h2(k), czyli dodanie do pierwotnego rezultatu h(k) wyniku funkcji h1(k) i ewentualnie h2(k). Zapewnia najmniejsze prawdopodobieństwo zgrupowania się wyrazów, ale może lekko utrudnić “dojście” dla właściwego klucza.

Więcej grzechów nie pamiętam. Przyznam uczciwie, że nie badałem dokładniej adresowania otwartego, które się wydaje rozsądną propozycją, kiedy uczynimy tablicę haszującą dość dużą – najlepiej przewidywane N pomnożyć jeszcze przez jakąś liczbę.

Jak widać, czeka nas troszkę problemów przy implementacji haszowania. Do tego wypada wiedzieć jedno – trzeba z góry wiedzieć ile mniej więcej elementów będziemy chcieli przechować, gdyż wypełnienie całej tablicy i jeszcze jej “nadpisywanie” w przypadku metody łańcuchowej całkowicie gubi sens stosowania transformacji kluczowej. Rzekomo, granicą, po przekroczeniu której haszowanie staje się bezużyteczne, jest tablica wypełniona w ok. 70%, zatem, jeżeli wiemy, że będziemy przechowywać około 70 elementów, warto zadeklarować tablicę 100-elementową.

Warto jednak znać takie struktury – może nam się kiedyś przydać przy tworzeniu gier, ale także w bazach danych, kryptografii. W dodatku, część języków posiada już wbudowane tablice haszujące (lub też asocjacyjne) – PHP, Ruby, Perl, Python i inne. No i warto się z tym zaznajomić wcześniej, jeżeli w przyszłości czeka nas przedmiot Algorytmy i Struktury Danych.

Zatem przejdziemy teraz do mięsa, czyli implemetancji. Z góry mówię, że (jak zwykle) pomysł nie jest mój – tutaj wielkie dzięki składam Wyszowi, Toxicowi i nie-pamiętam-komu oraz całemu zespołowi SystemSzok, który tworzył grę Shadow Clones (a teraz kreuje Wielkiego Mistrza).

Ogólne założenie jest takie – stosujemy haszowanie modularne, a w przypadku kolizji – metodę łańcuchową. W dodatku, ciekawe jest tutaj to, że w jednej tablicy możemy zapamiętać zarówno liczby całkowite jak i rzeczywiste (w wersji zespołu SystemSzok można było jeszcze przechowywać łańcuchy, ale z tego zrezygnowałem). A wszystko zostało oczywiście opakowane w klasę i przyjęte do frameworka jako “zatwierdzone”.

Ze względu na pewne problemy z pluginem Code Snipper, wszystkie kody źródłowe wyjątkowo podam w sposób standardowy. Wprawdzie będzie brzydko, ale siła wyższa - przynajmniej nic nie ucieknie (swoją drogą, miał już ktoś problemy z Code Snipperem?).

Na początku trzeba zdefiniować sobie dwie rzeczy – strukturę CHashNode, która będzie opisywała daną wartość w tablicy haszującej oraz typ wyliczeniowy, dzięki któremu będzie łatwiejsze określenie, jakiego typu jest wartość, którą przechowujemy na danej pozycji. Warto bowiem wspomnieć, iż chociaż pod jednym kluczem może się znajdować zarówno wartość typu int jak i typu float (i będą to różne wartości), to będą one przechowywane na osobnych elementach listy.

#include <>
#include <>

// typ wyliczeniowy rodzaju zmiennych do hashowania
enum HASH_TYPE
{
HT_INT, // wartość typu int
HT_FLOAT // wartość typu float
};

// struktura węzła w tablicy hashującej
struct CHashNode
{
int h_iValue; // wartość int
float h_fValue; // wartość float
std::string h_cKey; // nazwa klucza

HASH_TYPE h_htType; // typ danej
};

Wartości rozróżniamy według notacji, jaką sobie założyłem, czyli h_pierwsza-literka-typu-zmiennejValue. Dodatkowo, przechowujemy informację o tym typie oraz łańcuch klucza prowadzącego do danego węzła (aby można było porównać).

Przystępujemy zatem do deklaracji klasy CHash.

class CHash
{
private:

std::list* h_lHashTable; // wskaźnik na tablicę z danymi
unsigned h_uQuantity; // wielkość tablicy hashującej

void InitNode (CHashNode*); // inicjalizacja węzła
int Hash (char*); // funkcja hashująca

public:

CHash (unsigned); // konstruktor
~CHash(); // destruktor

void SetInt (char*, int); // wczytanie wartości typu int
void SetFloat (char*, float); // wczytanie wartości typu float

void ChangeInt (char*, int); // zmiana wartości typu int
void ChangeFloat (char*, float); // zmiana wartości typu float

int GetInt (char*); // pobranie wartości typu int
float GetFloat (char*); // pobranie wartości typu float

void RemoveInt (char*); // usunięcie wartości typu int powiązanej z danym kluczem
void RemoveFloat (char*); // usunięcie wartości typu float powiązanej z danym kluczem
};

Widać, że stosujemy metodę łańcuchową – każdy indeks tablicy będzie tak naprawdę głową listy, na której będą zapisywane kolejne elementy. Ta struktura oraz wielkość tablicy jest inicjalizowana w konstruktorze – zastosowałem tutaj znany i lubiany model RAII, który z uwielbieniem jest wykorzystywany w całym frameworku. Mamy dwie metody prywatne – InitNode (zerującą każdy nowo utworzony element tablicy haszującej) oraz Hash (czyli naszą funkcję haszującą). Lekki bałagan panuje w sekcji publicznej – mam na myśli to, że Code Snipper niezbyt poprawnie formatuje kod i z tego powodu możecie widzieć takie kwiatki, za co serdecznie przepraszam. Można jednak zauważyć cztery rodzaje operacji – Set (dodanie nowego elementu do tablicy wraz z odpowiadającym mu kluczem), Change (zmiana wartości elementu określonego danym kluczem), Get (pobranie wartości z tablicy za pomocą klucza) oraz Remove (usunięcie klucza z tablicy). Każda metoda zawiera dodatkowo sufiks Int lub Float, który naturalnie określa aktualną pogodę na wyspie Fidżi, choć prawdopodobnie jednak determinuje wykonanie operacji na wartości o żądanym typie.

Tyle implementacji pliku nagłówkowego. Należy zająć się zatem plikiem źródłowym. Na początek konstruktor oraz destruktor, czyli wykorzystanie wcześniej wspomnianego wzorca RAII.

#include "CHash.h"

CHash::CHash (unsigned n) // konstruktor
{
// pobranie wielkości tablicy haszującej
h_uQuantity = n;
h_lHashTable = new std::list[n];
}

CHash::~CHash() // destruktor
{
// zwolnienie pamięci po strukturze
delete[] h_lHashTable;
h_lHashTable = NULL;
}

Do konstruktora podajemy rozmiar tablicy haszującej, a w nim samym alokowana jest pamięć dla tablicy głów list, która zwalniana jest w destruktorze. Nie ma tutaj nic ciekawego, zatem przejdziemy do implementacji metody InitNode.

void CHash::InitNode (CHashNode* node) // inicjalizacja węzła
{
node->h_cKey = "";
node->h_fValue = 0.0f;
node->h_iValue = 0;
}

Jak widać, nie jest to też demon komp(l)ikacji. Przekazany węzeł ma zerowane wartości oraz klucz. Zmienne te potraktujemy odpowiednio w metodach SetInt oraz SetFloat. Natomiast teraz proponuję zająć się czymś ciekawszym – funkcja haszująca.

int CHash::Hash (char* key) // funkcja haszująca
{
// pobranie długości klucza oraz inicjalizacja zmiennej sumującej
int length = strlen(key);
unsigned s = 0;

// funkcja haszujca działa następująco:
// zsumuj kody ASCII wszystkich znaków oraz i, gdzie i to pozycja każdego znaku
// czyli np. klucz "kot", to dodawanie:
// 107 + 0 + 111 + 1 + 116 + 2 = 337
for (unsigned i = 0; i <>
{
s += static_cast<>(key[i]) + i;
}

// zwrócony indeks to ta suma modulo wielkość tablicy
return (s % h_uQuantity);
}

Pozwoliłem sobie na zostawienie całego kodu w niezmienionej postaci wraz z komentarzami. Nie postarałem się specjalnie – zastosowałem zwykłe haszowanie modularne, ale z małym mykiem – dodawanie wartości ASCII znaków łańcucha do siebie nie jest tak bezmyślne. Uwzględniana jest również pozycja danego znaku w łańcuchu. Ma to na celu zapobieganie sytuacji, gdy klucz “banan” ma dokładnie taką samą wartość jak “nanab” czy inna dowolna permutacja tego ciągu znaków. Nie jest to może nadto wyrafinowane, gdyż nadal stosunkowo łatwo uzyskać kolizję, ale lepszy rydz niż nic.

Uzbrojeni w potrzebne funkcje, napiszmy teraz pierwszą parę metod operacyjnych – SetInt oraz SetFloat.

void CHash::SetInt (char* key, int value) // wczytanie wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// utworzenie nowego węzła i wyczyszczenie go
CHashNode node;
InitNode(&node);

// zapisanie wartości, klucza i typu w nowym węźle
node.h_cKey.assign(key);
node.h_iValue = value;
node.h_htType = HT_INT;

// dopisanie węzła do listy
h_lHashTable[index].push_back(node);
}

void CHash::SetFloat (char* key, float value) // wczytanie wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// utworzenie nowego węzła i wyczyszczenie go
CHashNode node;
InitNode(&node);

// zapisanie wartości, klucza i typu w nowym węźle
node.h_cKey.assign(key);
node.h_fValue = value;
node.h_htType = HT_FLOAT;

// dopisanie węzła do listy
h_lHashTable[index].push_back(node);
}

Dla formalności będę podawał zawsze obie wersje – chociażby dlatego, że sam lubię mieć wszystko “na tacy”. Przy omawianiu jednak skupię się na ogólnym zarysie algorytmów ze względu na to, że obie wersje różnią się między sobą typem oraz zmienną, do której jest zapisywana wartość. Tak czy inaczej, najpierw pobierany jest indeks obliczony przez funkcję haszującą dla danego klucza, a także tworzony i zerowany nowy węzeł. Pewne komplikacje wynikły przy typie łańcuchów char* – w całym frameworku stosuje właśnie tą konwencję, natomiast tutaj wyjątkowo jest to konwertowane w locie na std::string, co akurat wielkim problemem nie jest – z punktu widzenia obsługi obiektu wszystko zostaje po staremu. Zapisywana jest wartość klucza, wartość value w odpowiedniej zmiennej oraz ustawiana jest flaga typu tej zmiennej. Po wykonaniu tych operacji, cały element jest dodawany do listy znajdującej się w odpowiednim indeksie, obliczonym wcześniej przez funkcję h(k).

Świetnie, umiemy zapisać wartość do tablicy haszującej. Czasami jednak trzeba ją zmienić. Dlatego teraz implementacja metod ChangeInt oraz ChangeFloat.

void CHash::ChangeInt (char* key, int value) // zmiana wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu int
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// wartość zostaje zmieniona na nową
it->h_iValue = value;
break;
}
}
}

void CHash::ChangeFloat (char* key, float value) // zmiana wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// wartość zostaje zmieniona na nową
it->h_fValue = value;
break;
}
}
}

Początek operacji standardowy – obliczamy indeks w tablicy według klucza. Jeśli z jakiś względów podaliśmy zły klucz i w dodatku na danej pozycji lista jest pusta, wychodzimy od razu z metody, żeby nie zabierać czasu na bezsensowne operacje. Jeśli jednak istnieje uzasadnione prawdopodobieństwo, iż działamy zgodnie z planem, deklarujemy sobie iterator do wędrowania po liście, a następnie sprawdzamy ją całą. Jeśli w którymś miejscu dopasowanie podanego klucza do wcześniej zapisanego skończy się sukcesem, a w dodatku typ zmiennej się zgadza – wartość zostanie zmieniona na nową. Wtedy wychodzimy z pętli for i całej funkcji.

Na tym schemacie bazują praktycznie wszystkie następne funkcje. Korzystając z tego, jeszcze bardziej ułatwię sobie zadanie i będę opisywał wyłącznie operacje, które są z jakiegoś względu niezwykłe. Można tak powiedzieć o parze metod GetInt i GetFloat, które są kluczowe, gdyż pozwalają nam uzyskać dostęp do zapisanych wcześniej wartości.

int CHash::GetInt (char* key) // pobranie wartości typu int
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty", zwracamy -1
if (h_lHashTable[index].size() == 0)
{
return 0;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;
int ret = 0;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu int - zwracamy wartość
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// będziemy zwracać tą wartość
ret = it->h_iValue;
break;
}
}

// zwrócenie danej wartości
return ret;
} // int CHash::GetInt (char* key)

float CHash::GetFloat (char* key) // pobranie wartości typu float
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty", zwracamy -1
if (h_lHashTable[index].size() == 0)
{
return 0.0f;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;
float ret = 0.0f;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float - zwracamy wartość
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// będziemy zwracać tą wartość
ret = it->h_fValue;
break;
}
}

// zwrócenie danej wartości
return ret;
} // float CHash::GetFloat (char* key)

Domyślnie zwracaną wartością jest 0 i to zarówno gdy podamy zły klucz jak i zły typ. Sam algorytm przebiega praktycznie identycznie jak operacja Change – z tym wyjątkiem jednak, że tutaj zwracamy wartość, a nie zamieniamy jej.

Pozostała nam jeszcze jedna operacja – usuwanie atrybutu (w takim kontekście można to określić) z tablicy. Przyjrzyjmy się zatem metodom RemoveInt oraz RemoveFloat.

void CHash::RemoveInt (char* key) // usunięcie wartości typu int powiązanej z danym kluczem
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_INT)
{
// wartość zostanie usunięta
h_lHashTable[index].erase(it);
break;
}
}
} // void CHash::RemoveInt (char* key)

void CHash::RemoveFloat (char* key) // usunięcie wartości typu float powiązanej z danym kluczem
{
// pobranie zahaszowanego indeksu
int index = Hash(key);

// jeśli dany indeks jest "pusty"
if (h_lHashTable[index].size() == 0)
{
return;
}

// poruszanie się po liście na danym indeksie, w celu
// znalezienia pozycji, na której znajduje się wartość
// o danym kluczu

std::list::iterator it;

for (it = h_lHashTable[index].begin(); it != h_lHashTable[index].end(); ++it)
{
// jeśli klucz się zgadza i przechowuje wartość typu float
if (it->h_cKey.compare(key) == 0 && it->h_htType == HT_FLOAT)
{
// wartość zostanie usunięta
h_lHashTable[index].erase(it);
break;
}
}
} // void CHash::RemoveFloat (char* key)

Ponownie nic ciekawego się tutaj nie dzieje – stały schemat, który ulega modyfikacji dopiero po najechaniu iteratorem na element przeznaczony do usunięcia, który znajduje się na strukturze pod obliczonym indeksem w tablicy. Wykonywana jest tutaj zwykła operacje erase, która kasuje element znajdujący się na liście. I już.

Mam nadzieję, że przedstawiona poniżej implementacja haszowania nieco rozjaśnia całe zagadnienie. Zdaję sobie jednak sprawę, że być może zbyt pobieżnie przeanalizowałem kody źródłowe. Aby formalności stało się za dość, przedstawiam króciutki programik testujący nasz algorytm.

#include <>
#include "CHash.h"

int main()
{
CHash hash(10);

hash.SetFloat("kot", 3.04f);
hash.SetInt("koteczek", 34);

std::cout << hash.GetInt("zuo") << std::endl; // nie przypisaliśmy wartości do klucza "zuo"
std::cout << hash.GetInt("kot") << std::endl; // niepoprawne wywołanie, "kot" jest floatem
std::cout << hash.GetFloat("kot") << std::endl;
std::cout << hash.GetInt("koteczek") << std::endl;

hash.ChangeInt("koteczek", 26);
std::cout << hash.GetInt("koteczek") << std::endl;

hash.ChangeFloat("kot", -1.1f);
std::cout << hash.GetFloat("kot") << std::endl;

hash.RemoveFloat("kot");
std::cout << hash.GetFloat("kot") << std::endl;

hash.SetFloat("kot", -1.1f);
std::cout << hash.GetFloat("kot") << std::endl;

getchar();
return 0;
}

Skompilowanie i uruchomienie tego kodu powinno dać poniższy rezultat.

0
0
3.04
34
26
-1.1
0
-1.1

Widać, że nasze starania warte były zachodu – w przypadku podania nieodpowiedniego klucza uzyskujemy wartość domyślną zero, a w przy poprawnych wywołaniach – to, o co nam chodziło.

Warto tutaj wspomnieć, że domyślne zero to bardzo wygodna wartość. Przykładowo – odmierzamy czas jaki pozostał do wygaśnięcia jakiegoś czaru, przyjmijmy Spowolnienie. W tym celu, po jego rzuceniu wywołujemy funkcję nadającą wartość danemu atrybutowi.

hash.SetFloat("slow_time_to_live", 10.0f);

W każdej klatce zmniejszamy ten czas o pewną wartość delta_time.

int remaining_time = hash.GetFloat("slow_time_to_live");
hash.ChangeFloat("slow_time_to_live", remaining_time - delta_time);

A jeśli czas ten dojedzie (bądź minie) do zera – możemy usunąć atrybut.

hash.RemoveFloat("slow_time_to_live");

W ten sposób nie musimy pamiętać indeksu w tablicy (co cały czas podkreślam). Wystarczy wiedzieć, że dany stan bohatera czy potwora określony jest przez atrybut (klucz) “slow_time_to_live”.

Cóż, to wszystko co miałbym do przekazania odnośnie transformacji kluczowej. Mam nadzieję, iż udało mi się przekazać to zagadnienie w sposób przyjazny i zrozumiały. Jeśli gdzieś zauważyliście błędy, nieścisłości bądź chcecie mi wytknąć poważną pomyłkę merytoryczną żebym się zamknął w sobie i zaczął kręcić kółeczka – jestem do Waszej dyspozycji w komentarzach pod notką.

Na koniec podam jeszcze referencje, czyli małą bibliografię i linki, pod którymi można znaleźć ciekawe rzeczy odnośnie haszowania (z czego skrzętnie korzystałem podczas redagowania artykułu).

[1] Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów, Wydawnictwo Naukowo-Techniczne, 2007, Seria Klasyka Informatyki
[2] Wróblewski P., Algorytmy - struktury danych i techniki programowania, Wydanie III, Wydawnictwo Helion, Gliwice, 2003
[3] http://en.wikipedia.org/wiki/Hash_table
[4] http://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca
[5] http://krzyjab.w.interia.pl/html/edu_haszowanie.html
[6] http://www.mif.pg.gda.pl/homepages/sylas/students/alg_podypl/w9.pdf
[7] http://math.univ.gda.pl/~blaszep/asd/wyklad/wyklad13_drukuj.pdf
[8] http://pl.wikipedia.org/wiki/Prawa_Murphy%27ego

Pozdrawiam i dziękuję – SceNtriC.