Pages

Tuesday, July 30, 2013

Using Probability for RPGs in UnrealScript Part 2

Using Probability for RPGs in UnrealScript Part 2 -
Weighted Lists using Structs

This tutorial is intended for people that have already set up a weapon and inventory system (or know how to use the default system) and will not go into details on how to spawn your items/weapons because there are a lot of different ways to do so that may not be compatible or would make things more complicated to explain. Instead, I will focus on the details of creating a list of entries or a single entry from a larger list that has the percentage chance of each entry being picked. It's pretty basic stuff that may not be immediately apparent when starting out with UnrealScript.

Scenarios in which weighted lists are useful include loot list generation and random event generators such as weather systems. This tutorial covers using a struct to store the weighted list. Another way to do it that would be to use two arrays if nothing besides a reference and weight is needed. The reason I'm using a struct for this is that it can store other variables of different types used in item creation without the need to create another array for each variable. Arrays of structs can also be saved to config files, which allows for easy addition of new items.

At its most basic, all a weighted list needs is a reference to whatever you're trying to accomplish (item to spawn, weather to change to, etc.) and a weight (the chance of the reference being picked).

 
Basic weighted list example:

This code should work in any class, but I suggest having it somewhere central that can be accessed by any classes that need to be able to or spawning an instance of it whenever needed since you don't want a bunch of redundant structs in memory.

*NOTE: In my random loot implementation, I'm using a string called sItemName to hold a unique identifier string that my inventory manager class uses to figure out which item to spawn. If you aren't using a method like that, you could use the item's classname with type class instead.

//weighted list struct definition
struct WeightedListStruct
{
 var string sItemName;
 var float fItemWeight;
};
var array WeightedList;

// generates a dynamic array of strings with items from WeightedList
function array GenerateList_Basic()
{
 local int i;
 local array tempItemsList;

 for (i=0; i  // probability check for each item
  if (FRand() < WeightedList[i].fItemWeight) {
   tempItemsList.AddItem(WeightedList[i].sItemName);
   break; //break if item is picked
  }
 }

 return tempItemsList;
}

//The following can also go into a config file
DefaultProperties
{
 WeightedList(0)=(sItemName="Item1",fItemWeight=0.5)
 WeightedList(1)=(sItemName="Item2",fItemWeight=0.25)
 WeightedList(2)=(sItemName="Item3",fItemWeight=0.125)
 WeightedList(3)=(sItemName="Item4",fItemWeight=0.125)
}



This will create a weighted list with 4 items, with chances of being added to the output list ranging from 12.5% to 50%. Notice that the chances add up to 1, or 100%. This is because a normalized list is the mathematically accurate way to deal with an array of chances, allowing the use of total probability and any other probabilistic functions you may want to use on it for debugging. Normalizing the list isn't required if you don't plan on using any advanced probability math on it.

The GenerateList_Basic() function runs a probability check on each item in the weighted list, adding items if they pass, and returns the resulting list as a dynamic array.

*NOTE: If using this in multiplayer, you will need to move the contents of the resulting array into a static array if you want to be able to replicate the list to other clients (for example, when using it for a loot list that other players can see). The function could also easily be rewritten to return one item at a time to be added to said static array in the class that needs it.


Advanced weighted list example:

Here is an example that uses some more variables to tweak the conditions under which an item will be added to the list. New variables in this example are fDiminish (diminishing returns for each item added), bExcludeAfterAdd (an item with this variable set to true can be added once), fChanceModifier (adjusts chance based on parameters fed into main function), and fBasePercentage (the chance that anything at all will be added to the list). For good measure, I'll also throw two in that are specific to loot lists, iMinLevel and iMaxLevel, which can be used to add an item only if the instigating character is within a certain level range. (The same concept can also be used in a crafting list to limit what a character can craft based on skill level.)

The diminishing returns variable is something I stole from economics to make rare items spawn less frequently. Each time an item is added to the list, the chance of any item being added decreases by a small amount (1% in my typical case). So if you have, for example, an item with a 3% chance of being picked, it will not be possible to add after 3 items have been added to the list. A side-effect of this is that the probability of adding an item can be so low after several iterations that there are substantially less items in the list than without it.

The formatting/wrapping on this piece of code is strange due to screen size limitations. It should copy/paste into a text editor properly, though. I've resized the box as much as I feel comfortable without making things unreadable at lower resolutions.

struct WeightedListStruct
{
 var string sItemName;
 var float fItemWeight;
 //new vars:
 var bool bExcludeAfterAdd;
 var int iMinLevel;
 var int iMaxLevel;
};
var array WeightedList;

