Bitmasking too many values

[NickThissen]

Hi,

I am writing an administration tool for a game. I have a list of weapons in the game, and each weapon has a unique Id (numeric). Until recently I had this Id just 0, 1, 2, 3, etc...

Now however I need some way to allow the user to restrict use of some weapons, and store that information in an Access database. The most obvious approach I thought was to give the weapons Ids that were powers of two: 1, 2, 4, 8, 16, etc... This way, a user can check a number of weapons (via checkboxes or whatever), and I simply store the sum of their Ids in the database. Then I can use a bitmask and the bitwise And operator to check which weapons are restricted and which aren't.

Example: the user selects weapons with Id 2, 4 and 16. The database then stores the value 2+4+16 = 22.
Later, I come around and want to check if some weapon is restricted. I then take the bitwise AND operator of 22 and the Id of that weapon. If the result is the Id of the weapon, that means the weapon is restricted. Just the usual bitmasking...

Suppose the weapon Id is 8 then we have: 22 And 8 = 0. Nope, weapon 8 is not restricted!
Another weapon with Id 4 then: 22 And 4 = 4. Yep, weapon 4 is restricted!


Anyway... Long story short: that won't work for the simple reason that I have too many weapons! There are 81 weapons (and counting...) if I counted correctly, which means I'd need values up to 2^81. As far as I know no integer value type in .NET supports numbers that high, except perhaps the BigInteger. But remember: I have to store those Ids in the database as well (theoretically even up to 2^82 - 1 if the user decides to restrict every weapon), and I don't think an Access database supports anything over 2^64 (long)...?



Can anyone come up with a solution to this problem? Am I overlooking obvious solutions?

I did come up with one possible solution, but don't really like it. I could put weapons in their own 'category' (there are logical divisions already so that's easy) and start the count from 1 in each category. Then there would be no more then 15-20 weapons per category so those numbers are not too large (2^20). However then I'd have to store the restricted weapons for each category separately (resulting in quite a large table, there would be about 10-12 categories). I also need to store single weapons in another table, in that case I'd also have to add a column that stores the category of that weapon.
All in all, a lot of cumbersome work arounds that might not be necessary...

Anything else I can do to avoid having to work with numbers up to 2^82..?

[ForumAccount]

How about an 81 character long binary string? It would always have to be 81 characters (to maintain indexes). Each character is either a '1' or a '0'. And, either in code, or the database you would correlate a character index to a weapon. Wouldn't be hard to make a class that wraps around that in code for checking. So instead of a number that you store, it's a string.

[NickThissen]

Hm, that's a good idea. So the weapons would then just have ids 0,1,2,3.. corresponding to the index in the string. I suppose it could work although it's not very flexible should I ever need to add/remove weapons.

I'm going to wait for some more suggestions but I'll probably end up using this, thanks!

[ForumAccount]

Adding and removing isn't a problem. You just leave "removed" weapons in the string (i.e. don't ever change existing indexes). And adding weapons just means adding indexes. But yeah, It would be cool to see a bit masking solution.

[jmcilhinney]

You could use the BigInteger type in VB as normal. In the database, either use text or a non-integer numeric type to store the data. To convert just use the ToString and Parse/TryParse methods of the BigInteger type. BigInteger also has a Pow method, so you can just raise 2 to the power of the weapon index as usual to get the appropriate BigInteger mask.

[Zeljko]

Why don't you create another Column in database with Boolean set to False if Weapon is not Enabled in Game, or True if it is Enabled in Game?

[jmcilhinney]

Why don't you create another Column in database with Boolean set to False if Weapon is not Enabled in Game, or True if it is Enabled in Game?

I think the issue is that there is a Weapon table and a User table and your solution would require another table with a record for every combination of WeaponID and UserID and an extra column for IsEnabled. That's not the end of the world but it is a lot more records. You could always omit the extra column and then only include records for weapons that were enabled or weren't enabled. I think the idea here is to just have one extra column in the User table that handles every weapon for every user. Probably not ideal from a database design perspective but probably more efficient.

[NickThissen]

That's not exactly my database design, but it's close. It's actually two tables that ever store information about the weapons. I have one table with 'kills' where each time someone kills someone else I store the id of the attacker, the id of the victim and the id of the weapon that was used (amongst some other data). In this case, there's always just one weapon so here I could use regular weapon ids of 0,1,2,3,4 etc.

