Bitmasking

[Cassy]

Well I'm really fricking annoyed with this topic.
I've had two people trying to help me understand this and I really, really appreciate any help.
It's just that all tries to explain bitmasking start somewhere in the middle of the topic instead of the beginning and looking at existing scripts isn't very helpful.


I've received many links, probably these two are the most important ones:
http://pastebin.com/6Jj65wX3
https://github.com/themanaworld/tmwa-se ... -quest.txt


So to start from the beginning:
1. What is bitmasking (in a nutshell!)?
2. Why do we need bitmasking?

If I understood correctly this would be a good (short) answer to both questions:
Bitmasking allows to use many different quest states which is necessary when you want to create a quest in which several tasks can be done in any order.

Example (picking the Witch Cult Quest I'm working on):

Code: Select all

Task    NPC              Description                              Comment
1       Troll Mask Guy   Read the story and accepted the task     -
2       Torch1           Disabled the torch                       Torches 1-9 can be disabled in any order
3       Torch2           Disabled the torch                       Torches 1-9 can be disabled in any order
4       Torch3           Disabled the torch                       Torches 1-9 can be disabled in any order
5       Torch4           Disabled the torch                       Torches 1-9 can be disabled in any order
6       Torch5           Disabled the torch                       Torches 1-9 can be disabled in any order
7       Torch6           Disabled the torch                       Torches 1-9 can be disabled in any order
8       Torch7           Disabled the torch                       Torches 1-9 can be disabled in any order
9       Torch8           Disabled the torch                       Torches 1-9 can be disabled in any order
10      Torch9           Disabled the torch                       Torches 1-9 can be disabled in any order
11      Kalinoir Torch   Defeated Kalinoir                        -
12      Troll Mask Guy   Received first reward                    -
13      Troll Mask Guy   Listened to his offer                    -
14      Troll Mask Guy   Offer accepted, received second reward   -

Since you can disable the 9 torches in any order you would need tons of different states:

• one for "Torch 1 disabled"
• one for "Torch 1+2 disabled"
• one for "Torch 2+3+7 disabled"
• one for "Torch 4+6+8+9 disabled" and so on

But with bitmasking this is easier... if you understood bitmasking.


3. How does bitmasking work?
I would start at this point:
There are different ways to use bitmasking:

• Bytes which have a range of 0-255
• Nibbles which have a range of 0-15
• 2Bits (or TWOBIT) which have a range of 0-3
• Bits which have a range of 0-1

Source (line 13-16)
I think my example shows how to decide between those:
The 9 Torches which require bitmasking only need two states: torch enabled, torch disabled.
Bits can only be 0 or 1, that's perfect, so:
0 = torch enabled, 1 = torch disabled


This is where my understanding stops so far.
In this file there are things like:
TWOBIT_0_SHIFT 0
TWOBIT_0_MASK 3

The documentation sucks so much.
You can see nowhere what that means.
Meanwhile I figured out that I need this file again.
So "TWOBIT_0_SHIFT 0" refers to byte 0 and "TWOBIT_0_MASK 3" refers to the four (0-3) 2Bits in it.
But that's all I understood.
So what are shift and mask doing?
How do I use them?
Also I see Bytes, Nibbles and 2Bits in there, but no Bits?


Phew... I need sleep now, been at this for hours today.
Thanks for every help

[GARRETTtheGREAT]

Intro

I can't speak of the dev team standards, but maybe this will help you understand. Excuse me if I cover a topic you already understand, I figured I'd start from the top.

Basically, we're combining many small data pieces into one larger piece. Bit masks allow us to isolate/or and manipulate these pieces.

The big piece is a 32 bit integer, from what I gather reading your links to the TMWA doc. The "integer" part just means we'll interpret the 32 bits as a counting number (0, 1, 2, 3, ... 4294967295).

Let's imagine you're making a system of keeping track of the quest states. You'll need a different number for each possible state. So, what would that look like?

* 0 - Quest has not been started
* 1 - Quest started, no torches
* 2 - Quest started, torch 1 was disabled
* 3 - Quest started, torch 2 was disabled
...

This is a completely valid system. The problem is that you would have to make a complicated system to keep track of what number means what. That's where using bits comes into play. Each bit is a yes or no question, so we'll say bit # 0 is "quest accepted?". 1 will be "yes" and 0 will be "no". Since we have a 32 bit block of data, we can have 32 yes or no questions.

However, even though it's 32 bits logically, we can only work on the whole chunk at once. That's where binary operations come into play.

Binary Numbers

Let's look at the number system again, but we'll use bits instead of numbers.

* 0000 - Quest has not been started
* 0001 - Quest started, no torches
* 0011 - Quest started, torch 1 was disabled
* 0101 - Quest started, torch 2 was disabled
* 0111 - Quest started, torch 1 and 2 were disabled
...

You can see that that rightmost bit is for quest started, next from the right is torch 1, next to that is torch 2, etc. If we translate that from binary into human-readable numbers we get the numbers 0 (Quest started), 1 (Quest started, no torches), 3 (Quest started, torch 1), 5 (Quest started, torch 2), 7 (Quest started, torch 1 + 2). Each yes or no position is given a value from 2^0 (2 to the power of zero = 1) all the way to 2^31, which gives us 32 positions total. You only add a value for the position if it's a "yes" answer (1). So, for 0101 binary we have (2^0 + 0 + 2^2 + 0) = (1 + 0 + 4 + 0) = 5.

Setting Values

We can set bits by changing the value of the integer. I'm not familiar with the TMWA scripting language (Lua?), so hopefully I've got it right from the example.

set CASSYSQUEST, 0; // Quest has not been started
set CASSYSQUEST, 1; // Quest started, no torches
...

Usually, we're going to be changing only one bit at a time and usually we're going to be adding one yes answer, so let's look at that.

set CASSYSQUEST, CASSYSQUEST | 4; // set bit number 2 (2^2 = 4) to yes in addition to any other bits already set

You'll see the binary OR operator above ("|"). This means if either CASSYSQUEST has bit 2 set, OR the number 4 has bit 2 set (that's the only bit it has set, hence why we chose the number). So, the result of CASSYSQUEST | 4 is going to be the exact same as CASSYSQUEST was before, in addition, bit #2 is set.

