79 réponses à ce sujet

[Kato -]

Hi all,

Does anyone know how to do that? For instance, passing 15 to a given function, it randomizes over the contained values (1,2,4 and 8) and returns the picked value.

Thanks in advance.

Kato 

[WhiZard]

Kato_Yang wrote...

Hi all,

Does anyone know how to do that? For instance, passing 15 to a given function, it randomizes over the contained values (1,2,4 and 8) and returns the picked value.

Thanks in advance.

Kato 

const int MAX_BITS = 32;

int RandomBit(int nInteger)
{
if(!nInteger) return FALSE;
int nRandom = Random(MAX_BITS) + 1;
int nBitValue = 1;
int nInt = 1;
while(nInt < nRandom)
  {
  nBitValue *= 2;
  nInt++;
  }
if(!(nInteger & nBitValue))
  return RandomBit(nInteger);
return(nInteger & nBitValue);
}

Modifié par WhiZard, 11 novembre 2011 - 05:11 .

[Kato -]

Tyvm WhiZard!

[Lightfoot8]

To return a number with a random bit set,within the first 4 bits, you could just use.

nRandomBit = 1<< Random( 4);

[WhiZard]

Lightfoot8 wrote...

To return a number with a random bit set,within the first 4 bits, you could just use.

nRandomBit = 1<< Random( 4);

That would replace my while loop, but what the OP wants is for a random bit that is flagged as TRUE in a number to be returned (e.g. 17 would only return 16 or 1).

EDIT attached is a code shortening per Lightfoot8's suggestion.


const int MAX_BITS = 32;

int RandomBit(int nInteger)
{
if(!nInteger) return FALSE;
int nBitValue = 1 << Random(MAX_BITS);
if(!(nInteger & nBitValue))
  return RandomBit(nInteger);
return(nInteger & nBitValue);
}

Modifié par WhiZard, 11 novembre 2011 - 03:35 .

[Kato -]

Very nice indeed. I'm studying the binary arithmetic and bitwise operators so this is instructive to me, thank you both.

Kato

[FunkySwerve]

Avoid using the 32nd bit. It freaks NWN out in some instances. For example, in this function:

void SetTaskCompleted(object oPC, int nTaskGiver, int nTaskNumber, int nCompleteNext = FALSE, int nVFX = VFX_IMP_KNOCK) {
    string sKey = "TasksCompleted_" + IntToString(((nTaskGiver-1)/7)+1);
    int nTaskOffset = ((nTaskGiver%7)*4);
    int nCompleted = GetLocalInt(oPC, sKey);
    int nTask = nCompleted >> nTaskOffset;
    int nNew, nMask, nCurrent = nTask & 0xF;

    if (nCompleteNext) {
        nNew = ((nCurrent+1)>15 ? 15 : nCurrent+1);
        nNew = nNew << nTaskOffset;
        nMask = 0xF << nTaskOffset;
        nCompleted &= ~nMask;
        nCompleted |= nNew;

    } else {

        nTaskNumber = ((nTaskNumber > 15) ? 15 : nTaskNumber);
        nNew = nTaskNumber << nTaskOffset;
        nMask = 0xF << nTaskOffset;
        nCompleted &= ~nMask;
        if (nTaskNumber >= 1)//if zero we just leave the bits masked out, resetting task chain
            nCompleted |= nNew;
    }

    if (nTaskNumber > 0)
        AssignCommand(GetModule(), DelayCommand(0.1, ApplyVisualToObject(nVFX, oPC)));
    else
        AssignCommand(GetModule(), DelayCommand(0.1, ApplyVisualToObject(VFX_IMP_REDUCE_ABILITY_SCORE, oPC)));

    SetLocalInt(oPC, sKey, nCompleted);
    SetPersistentInt(oPC, sKey, nCompleted);
}

'Task' completion data gets stored for 7 different taskgivers, who are assigned 4 bits each. Because their tasks are sequential, that allowed us to store up to 15 tasks for each of them (as opposed to 4 independant quest states, 1 per bit). Originally, however, it held 8 taskgivers, using the total 32 bits.Bioware's bitmath worked perfectly until the 32nd bit was set, when a player completed that taskgiver's 8th task. Then it bugged the entire setup.

Funky

[WhiZard]

Kato_Yang wrote...