Then I also have a table that stores restrictions for every game server. Some weapons are not allowed to be used; however there is no way for anyone to control that from within the game, so these kind of tools simply check if a kill was made with a restricted weapon and warn (eventually 'kick') the attacker.
My app can control multiple game servers and each entry in the Restrictions table correspond to one of those servers. The Restrictions table thus has columns ServerId and Weapons, where this time Weapons should be a bitwise combination of all the restricted weapons on that server. This is where I need the bitmasked values so the weapon Ids need to be 1,2,4,8,etc. And this is where I run into trouble because there are simply not enough powers of two in the integer/long types.

If I had a boolean column for every weapon that would mean the Restrictions table would get over 85 columns; I think that's a bit much.

Finally, the weapons themselves are not in the database, I define and add them in code. The reason is that, so far at least, no changes in the weapons have been made to the game (so I don't think I'll ever need to change them) and more importantly, a change in the weapons would require a new build anyway.



Ok, so far I have to viable solutions:
1. Use a binary string where each character represents the restricted state of a weapon,
2. Use the BigInteger and store the result as text in the database.

Which is the most efficient / fast method? My app is reading new log lines every 5 seconds, and it might get as much as 50 new lines in that time. If all of those are Kill/Damage events (damage events are just when someone gets shot but not deadly yet) then I would need to check if a weapon is restricted 50 times in a row. Handling one such event thus should take no longer than 0.1 second.

My code that handles a Kill event (a Damage event is similar except using a different table) is basically:

Dim attacker As Player = GetAttacker()
Dim victim As Player = GetPlayer()
Dim weapon As Weapon = ParseWeapon(code)

Dim kill As New Kill(attacker, victim, weapon)
KillManager.Instance.Save(kill)

If Restrictions.IsWeaponRestricted(weapon) Then
    MessageManager.WarnPlayer(player, weapon)
End If

The IsWeaponRestricted method when I decide to use option 1 would be something like

Public Shared Function IsWeaponRestricted(weapon As Weapon) As Boolean
    Dim restricted As String = Me.Server.Restrictions.Weapons  'the binary string
    Return restricted(weapon.Id) = "1"
End Function

For option 2 I guess it would look like

Public Shared Function IsWeaponRestricted(weapon As Weapon) As Boolean
    Dim restricted As String = Me.Server.Restrictions.Weapons  'the BigInteger string
    Dim int As BigInteger = BigInteger.Parse(restricted)
    Return (int And weapon.Id) = weapon.Id
End Function

So option 1 is merely finding a character at a specified index while option 2 needs to parse a string into a BigInteger and then use bitwise logic. At a guess I would say option 1 is faster, but I might be underestimating the BigInteger, I've never used it...

I'll test this as soon as I can (at the moment my project doesn't build), but maybe someone has some thoughts about this?

[ForumAccount]

Would you actually have to retrieve the weapons string each time you make that call? Does it have the ability to change at any time? Could you just store sort of a, Singleton, of each player's restricted weapons? If so, that would definitely speed up the call.

[NickThissen]

I didn't show that in detail in my example (which is wrong now as I see I used 'Me' in a shared function ) but for all intents and purposes the Restrictions class is a singleton. There is actually one instance per server. The Server object is loaded whenever the user makes a change to the rules of that server. Those rules include the restricted weapons. (I notice everyone seems to think weapons are restricted on a 'per player' basis, but actually each server has just one set of restricted weapons and every player on that server will be warned for using any of them).

Anyway, to answer your question, the binary string comes from memory (except the first time it is loaded which would be every time the user makes a change to the server options, which will be almost never) so it does not require a trip to the database every time.

Retrieving the binary string (or the string representing the BigInteger) will not be the slow part of the process, it is indexing the binary string or doing bitwise operations on a BigInteger that is probably going to be the slowest. As far as I know indexing a string like this should be very quick, whereas I can imagine using bitwise AND on a BigInteger would be extremely slow in comparison. Note I am not counting parsing the string into a BigInteger anymore (I was in my previous post, mistake) because of course I can just do that once and store it in memory as soon as the Server object is loaded from the database.

[ThomasJohnsen]

Personally I wouldn't go for a bitmask at all.
A table of weapons with a unique key (like you already have), a table of users and a table of inventory with no primary key but two indexed columns into both tables is both very readable, easily changeable and fast. It will of course be much less space-efficient than the bitfield solution.
By omitting a primary key in the third table, you will allow users to have multiple instances of the same weapon (which bitfields of course won't allow), or you can add a primary key consisting of both fields to avoid multiple instances.
A question like 'does the user have a resticted weapon' can be answered in constant time (similar to bitfileds) due to indexing with simple sql.

Just my $0.02