Getting Values

We'll need to see if one bit is set as well.

set @cassysquest, CASSYSQUEST & 4; // get if bit number 2 (2^2 = 4) is set

In this example, if bit 2 is set, then @cassysquest will be a number other than zero. If it is not set, it will be zero. We're using the logical AND here ("&"). This means that only the bits that both CASSYSQUEST AND the number 4 have set in common will stay set. In this case the number 4 only has bit number 2 set, so only bit number 2 is checked in CASSYSQUEST.

There's a lot more you'll need to learn with more advanced binary operations, using nybbles and bytes, etc, but hopefully this helps.

Edit:

I think the reason there's so much more for 2bit, nybble, and byte is because these operations are much trickier than than single bit operations. Again, I can't speak of the coding standard to which you would be held, but if I were going to write this quest, I would do something like:

set CASSYSQUEST_STARTED, 1; // bitmask for quest started
set CASSYSQUEST_TORCH1, 2; // bitmask for torch 1 disabled
set CASSYSQUEST_TORCH2, 4; // bitmask for torch 2 disabled
...

If you do this (or maybe there's a better way to set these constants), then you can have your code make a lot more sense:

set @cassysquest_is_started, CASSYSQUEST | CASSYSQUEST_STARTED; // 0 if the quest is not started

if (@cassysquest_is_started) ... // do something if the quest is started

[wushin]

how-to 9 items without any order attached to them.

Code: Select all

001-1.gat,112,44,0|script|Torch0#0|400
{
    set @torch, 0;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,114,44,0|script|Torch1#1|400
{
    set @torch, 1;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,116,44,0|script|Torch2#2|400
{
    set @torch, 2;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,112,46,0|script|Torch3#3|400
{
    set @torch, 3;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,114,46,0|script|Torch4#4|400
{
    set @torch, 4;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,116,46,0|script|Torch5#5|400
{
    set @torch, 5;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,112,48,0|script|Torch6#6|400
{
    set @torch, 6;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,114,48,0|script|Torch7#7|400
{
    set @torch, 7;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,116,48,0|script|Torch8#8|400
{
    set @torch, 8;
    callfunc "ToggleTorch";
    end;
}
001-1.gat,110,44,0|script|Torch Debug|400
{
    mes "[Torch Debug]";
    menu
        "States", L_ShowStates,
        "reset all torches", L_TorchReset,
        "reset cassy var", L_CassyReset;

L_ShowStates:
    callfunc "TorchCount";
    callfunc "GetCassyState";
    mes "Cassy Nibble 3: " + @cassy_state;
    mes "Torches Lit: " + @torch_count;
    goto L_Close;

L_TorchReset:
    set CASSYSQUEST, (CASSYSQUEST & ~(BYTE_0_MASK) | (0 << BYTE_0_SHIFT));
    set CASSYSQUEST, (CASSYSQUEST & ~(NIBBLE_2_MASK) | (0 << NIBBLE_2_SHIFT));
    goto L_Close;

L_CassyReset:
    mes "set CASSYSQUEST between 0-15";
    input @cassy_tmp;
    callfunc "SetCassyState";
    goto L_Close;

L_Close:
    close;
}

function|script|GetCassyState
{
    set @cassy_state, ((CASSYSQUEST & NIBBLE_3_MASK) >> NIBBLE_3_SHIFT);
    return;
}

function|script|SetCassyState
{
    set CASSYSQUEST, (CASSYSQUEST & ~(NIBBLE_3_MASK) | (@cassy_tmp << NIBBLE_3_SHIFT));
    set @cassy_tmp, 0;
    return;
}

function|script|TorchCount
{
    setarray @torches, 0, 1, 2, 3, 4, 5, 6, 7, 8;
    set @loop, 0;
    set @torch_count, 0;
    goto L_Loop;

L_Loop:
    if (CASSYSQUEST & (1 << @torches[@loop]))
        goto L_LoopSet;
    goto L_LoopNext;

L_LoopSet:
    set @torch_count, (@torch_count + 1);
    if (@torch_count == getarraysize(@torches))
        goto L_Complete;
    goto L_LoopNext;
    
L_LoopNext:
    set @loop, (@loop + 1);
    if (@loop > getarraysize(@torches))
        goto L_Return;
    goto L_Loop;

L_Complete:
    set @cassy_tmp, 1;
    callfunc "SetCassyState";
    message strcharinfo(0), "Completed all torches!";
    goto L_Return;

L_Return:
    return;
}

function|script|ToggleTorch
{
    callfunc "TorchCount";
    callfunc "GetCassyState";
    if (@cassy_state > 1)
        goto L_AllDone;
    if (CASSYSQUEST & (1 << @torch))
        goto L_UnSet;
    message strcharinfo(0), "Torch " + @torch + " Set";
    set CASSYSQUEST, (CASSYSQUEST | (1 << @torch));
    goto L_Return;

L_UnSet:
    message strcharinfo(0), "Torch " + @torch + " Unset";
    set CASSYSQUEST, (CASSYSQUEST &~ (1 << @torch));
    goto L_Return;

L_AllDone:
    message strcharinfo(0), "You have set all the torches!";
    goto L_Return;

L_Return:
    return;
}

[o11c]

IMO the user of db/const.txt or other constants makes bitshifts a *lot* harder to understand. So here's one with just constants.

Basically, stop thinking of integers as integers. Instead, and integer is a structure that contains 32 boolean fields, each of which can be set (to 0 or 1) independently. It is also possible to test or set any advacent sequence of them at once, but I'm not explaining that here.

so:

Code: Select all

struct CassyQuest:
    b0: bit = 0 # started quest at all?
    b1: bit = 0 # torch 1
    b2: bit = 0 # torch 2
    b3: bit = 0 # torch 3
    b4: bit = 0 # torch 4
    b5: bit = 0 # torch 5
    b6: bit = 0 # torch 6
    b7: bit = 0 # torch 7
    b8: bit = 0 # torch 8
    b9: bit = 0 # torch 9
    # b10 .. b31 not used so let's not write them all

Then write code like:

Code: Select all

on click torch1:
    if CassyQuest.b0: # started the quest
        CassyQuest.b1 = True

which is actually written like:

Code: Select all

on click torch1:
    if (CassyQuest & (1 << 0))
    {
        CassyQuest |= (1 << 1);
    }

(none of this code actually matches any real-world syntax, but the bitmasking part is right at least.)

[o11c]

To answer the second question (my previous post answers the first), there is a hard limit of 96 persistent variables and we currently use about 70 of them.