Jakiej struktury danych należy użyć dla drzewa talentów w stylu Diablo / WoW?

Zastanawiam się nad wdrożeniem systemu drzewa talentów do internetowej gry RPG, podobnej do tej w World of Warcraft, gdzie zdobycie umiejętności odblokowuje kolejny „poziom” pod nią w drzewie.

Czy ktoś wie o najlepszym sposobie implementacji tego strukturalnie w bazie danych / kodzie?

Użyj takiej struktury, aby przedstawić drzewo w bazie danych:

#Talent
id  parent  description
1   0       Tackle
2   1       Kick
3   1       Punch
4   3       Fire Punch

I kolejna tabela reprezentująca nabyte talenty na użytkownika

#UserTalent
id  user  talent
1   4     1
2   4     3
3   4     4

Możesz programowo sprawdzić zależności między talentami, sprawdzając pełną tabelę talentów i budując połączone drzewo. Możesz to zrobić również za pomocą SQL, ale będzie to wymagało rekursywnych podselekcji lub wielu zapytań. Lepiej zrób to w kodzie.

Jeśli istnieje wiele zależności, na przykład Fire Punchzależy od PunchAND, Immolationużyj dwóch tabel do przedstawienia wykresu zależności:

#Talent
id  description
1   Tackle
2   Kick
3   Punch
4   Fire Punch
5   Immolation

#Depedency
id  parent  child
1   0       1
2   0       5
3   1       2
4   1       3
5   3       4
6   5       4

Polecam użycie drzewa, w którym każdy węzeł reprezentuje określony talent / umiejętność. W zależności od tego, czy gracz zdobył talent, można go zdobyć. Na przykład następująca struktura danych

class Talent {
    std::vector<Talent*> children;
    bool earned;
};

Aby ustalić, jakie talenty ma gracz, weź główny talent i idź w dół wykresu, aż dojdziesz do węzłów talentów, w których zdobyta wartość jest fałszywa. Ujawni to również, które talenty są dostępne do zdobycia: pierwszy talent w każdej gałęzi w dół od głównego talentu, w którym zarobione są fałszywe.

W mojej grze robię to tak:

Baza danych:

reference_talent : zawiera unikalny identyfikator, nazwę, efekt itp

talent : id, playerid <- zawiera wszystkie talenty, których „nauczyli się” gracze.

Ingame: (na serwerze)

Ładuję wszystkie pliki referencyjne na „statycznej” (tylko do odczytu) std :: map, dzięki czemu mogę łatwo uzyskać do nich dostęp dzięki ich identyfikatorowi.

Kiedy klient sprawdza gracza, pobieram wszystkie talenty z bazy danych i gromadzę je w standardzie std :: vector, aby kiedy potrzebowałem obliczyć cechy itp., Mam je w pamięci RAM. Wysyłam również talenty do klienta.

To wszystko (oprócz oszczędzania nowych talentów, które są po prostu „WSTAW” w tabeli „talent” + wiadomość dla klienta).

Podejście relacyjne

Opisujesz to jako relację między odblokowaniem a odblokowaniem podobnie jak w tym samouczku . Sugeruję, aby dowiedzieć się więcej na temat algebry relacyjnej i baz danych. Są dobrym sposobem modelowania danych. Jeśli nauczysz się wyszukiwać informacje z bazy danych, możesz dość łatwo modelować dane.

Nie wiem ile wiesz o modelowaniu relacji. Ten samouczek powinien ci w tym pomóc.

Jedno rozwiązanie

Zakładam, że WoW działa tak jak w rzeczywistości (ehm), że tak jest

• talent odblokowuje kilka (innych) talentów
• talent odblokowuje kilka (innych) talentów.

Jest to relacja N: N, co oznacza, że ​​potrzebujesz „średniego człowieka” nowej relacji między dwoma talentami:

(talent who unlocks id, talent who is unlocked)

W ten sposób możesz odblokować talent A odblokowujący B, C i D ((A, B), (A, C), (A, D)) i talent Y odblokowany przez X, Z i W ((X, Y), ( Z, Y), (W, Y)). W języku imperatywnym / proceduralnym / obiektowym Zrobiłbyś to jako listę / tablicę par takich jak tam:

var unlocks_unlocked = [[A, B],[A,C],[A,D],[X,Y],[Z,Y],[W,Y]];

Na przykład w „świecie rzeczywistym” możesz mieć:

... ["running fast", "jumping superhigh"], ["antigravity's child", "jumping superhigh"]

i oznacza to, że „skok superhigh” uzyskuje się po tym, jak masz talent „szybkiego biegania” i „dziecka antygrawitacji”.

Inne rozwiązanie

Ostatnio nie grałem w Diablo, ale możliwe, że miał tylko:

• talent odblokowuje kilka innych talentów
• talent odblokowuje tylko jeden talent.

Jest to relacja 1: N:

 You put "is unlocked by this talent's id" variable into talent's structure

lubić:

 var Talent[8] = { "name": "superpower", "unlocked by": "being Clark Kent"};