Very nice indeed. I'm studying the binary arithmetic and bitwise operators so this is instructive to me, thank you both.

Kato

Looking again at the script there is one critical flaw.  For single bit numbers the average number of times the function will be called is 32.  The maximum times NWScript allows for such self-referencing is 125.  There is a 1.8% chance that single bit numbers would cause an overflow number of loopings.  There are two ways around this.  Either 1. decrease MAX_BITS to something like 16, or 2. store the usable bits as local Integers, and return a random local integer.

Below is a script demonstrating method 2.


int RandomBit(int nInteger)
{
if(!nInteger) return FALSE;// If there are no good bits none can be returned
int nBitValue = 1;
int nCount = 0;
while(nBitValue <= nInteger  && nBitValue != 0) // Stores all good bits in one loop
  {
  if(nBitValue & nInteger)
    {
   nCount++;
    SetLocalInt(OBJECT_SELF, "BIT" + IntToString(nCount), nBitValue);
   
    }
  nBitValue << 1;
  }
int nReturn = GetLocalInt(OBJECT_SELF, "BIT" + IntToString(Random(nCount) + 1)); //Get a random stored bit
while(nCount > 0)// Clean up
  {
  DeleteLocalInt(OBJECT_SELF, "BIT" + IntToString(nCount));
  nCount--;
  }
return nReturn;
}


EDIT: Fixed an off by one issue for nCount

Modifié par WhiZard, 11 novembre 2011 - 05:00 .

[Kato -]

Okay, certainly. Fortunately, avoiding the 32nd bit is not a problem in the systems I'm using. I did not know about the limit of 125 for recursive calls either, so you guys make my day, thanks again. 

Kato

Modifié par Kato_Yang, 11 novembre 2011 - 06:00 .

[Lightfoot8]

Kato_Yang wrote...

Very nice indeed. I'm studying the binary arithmetic and bitwise operators so this is instructive to me, thank you both.

Kato

ok here is a little more advanced form.  That is if you want to push your understanding.   If not ingnore it,  Also im typing it at work so please excuse any typos.  

int GetRandonBit( int aBitArray)
{
   int aArrayCopy = aBitArray;
   int nCount;
   
   While (aArrayCopy)
   {
      aArrayCopy = (aArrayCopy & - aArrayCopy) ^ aArrayCopy;
      nCount++;
   }
  
   int nRND = Random(nCount);
  
   while ( nCount--) aBitArray= (aBitArray& - aBitArray) ^ aBitArray;
  
   return  aBitArray & - aBitArray;
}

Ill try to comment it when I get home later.

Modifié par Lightfoot8, 11 novembre 2011 - 07:59 .

[WhiZard]

Lightfoot8 wrote...
ok here is a little more advanced form.  That is if you want to push your understanding.   If not ingnore it,  Also im typing it at work so please excuse any typos.  

int GetRandomBit( int aBitArray)
{
   int aArrayCopy = aBitArray;
   int nCount;
   
   While (aArrayCopy)
   {
      aArrayCopy = (aArrayCopy & - aArrayCopy) ^ aArrayCopy;  //Gets smallest bit and removes it
      nCount++; //Counts the bits
   }
  
   int nRND = Random(nCount);  //0 stays zero, otherwise randomly selects from 0 to one less than nCount
  
   while ( nCount--) aBitArray= (aBitArray& - aBitArray) ^ aBitArray; //removes all bits less than the one designated.
  
   return  aBitArray & - aBitArray;//Returns smallest remaining bit (the one designated), 0 returns 0.
}

Ill try to comment it when I get home later.

Impressive, even returns FALSE for the 0 case.  I've added comments for you, and renamed the function to GetRandomBit().

Modifié par WhiZard, 11 novembre 2011 - 08:47 .

[WhiZard]

WhiZard wrote...
while ( nCount--)

My eyes jumped over this flaw.  Should be while (nRND--) .

[Lightfoot8]

WhiZard wrote...

WhiZard wrote...
while ( nCount--)

My eyes jumped over this flaw.  Should be while (nRND--) .

Yep,   sure enough.   
Thank for the added comments.   Looks a lot better the what I would have written.   Since the nCount/ nRND is messed up any way, Might as well just get trime the extra var out and use  nCount for the random number.  

So here it is with Wiz's comments, bug fixes and spelling corrections. 

