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?