Какую структуру данных я должен использовать для дерева талантов в стиле Diablo / WoW?
23
Я подумываю о внедрении системы дерева талантов для онлайновой RPG, подобной той, что была замечена в World of Warcraft, где приобретение навыка открывает следующий «уровень» под ним в дереве.
Кто-нибудь знает, как лучше реализовать это структурно в базе данных / коде?
Используйте такую структуру, чтобы представить дерево в базе данных:
#Talent
id parent description
10Tackle21Kick31Punch43FirePunch
И еще одна таблица для представления приобретенных талантов на пользователя
#UserTalent
id user talent
141243344
Вы можете программно проверять зависимости талантов, запрашивая полную таблицу талантов и создавая связанное дерево. Вы также можете сделать это с SQL, но это потребует либо рекурсивных вложенных выборок, либо большого количества запросов. Лучше сделай это в своем коде.
Если существует несколько зависимостей, как, например, Fire Punchзависит от PunchAND, Immolationиспользуйте две таблицы для представления графа зависимостей:
#Talent
id description
1Tackle2Kick3Punch4FirePunch5Immolation#Depedency
id parent child
101205312413534654
Ваша UserTalentтаблица не нуждается в колонке автоключей. userи talentмогут быть только два столбца и составной ключ: они никогда не будут дубликатами, и вы никогда не будете запрашивать в idлюбом случае.
Доппельгринер
Я не дизайнер баз данных, и мне было бы интересно услышать, как кто-то скажет по этому поводу: если бы у каждого таланта было уникальное имя, не могли бы вы также покончить со всеми другими полями числовых идентификаторов в этом дизайне таблицы и использовать имена в качестве ключей (с какие-либо правки каскадно)? Будут ли в этом какие-либо значительные затраты или выгоды?
doppelgreener
3
@Jonathan Hobbs: первичный идентификатор автоинкремента всегда хорош для операций удаления / обновления. Это никогда не медленнее, но часто быстрее. Также размер строки здесь не имеет значения. То же самое относится и к случаю уникальных имен талантов. Для хорошей производительности вы захотите объединить свои таблицы только с уникальными целыми числами. См en.wikipedia.org/wiki/Database_normalization и т.д.
Jonas BOTEL
Спасибо. Дизайнер БД, которого я знал однажды, заявил, что автоключи - это зло, и их следует избегать, но мне никогда не было ясно, так ли это или почему. Я полагаю, это не так.
Доппельгринер
Нет реальной причины использовать базу данных для хранения этих данных, если вам не нужна база данных для дизайнеров, потому что вы поддерживаете многопользовательское редактирование или что-то в этом роде. В противном случае это будет только мешать. (Я бы также никогда не использовал первичный ключ автоинкремента для этого, потому что вы почти наверняка захотите присоединиться к логическим именам,
5
Я бы порекомендовал использовать дерево, где каждый узел представляет определенный талант / навык. В зависимости от того, заработал ли игрок талант, его детские таланты могут быть заработаны. Например, следующая структура данных
Чтобы определить, какие таланты есть у игрока, вы берете основной талант и идете вниз по графику, пока не достигнете узлов талантов, где заработанное значение является ложным. Это также покажет, какие таланты доступны для получения: первый талант в каждой ветви от корневого таланта, где заработано, является ложным.
У вас есть указатель на собственный массив и размер? Fail - использовать самозаводящийся указатель самоконтроля.
DeadMG
Упс ... C / C ++ путаница и ошибка. Я обновил свой ответ. Спасибо за хедз-ап.
призрак
@DeadMG: что именно вы подразумеваете под «самооценкой»? Ты имеешь в виду что-то похожее на вектор выше, или ты думал о другом?
Килотан
Повышение ptr_vectorможет быть даже лучше.
Zan Lynx
5
Древовидная структура должна быть полностью отделена от того, заработал ли ее игрок, первая - это статические данные, сделанные дизайнерами, а вторая - данные для каждого игрока, сохраненные в сохраненной игре или БД.
1
В моей игре я делаю это так:
База данных:
reference_talent : содержит уникальный идентификатор, имя, эффект и т. д.
talent : id, playerid <- содержит все таланты, которые «усвоили» игроки.
Внутриигровая: (на сервере)
Я загружаю все reference_talents в «статический» (только для чтения) std :: map, чтобы я мог легко получить к ним доступ по их идентификатору.
Когда клиент проверяет игрока, я извлекаю все таланты из базы данных и сохраняю их в std :: vector, так что когда мне нужно вычислить характеристики и т. Д., Я получаю их в оперативной памяти. Я также отправляю таланты клиенту.
Вот и все (кроме сохранения новых талантов, конечно, это просто «ВСТАВКА» в таблице «талант» + сообщение для клиента).
Вы описываете это как отношение между разблокировщиками и разблокированными, как в этом уроке . Я предлагаю узнать больше о реляционной алгебре и базах данных. Это хороший способ для моделирования данных. Если вы научитесь запрашивать информацию из базы данных, вы можете легко смоделировать данные.
Я не знаю, сколько Вы знаете о модельных отношениях. Этот урок должен помочь вам в этом.
Одно решение
Я предполагаю, что 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]];
UserTalent
таблица не нуждается в колонке автоключей.user
иtalent
могут быть только два столбца и составной ключ: они никогда не будут дубликатами, и вы никогда не будете запрашивать вid
любом случае.Я бы порекомендовал использовать дерево, где каждый узел представляет определенный талант / навык. В зависимости от того, заработал ли игрок талант, его детские таланты могут быть заработаны. Например, следующая структура данных
Чтобы определить, какие таланты есть у игрока, вы берете основной талант и идете вниз по графику, пока не достигнете узлов талантов, где заработанное значение является ложным. Это также покажет, какие таланты доступны для получения: первый талант в каждой ветви от корневого таланта, где заработано, является ложным.
источник
ptr_vector
может быть даже лучше.В моей игре я делаю это так:
База данных:
reference_talent : содержит уникальный идентификатор, имя, эффект и т. д.
talent : id, playerid <- содержит все таланты, которые «усвоили» игроки.
Внутриигровая: (на сервере)
Я загружаю все reference_talents в «статический» (только для чтения) std :: map, чтобы я мог легко получить к ним доступ по их идентификатору.
Когда клиент проверяет игрока, я извлекаю все таланты из базы данных и сохраняю их в std :: vector, так что когда мне нужно вычислить характеристики и т. Д., Я получаю их в оперативной памяти. Я также отправляю таланты клиенту.
Вот и все (кроме сохранения новых талантов, конечно, это просто «ВСТАВКА» в таблице «талант» + сообщение для клиента).
источник
Реляционный подход
Вы описываете это как отношение между разблокировщиками и разблокированными, как в этом уроке . Я предлагаю узнать больше о реляционной алгебре и базах данных. Это хороший способ для моделирования данных. Если вы научитесь запрашивать информацию из базы данных, вы можете легко смоделировать данные.
Я не знаю, сколько Вы знаете о модельных отношениях. Этот урок должен помочь вам в этом.
Одно решение
Я предполагаю, что WoW работает как на самом деле (эм), что это
Это отношение N: N, которое подразумевает, что «среднему человеку» нужно новое отношение между двумя талантами:
Таким образом, вы можете иметь талант A, разблокирующий B, C и D ((A, B), (A, C), (A, D)) и талант Y, разблокированный с помощью X, Z и W ((X, Y), ( Z, Y), (W, Y)). В императивном / процедурном / объектно-ориентированном языке вы бы сделали это в виде списка / массива пар, например:
Так что для «реального» примера Вы можете иметь:
и это означает, что «сверхскоростной прыжок» получается после того, как у вас есть «быстро бегать» и «антигравитационные дитя».
Другое решение
Я не играл в Diablo в последнее время, но, возможно, это было только:
Это отношение 1: N:
нравится:
источник