int GetRandomBit( int aBitArray)
{
   int aArrayCopy = aBitArray;
   int nCount;

   While (aArrayCopy)
   { 
      //Get smallest bit and removes it
      aArrayCopy = (aArrayCopy & - aArrayCopy) ^ aArrayCopy;

      //Count the bits
      nCount++;
   }

   //0 stays zero, otherwise randomly selects from 0 to one less than nCount
   nCount = Random(nCount);

   //remove all bits less than the one designated.
   while ( nCount--) aBitArray= (aBitArray& - aBitArray) ^ aBitArray;
 
  //Returns smallest remaining bit (the one designated), 0 returns 0.
   return  aBitArray & - aBitArray;
}   

 

Modifié par Lightfoot8, 12 novembre 2011 - 12:33 .

[Kato -]

That's some serious coding, Lightfoot, tyvm. I'll have to study this a bit...


Kato

[Lightfoot8]

Kato_Yang wrote...

That's some serious coding, Lightfoot, tyvm. I'll have to study this a bit...


Kato

The main concept comes from a post that The.Gray.Fox made.

Modifié par Lightfoot8, 12 novembre 2011 - 01:14 .

[Lord Sullivan]

I've been reading this and been wondering in what scenario this is needed that cannot be achieved otherwise? why use bit math exactly?

I'm both interested and curious.

[Lightfoot8]

Lord Sullivan wrote...

I've been reading this and been wondering in what scenario this is needed that cannot be achieved otherwise? why use bit math exactly?

I'm both interested and curious.

Lets say we have a PW that has 20 towns in it, With a PC who is a thief.   Our thief has made a bad reputation for himself in many of the towns.  And we want to keep track of what towns he has behaved in, and the towns that well, would love to see him come back for a permanent stay.    We could set up a var for each town for Wanted/Unwanted  state  of the PC, in that town.  Or we could just pack all 25 into a single integer. Since the integer has 32 bits we can store 32 (31 if you take funkys warrning about using the 32nd) independet TRUE/FALSE values in the one varaiable.    

That way when our thief goes to sleep out in the wilds and that random encounter occures,  you only have the one integer to check to figure out what Town the bounty hunters are carrying papers from.    


i.e. 

const int TOWN1 = 0x01; 
const int TOWN2= 0x02;  
const int TOWN3 = 0x04; 
const int TOWN4 = 0x08;
....

SetThiefWanted( object oThief; int nTown); 
{
   int nWanted = GetLocalInt(oThief, "Wanted");
   nWanted = nWanted & nTown; 
   GetLocalInt(oThief, "Wanted", nWanted);
}

 

void main()
{
   // The Thief Has been spotted stealing stuff from 10 houses in town 1. 
   oThief = GetExitingObject();
  SetThiefWanted (oThief, TOWN1);  
}


  Once it is time for random bounty time.  You only have to check the one number to see if he is wanted in any of the towns.   in fact the GetRandomBit function above will return 0 if none of the bits are set, So it is simple enough to just bug out and not spawn the encounter if he is not wanted.

[Kato -]

Lord Sullivan wrote...

I've been reading this and been wondering in what scenario this is needed that cannot be achieved otherwise? why use bit math exactly?

I'm both interested and curious.

Well the system is very useful when you need to store many values into a single one and access them separately or in any combination of them. For instance, my loot system reads a variable on dying creatures, and this variable holds all the categories(each represented by a bitwise value) over wich MySQL will randomize at loot creation, giving tremendous flexibility.

I also use the system for my random placeable spawner: The placeables(shrubs, stones, chests etc...) are randomly spawned on placed waypoints, but there are more waypoints than placeables, to avoid the latter from always appearing at the same location. So the spawner loops over the waypoints and for each one wich does not have a corresponding placeable(because they are destroyable), a part of its tag(the ID) holding a bitwise value is retrieved and added to an integer variable, the total. Then a random bit value is retrieved from the total, giving the ID of the waypoint where the placeable will be spawned(with a delay, of course). That last operation was giving me some troubles, hence the post.


Kato 

Modifié par Kato_Yang, 12 novembre 2011 - 02:54 .

[Lord Sullivan]

Lightfoot8 wrote...

