有效的方法来检查必要条件以获得角色扮演游戏平台的能力

I'm developing a Role-Playing-Game Web Platform to manage in-game characters. I'm using PHP and MySql. Here is my problem : i need an efficient and easy way to check if a player has the requisites to get an ability.I just need an hint to structure the database.Currently here is the DB structure(just the necessary part to resolve my problem):

Abilities:

This table stores my abilities.

|Ability ID|Name|Cost|

Competences :

This table stores, for each character, what are his abilities.

|Character ID(references the character)|Ability ID(references the ability id)|

When a character tries to learn a new ability, i need to check if it knows the required abilities to learn the new one. I need to check things like(for example):

Swords && Shield
Swords && almost 2 of the following : (Alchemy,Potions,Brawling,Archery)
Swords || ( Archery && Fencing)

What's the best way to store those requirements? Thank you

I don't think you can do this with less than two additional tables in a fully normalized fashion.

Table: prerequisites
abilityid  Points to the ability table primary key
prereqid   Primary key of this table
prereqtype AND or OR, essentially

Table: prereq_elements
prereqid   Points to prerequisites table
abilityid  Points to ability table

Each entry in the prerequisites table defines a requirement need to purchase the ability referenced by abilityid. That 'requirement' is defined as a set of things referenced in the prereq_elements table. If the prereq type is 'and', every ability referenced in prereq_elements must be possessed by the character for the prereq to be satisfied. If it is 'or', any one of the abilities will do.

If you have a manageable number of abilities, you might consider looking at each one as a bit-wise integer value and using a bitmask to determine if specific requirements are met. This might be presented best with example tables:

abilities:

ability_id  name         bit_value cost
1           swords       1         ?
2           shield       10        ?
3           alchemy      100       ?
4           potions      1000      ?
5           brawling     10000     ?
6           archery      100000    ?
7           fencing      1000000   ?
8           new ability  10000000  ?

ability_bitmasks

   bitmask_id  bitmask      notes
   1            11            swords && shield
   2            101           swords && alchemy
   3            1001          swords && potions
   4            10001         swords && brawling
   5            100001        swords && archery      
   6            1             swords
   7            1100000       archery && fencing

Note that I am showing both swords and archery && fencing related to your suggested rule of swords || (archery && fencing) This rule however does not make logical sense as this renders all the other requirements (numbers 1-5 on the table above) moot as having only swords would suffice for the ability. I also split these on two lines as logical equivalent is having 4 rules instead of the 3 initially noted.

Next, you need a table to map the available abilities to the bitmasks which would "unlock" them.

ability_to_bitmasks

  ability_id   bitmask_id
  8            1
  8            2
  8            3
  8            4
  8            5
  8            6
  8            7

Now you would simply have a bitmask of all abilities your character currently has with which you could compare against the bitmask table to see which rules are satisfied. The query might look like this:

SELECT bitmask_id FROM ability_bitmasks WHERE bitmask & [your character's input bitmask] != 0

Or to take it a step further, you could get the eligible abilities via JOIN

SELECT DISTINCT
a.ability_id AS ability_id,
a.name AS name,
a.cost AS cost
FROM ability AS a
INNER JOIN ability_to_bitmasks AS atb on a.ability_id = atb.ability_id
INNER JOIN ability_bitmasks AS ab on atb.bitmask_id = ab.bitmask_id
WHERE ab.bitmask & [your character's input bitmask] != 0

So say you have a character with abilities - sword, potions, and archery. The bitmask would be:

101001

A query using this bitmask would trigger bitmask ID's 3, 5, and 6 which all have references to ability id 8.

Also note that you can use an integer field instead of a bit field if you like (with values 1, 2, 4, 8, 16, 32, ...) and use bitwise comparison on the integers. This might actually be easier to work with from in data management standpoint. I simply chose to use bit fields in this example, as hopefully it illustrates the usage a little better.

What about expressions? I would store in the prerequisites table strings to represent prerequisites. For example:

14 && 15 && 16 would represent "i need every ability with a certain ID"
14 && 3(15,16,17,19,20,21) would represent "i need ability 14 and 3 of the following abilities.

Then, using PHP, i could check the prerequisite parsing the string at runtime.

I was thinking about using two tables.

The first

Prereq_expression

|Ability ID(references the ability)| Expression|

Would contain the ID of the ability and the expression to get it(as i showed in the previous answer).

The second:

Prereq

|Ability ID(references the ability)|Prereq ID(references the needed ability)|

With this approach(redundance) i could easily answer " What abilities have ability with ID 20 as prerequisite?" querying the second table, while i could evaluate the requirements parsing expression in the first table.

However, this requires the consistence between the two tables, but, in my platform, changing an ability requirements means "the game master has changed the rulebook", which is a very rare operation... What do you think about?