Какую структуру данных я должен использовать для дерева талантов в стиле Diablo / WoW?

23

Я подумываю о внедрении системы дерева талантов для онлайновой RPG, подобной той, что была замечена в World of Warcraft, где приобретение навыка открывает следующий «уровень» под ним в дереве.

Кто-нибудь знает, как лучше реализовать это структурно в базе данных / коде?

RSH1
источник

Ответы:

13

Используйте такую ​​структуру, чтобы представить дерево в базе данных:

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

И еще одна таблица для представления приобретенных талантов на пользователя

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

Вы можете программно проверять зависимости талантов, запрашивая полную таблицу талантов и создавая связанное дерево. Вы также можете сделать это с SQL, но это потребует либо рекурсивных вложенных выборок, либо большого количества запросов. Лучше сделай это в своем коде.

Если существует несколько зависимостей, как, например, Fire Punchзависит от PunchAND, Immolationиспользуйте две таблицы для представления графа зависимостей:

#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
Йонас Бетел
источник
Ваша UserTalentтаблица не нуждается в колонке автоключей. userи talentмогут быть только два столбца и составной ключ: они никогда не будут дубликатами, и вы никогда не будете запрашивать в idлюбом случае.
Доппельгринер
Я не дизайнер баз данных, и мне было бы интересно услышать, как кто-то скажет по этому поводу: если бы у каждого таланта было уникальное имя, не могли бы вы также покончить со всеми другими полями числовых идентификаторов в этом дизайне таблицы и использовать имена в качестве ключей (с какие-либо правки каскадно)? Будут ли в этом какие-либо значительные затраты или выгоды?
doppelgreener
3
@Jonathan Hobbs: первичный идентификатор автоинкремента всегда хорош для операций удаления / обновления. Это никогда не медленнее, но часто быстрее. Также размер строки здесь не имеет значения. То же самое относится и к случаю уникальных имен талантов. Для хорошей производительности вы захотите объединить свои таблицы только с уникальными целыми числами. См en.wikipedia.org/wiki/Database_normalization и т.д.
Jonas BOTEL
Спасибо. Дизайнер БД, которого я знал однажды, заявил, что автоключи - это зло, и их следует избегать, но мне никогда не было ясно, так ли это или почему. Я полагаю, это не так.
Доппельгринер
Нет реальной причины использовать базу данных для хранения этих данных, если вам не нужна база данных для дизайнеров, потому что вы поддерживаете многопользовательское редактирование или что-то в этом роде. В противном случае это будет только мешать. (Я бы также никогда не использовал первичный ключ автоинкремента для этого, потому что вы почти наверняка захотите присоединиться к логическим именам,
5

Я бы порекомендовал использовать дерево, где каждый узел представляет определенный талант / навык. В зависимости от того, заработал ли игрок талант, его детские таланты могут быть заработаны. Например, следующая структура данных

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

Чтобы определить, какие таланты есть у игрока, вы берете основной талант и идете вниз по графику, пока не достигнете узлов талантов, где заработанное значение является ложным. Это также покажет, какие таланты доступны для получения: первый талант в каждой ветви от корневого таланта, где заработано, является ложным.

призрак
источник
У вас есть указатель на собственный массив и размер? Fail - использовать самозаводящийся указатель самоконтроля.
DeadMG
Упс ... C / C ++ путаница и ошибка. Я обновил свой ответ. Спасибо за хедз-ап.
призрак
@DeadMG: что именно вы подразумеваете под «самооценкой»? Ты имеешь в виду что-то похожее на вектор выше, или ты думал о другом?
Килотан
Повышение ptr_vectorможет быть даже лучше.
Zan Lynx
5
Древовидная структура должна быть полностью отделена от того, заработал ли ее игрок, первая - это статические данные, сделанные дизайнерами, а вторая - данные для каждого игрока, сохраненные в сохраненной игре или БД.
1

В моей игре я делаю это так:

База данных:

reference_talent : содержит уникальный идентификатор, имя, эффект и т. д.

talent : id, playerid <- содержит все таланты, которые «усвоили» игроки.

Внутриигровая: (на сервере)

Я загружаю все reference_talents в «статический» (только для чтения) std :: map, чтобы я мог легко получить к ним доступ по их идентификатору.

Когда клиент проверяет игрока, я извлекаю все таланты из базы данных и сохраняю их в std :: vector, так что когда мне нужно вычислить характеристики и т. Д., Я получаю их в оперативной памяти. Я также отправляю таланты клиенту.

Вот и все (кроме сохранения новых талантов, конечно, это просто «ВСТАВКА» в таблице «талант» + сообщение для клиента).

Valmond
источник
0

Реляционный подход

Вы описываете это как отношение между разблокировщиками и разблокированными, как в этом уроке . Я предлагаю узнать больше о реляционной алгебре и базах данных. Это хороший способ для моделирования данных. Если вы научитесь запрашивать информацию из базы данных, вы можете легко смоделировать данные.

Я не знаю, сколько Вы знаете о модельных отношениях. Этот урок должен помочь вам в этом.

Одно решение

Я предполагаю, что WoW работает как на самом деле (эм), что это

  • Талант открывает несколько (других) талантов
  • Талант разблокирован несколькими (другими) талантами.

Это отношение N: N, которое подразумевает, что «среднему человеку» нужно новое отношение между двумя талантами:

(talent who unlocks id, talent who is unlocked)

Таким образом, вы можете иметь талант A, разблокирующий B, C и D ((A, B), (A, C), (A, D)) и талант Y, разблокированный с помощью X, Z и W ((X, Y), ( Z, Y), (W, Y)). В императивном / процедурном / объектно-ориентированном языке вы бы сделали это в виде списка / массива пар, например:

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

Так что для «реального» примера Вы можете иметь:

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

и это означает, что «сверхскоростной прыжок» получается после того, как у вас есть «быстро бегать» и «антигравитационные дитя».

Другое решение

Я не играл в Diablo в последнее время, но, возможно, это было только:

  • талант открывает несколько других талантов
  • Талант разблокирован только одним талантом.

Это отношение 1: N:

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

нравится:

 var Talent[8] = { "name": "superpower", "unlocked by": "being Clark Kent"};
user712092
источник