Lets say we have a PW that has 20 towns in it, With a PC who is a thief.   Our thief has made a bad reputation for himself in many of the towns.  And we want to keep track of what towns he has behaved in, and the towns that well, would love to see him come back for a permanent stay.    We could set up a var for each town for Wanted/Unwanted  state  of the PC, in that town.  Or we could just pack all 25 into a single integer. Since the integer has 32 bits we can store 32 (31 if you take funkys warrning about using the 32nd) independet TRUE/FALSE values in the one varaiable.    

That way when our thief goes to sleep out in the wilds and that random encounter occures,  you only have the one integer to check to figure out what Town the bounty hunters are carrying papers from.    


i.e. 

const int TOWN1 = 0x01; 
const int TOWN2= 0x02;  
const int TOWN3 = 0x04; 
const int TOWN4 = 0x08;
....

SetThiefWanted( object oThief; int nTown); 
{
   int nWanted = GetLocalInt(oThief, "Wanted");
   nWanted = nWanted & nTown; 
   GetLocalInt(oThief, "Wanted", nWanted);
}

 

void main()
{
   // The Thief Has been spotted stealing stuff from 10 houses in town 1. 
   oThief = GetExitingObject();
  SetThiefWanted (oThief, TOWN1);  
}


  Once it is time for random bounty time.  You only have to check the one number to see if he is wanted in any of the towns.   in fact the GetRandomBit function above will return 0 if none of the bits are set, So it is simple enough to just bug out and not spawn the encounter if he is not wanted.

So let's see if I get this somewhat according to your example...

Would that mean that if the random number is

0000 0000 <-- Town1, No bounty
0000 0001 <-- Town1, with bounty
0000 0010 <-- Town 2, No Bounty
0000 0011 <-- Town2, with bounty
etc... ?

[WhiZard]

Lord Sullivan wrote...
So let's see if I get this somewhat according to your example...

Would that mean that if the random number is

0000 0000 <-- Town1, No bounty
0000 0001 <-- Town1, with bounty
0000 0010 <-- Town 2, No Bounty
0000 0011 <-- Town2, with bounty
etc... ?

Nope.

Let's say the number stored is 1110 1101
That would mean that Town's #1,3,4,6,7,8 could possibly send a bounty out because they are hostile.
When a party is sent out it we randomly decide which Town they came from and this is returned as a power of 2 (e.g. 0010 0000 would mean that this party came from Town #6)

[Lord Sullivan]

WhiZard wrote...

Lord Sullivan wrote...
So let's see if I get this somewhat according to your example...

Would that mean that if the random number is

0000 0000 <-- Town1, No bounty
0000 0001 <-- Town1, with bounty
0000 0010 <-- Town 2, No Bounty
0000 0011 <-- Town2, with bounty
etc... ?

Nope.

Let's say the number stored is 1110 1101
That would mean that Town's #1,3,4,6,7,8 could possibly send a bounty out because they are hostile.
When a party is sent out it we randomly decide which Town they came from and this is returned as a power of 2 (e.g. 0010 0000 would mean that this party came from Town #6)

Ah ok, position is the town, (0) or (1) means No Bounty or Bounty (Friendly) or (Hostile)

Yeah good idea. Never even crossed my mind.

[the.gray.fox]

I like these topics -- Food for the brain :-)

Since the OP has been properly helped already, I think he will not mind
if I go slightly off topic. This could interest him anyway.


--------------------------------------------------
Funky did good in warning against the flaws of the 32nd bit.
However, it is not completely unsafe to work with it.
But sure it is due care.

If you make certain that your integer is only treated as a
"repository" of bits, and you only Set and Query the bits _as bits_
(ie: like Lightfoot8 described in his "towns" example), then you
can rely on the 32nd bit safely.
In all other cases, it is wise to heed Funky warning and double-check
that all your bits are behaving. Better test 2 minutes now than debug
2 hours later -- Agree?

In regard to bits and operations with bits, I am aware of 3 specific
bugs. And more subtle ones may exist -- if anyone can list them
I will hear him gladly.


Bug 1) the float datatype
Sparing you the gory details of the floating point encoding / decoding
(you can read all about it if you google for IEEE 754 Single Precision Floating Point)
I tell you that in NWscript the Least Significant Bit in the float Mantissa is
"lost" in the act of encoding. And upon decoding it is always assumed to be 0,
which causes a small loss of precision in the final decoded value.
The Least Significant Bit (LSB) is bit 0, or the 1st bit, or the >> leftmost >> bit.
That is, the 1 in this pattern: 00000000 | 00000000 | 00000000 | 00000001
Said bit happens to be always 0 when you read from a float. And there is no
way to prevent the bug, other than not feeding to a float a value that makes use
of the LSB -- Which is not a practical solution.
Your best bet to dodge the problems caused by this is to not make use of
decimal values that want many digits of precision. The more digits you attempt
to retain, the heavier the precision loss sparked from that last 0 bit.
-
ODDLY enough, though, the NWscript float is correctly capable of storing and
retrieving any integer in the range -16777215 to +16777215 -- thus demonstrating
that the float bug strikes only when the Mantissa is employed to encode values
with a _decimal_ part whether it fits or not the 23 bits Mantissa storage.
-
Depending on the importance of your float values, it may be desirable to
pre-emptively convert them to an integer (multiplying by a proper power of 10)
so long it fits in the 23 bits range, and then assign them to the float variable.
I know it sounds extravagant -- well, extravagant solutions for extravagant bugs.
This will ensure that you retain (and can later retrieve) all your digits,
whatever the original value.



