Welche Datenstruktur sollte ich für einen Talentbaum im Diablo / WoW-Stil verwenden?

23

Ich denke darüber nach, ein Talent-Tree-System für ein Online-Rollenspiel zu implementieren, ähnlich dem in World of Warcraft, bei dem der Erwerb einer Fertigkeit die nächste "Stufe" im Baum darunter freischaltet.

Kennt jemand die beste Möglichkeit, dies strukturell in der Datenbank / im Code umzusetzen?

RSH1
quelle

Antworten:

13

Verwenden Sie eine Struktur wie diese, um einen Baum in einer Datenbank darzustellen:

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

Und eine weitere Tabelle zur Darstellung erworbener Talente pro Benutzer

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

Sie können programmgesteuert nach Talentabhängigkeiten suchen, indem Sie die gesamte Talenttabelle abfragen und einen verknüpften Baum erstellen. Sie können dies auch mit SQL tun, es sind jedoch entweder rekursive Unterauswahlen oder viele Abfragen erforderlich. Mach es besser in deinem Code.

Wenn es mehrere Abhängigkeiten gibt, wie zum Beispiel Fire Punchabhängig von PunchUND, Immolationverwenden Sie zwei Tabellen, um das Abhängigkeitsdiagramm darzustellen:

#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
Jonas Bötel
quelle
Ihre UserTalentTabelle benötigt keine Autokey-Spalte. userund talentkönnen die einzigen zwei Spalten und ein zusammengesetzter Schlüssel sein: Sie werden niemals Duplikate sein und Sie werden idsowieso niemals eine Abfrage durchführen .
doppelgreener
Ich bin kein Datenbankdesigner und würde mich freuen, wenn jemand dazu sagt: Wenn jedes Talent einen eindeutigen Namen hätte, könnten Sie nicht auch jedes andere numerische ID - Feld in diesem Tabellenentwurf entfernen und Namen als Schlüssel verwenden (mit irgendwelche Änderungen kaskadiert)? Wäre dies mit erheblichen Kosten oder Vorteilen verbunden?
doppelgreener
3
@ Jonathan Hobbs: Eine Autoincrement-Primär-ID ist immer gut für Lösch- / Aktualisierungsvorgänge geeignet. Es ist nie langsamer, aber oft schneller. Auch die Zeilengröße spielt hier keine Rolle. Gleiches gilt auch für den Fall eindeutiger Talentnamen. Um eine gute Leistung zu erzielen, sollten Sie Ihre Tabellen nur mit eindeutigen Ganzzahlen verknüpfen. Siehe en.wikipedia.org/wiki/Database_normalization usw.
Jonas Bötel
Vielen Dank. Ein DB-Designer, den ich kannte, erklärte einmal, dass Autoschlüssel böse seien und vermieden werden sollten, aber ich war mir nie sicher, ob das der Fall ist oder warum. Ich nehme an, es ist nicht so.
Doppelgreener
Es gibt keinen wirklichen Grund, eine Datenbank zum Speichern dieser Daten zu verwenden, es sei denn, Sie benötigen eine Datenbank für Designer, da Sie die Mehrbenutzerbearbeitung oder ähnliches unterstützen. Andernfalls wird es nur in die Quere kommen. (Ich würde auch niemals einen primären Autoincrement-Schlüssel verwenden, da Sie mit ziemlicher Sicherheit logische Namen verwenden möchten, die von einem Designer anstelle eines von der
5

Ich würde empfehlen, einen Baum zu verwenden, in dem jeder Knoten ein bestimmtes Talent / eine bestimmte Fertigkeit darstellt. Je nachdem, ob der Spieler ein Talent erworben hat oder nicht, können seine Kindertalente erworben werden. Zum Beispiel die folgende Datenstruktur

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

Um festzustellen, über welche Talente ein Spieler verfügt, nehmen Sie das Stammtalent und gehen den Graphen entlang, bis Sie die Talentknoten erreichen, bei denen das Erreichte falsch ist. Dies zeigt auch, welche Talente für den Erwerb verfügbar sind: Das erste Talent in jedem Zweig nach dem Stammtalent, bei dem es verdient wurde, ist falsch.

Geist
quelle
Sie haben einen Zeiger auf ein natives Array und eine Größe? Verwenden Sie keinen selbstständigen Zeiger zur Größenanpassung.
DeadMG
Whoops ... C / C ++ - Verwechslung und ein Fehler. Ich habe meine Antwort aktualisiert. Danke für das Heads-up.
Geist
@DeadMG: Was genau meinst du mit "Self-Sizing"? Beziehen Sie sich auf etwas wie den obigen Vektor oder haben Sie an etwas anderes gedacht?
Kylotan
Ein Boost ptr_vectorkönnte noch besser sein.
Zan Lynx
5
Die Baumstruktur sollte völlig unabhängig davon sein, ob der Spieler sie verdient hat, die ersteren sind statische Daten, die von Designern erstellt wurden, und die letzteren sind Daten pro Spieler, die in einem Spiel oder einer Datenbank gespeichert sind.
1

In meinem Spiel mache ich das so:

Datenbank:

reference_talent : enthält eine eindeutige ID, einen eindeutigen Namen, einen eindeutigen Effekt usw

talent : id, playerid <- enthält alle Talente, die Spieler "gelernt" haben.

Ingame: (auf dem Server)

Ich lade alle reference_talents in einer 'statischen' (schreibgeschützten) std :: map hoch, damit ich über ihre ID leicht darauf zugreifen kann.

Wenn ein Kunde einen Spieler auscheckt, hole ich mir alle Talente aus der Datenbank und speichere sie in einem std :: vector, sodass ich sie im RAM habe, wenn ich Eigenschaften usw. berechnen muss. Ich schicke auch die Talente an den Kunden.

Das war's auch schon (außer natürlich neue Talente einzusparen, was nur ein 'EINFÜGEN' in die Tabelle 'Talent' + eine Nachricht an den Kunden ist).

Valmond
quelle
0

Relationaler Ansatz

Sie beschreiben es als Beziehung zwischen Unlockern und Unlocked, ähnlich wie in diesem Tutorial . Ich schlage vor, mehr über relationale Algebra und Datenbanken zu lernen. Sie sind eine gute Möglichkeit, Daten zu modellieren. Wenn Sie lernen, wie Sie Informationen aus der Datenbank abfragen können, können Sie ganz einfach Daten modellieren.

Ich weiß nicht, wie viel Sie über das Modellieren von Beziehungen wissen. Dieses Tutorial soll Ihnen dabei helfen.

Eine Lösung

Ich gehe davon aus, dass WoW wie in der Realität funktioniert (ehm), dass es so ist

  • Talent setzt mehrere (andere) Talente frei
  • Talent wird von mehreren (anderen) Talenten freigeschaltet.

Es ist eine N: N-Beziehung, die impliziert, dass Sie "Mittelmann" eine neue Beziehung zwischen den beiden Talenten brauchen:

(talent who unlocks id, talent who is unlocked)

Auf diese Weise können Sie Talent A haben, das B, C und D ((A, B), (A, C), (A, D) und Talent Y freigeschaltet durch X, Z und W ((X, Y), ( Z, Y), (W, Y)). In imperativer / prozeduraler / objektorientierter Sprache würden Sie dies als Liste / Array von Paaren wie folgt tun:

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

Als "reales" Beispiel können Sie also Folgendes haben:

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

und es bedeutet, dass "Superhochspringen" erreicht wird, nachdem Sie Talente "schnell laufen" und "Antigravitationskind" haben.

Andere Lösung

Ich habe Diablo in letzter Zeit nicht gespielt, aber es könnte sein, dass es nur:

  • Talent schaltet mehrere andere Talente frei
  • Talent wird nur von einem Talent freigeschaltet.

Es ist 1: N Beziehung:

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

mögen:

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