Struktur data apa yang harus saya gunakan untuk pohon talenta gaya Diablo / WoW?

23

Saya sedang mempertimbangkan menerapkan sistem pohon-bakat untuk RPG online, mirip dengan yang terlihat di World of Warcraft, di mana memperoleh keterampilan membuka "tingkat" berikutnya di bawahnya di pohon.

Adakah yang tahu cara terbaik untuk mengimplementasikan ini secara struktural dalam database / kode?

RSH1
sumber

Jawaban:

13

Gunakan struktur seperti ini untuk mewakili pohon dalam database:

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

Dan tabel lain untuk mewakili talenta yang diperoleh per pengguna

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

Anda dapat memeriksa dependensi bakat secara pemrograman dengan menanyakan tabel bakat lengkap, dan membangun pohon yang ditautkan. Anda juga dapat melakukannya dengan SQL tetapi akan membutuhkan subselect rekursif atau banyak pertanyaan. Lebih baik melakukannya dalam kode Anda.

Jika ada beberapa dependensi, seperti misalnya Fire Punchtergantung pada PunchDAN Immolationmenggunakan dua tabel untuk mewakili grafik dependensi:

#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
sumber
UserTalentTabel Anda tidak memerlukan kolom otokey. userdan talentbisa menjadi hanya dua kolom dan kunci komposit: mereka tidak akan pernah menjadi duplikat dan Anda tidak akan pernah bertanya id.
doppelgreener
Saya bukan perancang basis data dan saya akan tertarik mendengar pendapat orang tentang ini: Jika setiap bakat memiliki nama yang unik, bisakah Anda juga tidak menghapus setiap bidang ID numerik lainnya dalam desain tabel ini, dan menggunakan nama sebagai kunci (dengan ada suntingan yang mengalir)? Apakah akan ada biaya atau manfaat yang signifikan dalam melakukannya?
doppelgreener
3
@Jonathan Hobbs: ID primer autoincrement selalu bagus untuk operasi hapus / perbarui. Tidak pernah lebih lambat tetapi seringkali lebih cepat. Ukuran baris juga tidak menjadi perhatian di sini. Hal yang sama juga berlaku untuk kasus nama-nama bakat unik. Untuk kinerja yang baik, Anda ingin bergabung dengan tabel Anda hanya pada bilangan bulat unik. Lihat en.wikipedia.org/wiki/Database_normalization dll.
Jonas Bötel
Terima kasih. Seorang desainer DB yang saya kenal pernah menyatakan bahwa autokeys itu jahat dan harus dihindari, tetapi saya tidak pernah jelas apakah itu masalahnya atau mengapa. Saya kira tidak.
doppelgreener
Tidak ada alasan nyata untuk menggunakan database untuk menyimpan data ini kecuali Anda memerlukan database untuk desainer karena Anda mendukung pengeditan multi-pengguna atau sesuatu. Kalau tidak, itu hanya akan menghalangi. (Saya juga tidak akan pernah menggunakan kunci autoincrement primer untuk ini, karena Anda hampir pasti ingin bergabung dengan nama logis yang diputuskan oleh seorang desainer daripada kunci yang disediakan DB.)
5

Saya akan merekomendasikan menggunakan pohon di mana setiap node mewakili bakat / keterampilan tertentu. Berdasarkan pada apakah pemain memiliki talenta atau tidak, talenta anaknya dapat diperoleh. Misalnya struktur data berikut

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

Untuk menentukan talenta yang dimiliki pemain, Anda mengambil talenta root dan berjalan menuruni grafik sampai Anda mencapai titik talenta di mana yang diperoleh adalah salah. Ini juga akan mengungkapkan talenta mana yang tersedia untuk diperoleh: talenta pertama di setiap cabang turun dari talenta root di mana yang diperoleh adalah salah.

hantu
sumber
Anda punya pointer ke array asli dan ukuran? Gagal menggunakan penunjuk ukuran sendiri milik sendiri.
DeadMG
Whoops ... C / C ++ mixup dan kesalahan. Saya telah memperbarui jawaban saya. Terimakasih atas peringatannya.
hantu
@DeadMG: apa sebenarnya yang Anda maksud dengan 'memiliki sendiri ukuran'? Apakah Anda mengacu pada sesuatu seperti vektor di atas, atau apakah Anda memikirkan sesuatu yang lain?
Kylotan
Peningkatan ptr_vectormungkin lebih baik.
Zan Lynx
5
Struktur pohon harus sepenuhnya terpisah dari apakah pemain telah mendapatkannya, yang pertama adalah data statis yang dibuat oleh desainer dan yang terakhir adalah data per pemain yang disimpan dalam save game atau DB.
1

Dalam permainan saya, saya melakukannya seperti ini:

Basis data:

reference_talent : berisi ID unik, nama, efek dll

talent : id, playerid <- berisi semua talenta yang telah "dipelajari" oleh pemain.

Ingame: (di server)

Saya memuat semua reference_talents dalam std :: map 'statis' (hanya baca) sehingga saya dapat mengaksesnya dengan mudah dengan id mereka.

Ketika seorang klien memeriksa pemain saya mendapatkan semua talenta dari database dan menyimpannya dalam std :: vector sehingga ketika saya harus menghitung karakteristik, dll. Saya memilikinya di RAM. Saya juga mengirim talenta kepada klien.

Itu saja (kecuali menabung talenta baru tentu saja yang hanya merupakan 'INSERT' di tabel 'talenta' + pesan kepada klien).

Valmond
sumber
0

Pendekatan relasional

Anda menggambarkannya sebagai hubungan antara unlocker dan unlocked yang serupa seperti pada tutorial ini . Saya menyarankan untuk belajar lebih banyak tentang aljabar dan basis data relasional. Mereka adalah cara yang bagus untuk memodelkan data. Jika Anda belajar cara menanyakan informasi dari basis data, Anda dapat memodelkan data dengan cukup mudah.

Saya tidak tahu seberapa banyak Anda tahu tentang hubungan pemodelan. Tutorial itu akan membantu Anda dengan itu.

Satu solusi

Saya berasumsi bahwa WoW bekerja seperti pada kenyataannya (ehm), memang begitu

  • bakat membuka beberapa bakat (lainnya)
  • bakat dibuka oleh beberapa bakat (lainnya).

Itu adalah relasi N: N, yang menyiratkan Anda membutuhkan "perantara" hubungan baru antara dua talenta:

(talent who unlocks id, talent who is unlocked)

Dengan cara ini Anda dapat memiliki bakat A membuka kunci B, C dan D ((A, B), (A, C), (A, D)) dan bakat Y dibuka oleh X, Z dan W ((X, Y), ( Z, Y), (W, Y)). Dalam bahasa imperatif / prosedural / berorientasi objek Anda akan melakukannya sebagai daftar / array pasangan seperti di sana:

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

Jadi untuk contoh "dunia nyata", Anda dapat memiliki:

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

dan itu berarti bahwa "melompat super" diperoleh setelah Anda memiliki bakat "berlari cepat" dan "anak anti-gravitasi".

Solusi lain

Saya belum pernah bermain Diablo baru-baru ini tetapi mungkin saja, bahwa itu hanya:

  • bakat membuka beberapa bakat lainnya
  • bakat dibuka hanya oleh satu bakat.

Ini adalah relasi 1: N:

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

seperti:

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