Bug 2) The >>> operator (part 1)
Consider the following code snippet:

int nInteger = -100;

int nZero = nInteger >>> 32;

nInteger set to -100 creates the following bit pattern:
11111111 | 11111111 | 11111111 | 10011100

Then the RightShift operator (>>>) is expected to clear all
the 32 bits by pushing them to the right, leaving in their
place only a streak of 0s, like this:
00000000 | 00000000 | 00000000 | 00000000

Here is the bug: the call to >>> 32 will produce no change.
nZero will be assigned the unmodified input pattern:
11111111 | 11111111 | 11111111 | 10011100
Which is wrong.

If you need to RightShift by 32 positions, you have to do so
in 2 moves, for an example: a >>> 31 followed by a >>> 1.
Any combo that sums up to 32 will work.
But avoid a >>> 16 followed by another >>> 16, because a
different bug can occur in that scenario (read below).


Bug 3) The >>> operator (part 2)
Consider the following code snippet:

int nInteger = 0xAAAA1111;

int nHiWord = nInteger >>> 16;

When RightShift-ing by 16 positions with the >>> operator,
and the 32nd bit is set... the >>> operator will behave just
like the >> operator.
That is, it will _drag_ the MSB and propagate it to its right.
Which is wrong.

In the above snippet, nHiWord should be assigned the value: 0x0000AAAA.
Instead it will be assigned the value: 0xFFFFAAAA, with the
phantom 0xFFFF0000 introduced by the MSB propagation.

To enforce the >>> behavior, in this specific case, there
is need of a [extra] masking operation to ensure that you
only retain the lower 16 bits.
Like this:

int nInteger = 0xAAAA1111;

int nHiWord = (nInteger >>> 16) & 0xFFFF;

Disclaimer:
(because the Strange does happen)
Should the code snippets I posted fail to reproduce the bugs,
I can provide the original (but way longer) source code that
will spark them sure-shot. Ask, no problem.


-fox

Modifié par the.gray.fox, 12 novembre 2011 - 03:35 .

[Kato -]

Great infos, Fox, ty. I'll watch out for those bugs...


Kato

[Lightfoot8]

@the.gray.fox
Interesting results, I wish I had more time to look at them right now.  

Here is a summery of what I have seen so far.

First there seems to be no roll operators in nwscript, that makes some of the results you are getting even mor interesting.  

the << operator does a shl machine code operation.   I see no possabile problems with this one. 

the >>> operator does a sar (Shift Arithmetic Right.).   This is a  instruction that i have just never looked at.  I will have to look at it more later. 

the >> operator I also dont have a good grip on at the monent.   It looks like it can do either a single sar instruction or   it  does a  neg (computs the 2's comp)   the a sar then another neg.   
right not I just dont have the time to look at it. 


Just to make sure we are reading from the same book.   Are you running the game on an X86 system?  

[WhiZard]

I did a quick testing to try to decipher
100 >> 3 returns 12 (...1100100 goes to ...001100)
100 >>> 3 returns 12 (same as above)
-100 >> 3 returns -12 (...0011100 goes to ...110010)
-100 >>> 3 returns -13 (...0011100 goes to ...110011)