function array GenerateFinalList(float fBasePercentage, float fChanceModifier, float fDiminish, int iMaxNumItems, int iCharLvl)
{
 local int i, j;
 local array tempItemsList;
 local float fDimRet;
 local bool bAlreadyThere; // for item exclusion check

 //Diminishing returns:
 // for each item added to the list, the chance of another being added
 // decreases. this is useful for limiting the amount of rare items that
        //  will be in a loot list
 fDimRet = 0;

 //check if anything should be added to the list
 if (FRand() < fBasePercentage) {
  // limit number of items
  for (i=0; i   for (j=0; j    bAlreadyThere = false;
    // check if character is in acceptable level range
    if ((iCharLvl >= WeightedList[j].iMinLevel) && (iCharLvl <= WeightedList[j].iMaxLevel)) {
     // probability check for each item
     if (FRand() < (FMax((WeightedList[j].fItemWeight + fChanceModifier - fDimRet), 0))) {
      // exclude if the item can only be added once
      if (WeightedList[j].bExcludeAfterAdd) {
       if (tempItemsList.Find(WeightedList[j].sItemName) > -1)
        bAlreadyThere = true;
      }
      if (!bAlreadyThere) {
       //decrease overall chance
       fDimRet += fDiminish;
       tempItemsList.AddItem(WeightedList[j].sItemName);
       break;
      }
     }
    }
   }
  }
 }

 return tempItemsList;
}

DefaultProperties
{
 WeightedList(0)=(sItemName="Item1",fItemWeight=0.4,bExcludeAfterAdd=true,iMinLevel=0,iMaxLevel=100)
 WeightedList(1)=(sItemName="Item2",fItemWeight=0.25,bExcludeAfterAdd=false,iMinLevel=0,iMaxLevel=50)
 WeightedList(2)=(sItemName="Item3",fItemWeight=0.125,bExcludeAfterAdd=false,iMinLevel=25,iMaxLevel=75)
 WeightedList(3)=(sItemName="Item4",fItemWeight=0.125,bExcludeAfterAdd=true,iMinLevel=10,iMaxLevel=50)
 WeightedList(4)=(sItemName="Item5",fItemWeight=0.125,bExcludeAfterAdd=false,iMinLevel=50,iMaxLevel=75)
 WeightedList(5)=(sItemName="Item6",fItemWeight=0.1,bExcludeAfterAdd=false,iMinLevel=25,iMaxLevel=100)
}


Weather System Example:

Since the rest of this tutorial is more geared towards loot lists, here is an example of using this method to choose the next weather in a dynamic weather system. Like above, this code doesn't include implementation details for a weather system. This example has 4 new variables, fChanceClear, fChanceCloudy, fChanceRain, and fChanceStorm, all of which are floating point numbers and are different for each weather type. These variables should be normalized to be mathematically accurate, but it won't break the function if you don't. If you have some knowledge of probability, think of them as the equivalents of P(A | A), P(A | B), etc. Since my weather system uses an enum to store the names of the different weather types, I'll include the enum definition. Of course, you can also use a string or name to identify the different weathers. Besides the four float variables above, you can store any information you need for the different weather types in the struct, such as fog density, fog distance, rain amount, etc. The variables you have in the struct depends on how you plan to manage your weather changes.

//holds weather names
enum EWeatherType
{
 Weather_Clear,
 Weather_Cloudy,
 Weather_Rain,
 Weather_Storm
};

//struct definition
struct WeatherStruct
{
 var EWeatherType WeatherType;
 var float fChanceClear;
 var float fChanceCloudy;
 var float fChanceRain;
 var float fChanceStorm;
};
var array WeatherTypesList;

var EWeatherType CurrentWeather;

//picks a random weather based on chances set by current weather type
function PickNewWeather()
{
 local int i;
 local EWeatherType tempWeather;

 tempWeather = CurrentWeather;

 for (i=0; i  if (CurrentWeather == WeatherTypesList[i].WeatherType) {
   if (FRand() < WeatherTypesList[i].fChanceClear)
    tempWeather = 0;
   else if (FRand() < WeatherTypesList[i].fChanceCloudy)
    tempWeather = 1;
   else if (FRand() < WeatherTypesList[i].fChanceRain)
    tempWeather = 2;
   else if (FRand() < WeatherTypesList[i].fChanceStorm)
    tempWeather = 3;
  
   break;
  }
 }

 if (CurrentWeather != tempWeather)
  CurrentWeather = tempWeather;
}

DefaultProperties
{
 CurrentWeather=Weather_Clear
 WeatherTypesList(0)=(WeatherType=Weather_Clear,fChanceClear=0.4,fChanceCloudy=0.3,fChanceRain=0.2,fChanceStorm=0.1)
 WeatherTypesList(1)=(WeatherType=Weather_Cloudy,fChanceClear=0.2,fChanceCloudy=0.4,fChanceRain=0.3,fChanceStorm=0.1)
 WeatherTypesList(2)=(WeatherType=Weather_Rain,fChanceClear=0.1,fChanceCloudy=0.2,fChanceRain=0.4,fChanceStorm=0.3)
 WeatherTypesList(3)=(WeatherType=Weather_Storm,fChanceClear=0.1,fChanceCloudy=0.3,fChanceRain=0.4,fChanceStorm=0.2)
}

No comments:

Post a Comment