Pages

Thursday, May 23, 2013

Using Probability in UDK-based Role-Playing Games - Part 1

Consider this a replacement for the probability class tutorial I shared a while ago.
This is a low to medium level tutorial that should cover the basics of probabilistic actions in UDK-based games with emphasis on the logic behind everything, some script snippets that should be ready to use, and some pseudo-code to explain usage. I will be demonstrating two methods, one that can have one of two outcomes (success/failure), and a slightly more advanced system with four outcomes (critical success/success/failure/critical failure).

Thanks to excellent feedback from members of the UDK forum, I went back over the functions from my earlier tutorial and tried to work out the most efficient ways to go about things.

Two common methods of generating a random number in UnrealScript are FRand(), which generates a random floating point number between 0.0 and 1.0, and Rand(int n), which generates a random number between 0 and n-1. There are up- and downsides to using either approach: FRand() can never (or almost never?) be 0 or 1, which simulates real probability but it comes with the additional slight cost of using floating point numbers. Rand() uses integers, which are a less accurate representation of probability if no additional calculations are added, but cheaper. I will be using FRand() for the examples in this tutorial.

There is also RandRange(float x, float y), which will output a floating point number between x and y. I won't be using this last one in this tutorial, but it will make an appearance in Parts 2 and 3.

NOTE: FRand() returns a decimal with 4 places, i. e. 0.0115, which can be simulated by generating a random integer between 0 and 10000 instead of 100 like in this example.


Examples of a 2-Way Decision (true/false)

Using float:

// fPercentage is the probability (as a floating point number between 0.0 and 1.0)
// that the function will return true cast as an int (0,1)
function bool ProbabilisticActionFloat(float fPercentage)
{
     return (fRand() < fPercentage);
}



Using int:

// iPercentage is the probability (as an integer representing percentage)
// that the function will return true cast as an int (0,1)
function bool ProbabilisticActionInt(int iPercentage)
{
     return (Rand(101) < iPercentage);
}



Using byte:


// iPercentage is the probability (as byte representing percentage)
// that the function will return true cast as a byte (0,1)
function bool ProbabilisticActionByte(byte iPercentage)
{
     return (Rand(101) < iPercentage);
}


NOTE: Byte and int number types can be used interchangeably as long as you cast the return value as the appropriate type.

These three functions have the same logic: A number is passed to the function, which them generates a random number and checks if if said number falls within the range of 0 to (input number), returning true if it does. This simulates probability since the chance of the random generator picking a number in this range equals the input number.

Function Usage (pseudo-code):
  
function SomeFunction()
{
     local float fChance; //chance of something happening

     fChance = fChanceOfEvent;
        //change to float number between 0.0000 and 1.0000

     if (ProbabilisticActionFloat(fChance)) {
          DoSomething();
     } else {
          DoSomethingElse();
     }
}


Critical Chance

These can also be nested to simulate Bayes' rule (don't worry, no math needed here), or multiple events having different chances of occurring depending on previous events. A good example of this is the use of critical success and failure events common in older role-playing games. Using the previous ProbabilisticActionFloat() function, a critical effect system could be implemented like this:

NOTE: this part is significantly different from the same functions in the previous version of the tutorial.

The inputs for the following functions are (in order) the chance of success, chance of critical success and chance of critical failure. I'm using a conditional operator (link) to evaluate and return the value because it turned out to be faster than both a regular conditional statement and adding/multiplying values together to come up with the output. The functions output an integer representing the selected outcome.

Examples of a 4-way Decision:

//Output:
// 0  - Failure, 1 – Success, 2 – Critical Success, 3 – Critical Failure

function int checkProbabilityFloat(float fSuccessRate, float fCritSRate, float fCritFRate)
{
     return ProbabilisticActionFloat(fSuccessRate) ? (1 + ProbabilisticActionFloat(fCritSRate)) : (ProbabilisticActionFloat(fCritFRate) * 3);
}

function int checkProbabilityInt(int iSuccessRate, int iCritSRate, int iCritFRate)
{
     return ProbabilisticActionInt(iSuccessRate) ? (1 + ProbabilisticActionInt(iCritSRate)) : (ProbabilisticActionInt(iCritFRate) * 3);
}



NOTE: The syntax for using the byte function is identical to the integer version, so I did not include it here.
 
Function Usage: (pseudo-code)

function SomeFunction()
{
 local int iProbVar;

 // 55 % success,
 // 3 % critical success,
 // 3 % critical failure
     iProbVar =  CheckProbability(0.55, 0.03, 0.03);

 // switch seems to be (very) slightly faster here than if-else
     switch (iProbVar) {
  case 0:
   DoFailureStuff();
   break;
  case 1:
   DoSuccessStuff();
   break;
  case 2:
   DoCritSuccessStuff();
   break;
  case 3:
   DoCritFailureStuff();
   break;
 }
}



Performance Analysis

There is a very slight performance difference between the different number types you could use for these functions because of the different ways in which the number types are stored in memory. Floating point numbers are the most accurate type available in UnrealScript, and take up the largest amount of memory, Integers are in the middle, and Bytes have the lowest memory use but with an upper limit of 255 they are also the least accurate (but perfect if you're going for percentages with no decimals or a number return value).

To test the execution speed of these functions, I used Clock/UnClock to time 1000 iterations of each function provided in this tutorial, then calculated the average time with 100 samples. The differences were minimal, but good to know about if you need to shave off some script time here and there. The largest performance difference I saw was between 32- and 64-bit mode.

NOTE: I'm timing 1000 runs of the functions because the functions executed too quickly for Clock() to give accurate results (lots of negative values).

ProbabilisticAction Results

In 32-bit mode, 1000 iterations of the ProbabilisticAction functions described above took between 0.1827 and 0.1934 ms to execute. There was an interesting result in my tests of these particular functions – the floating point function actually finished faster than the other two half of the time, but was the slowest, as expected, the other half of the time.

The same functions executed (comparatively) much faster in 64-bit mode, with times ranging from 0.1342 to 0.1457 ms. The floating point function actually performed best on average, followed by the integer function and the byte version.

CheckProbability Results

The checkProbability functions took between 0.4872 and 0.5082 ms to complete in 32-bit mode. The integer function was fastest most of the time by a small margin, followed by the float function, and the byte function was actually much slower than the others in this scenario.

In 64-bit mode, the functions took between 0.3264 and 0.3646 ms to execute. The floating point and integer versions of the function were fastest about the same number of times, and the byte version was again, much slower.

Based on my tests on this, it looks like using integers for this scenario is fastest in 32-bit, while floating point numbers are fastest in 64-bit. I find it interesting that bytes, despite having the smallest memory footprint, would be outperformed by floats and integers (Actually it's the reason I added this performance analysis).


Part 2, covering building a weighted loot list and using total probablity on a spreadsheet to debug said list should be done next week (hopefully).

No comments:

Post a Comment