【UE4】各要素の重さを考慮してランダムに取得するアルゴリズム

#はじめに
ゲームを作っていると「敵のステータスが瀕死状態の時は「行動A」と「行動B」と「行動C」を以下の表のように動いてほしい」といったことが頻発します

||行動A | 行動B | 行動C |
|:-----------|------------:|------------:|:------------:|
|**確率**| 10%       | 50%        | 40%         |

しかも厄介なのが「一定条件下だと行動Cは抽選から外す」といった仕様が追加されたりしますよね
都度都度条件式を書いているとバグの元だし、要素数が変わっても同じコードで動くようにしたいです

#アルゴリズム解説
1. TPair<重み,抽選要素>の形をした配列を作成
2. 重み0を防ぐため調整
3. Totalの重みを算出
4. 0 ~ Totalの範囲で乱数を取得しそれをkeyWeightとする
5. 配列をforで回し、重みの値で順番にtotalから減算していく
6. total値がkeyWeightを下回ったらその要素をreturn
7. forの中でreturnしなかったら最後の要素をreturn


#実装
使いまわせるようにUtilityとして実装しました.

```c++
UCLASS()
class JOHNNYLIBRARY_API UJohnnyUtility : public UBlueprintFunctionLibrary
{
	GENERATED_BODY()
public:

	template<typename T>
	static void AdjustWeight(TArray<TPair<int, T>>& weightList)
	{
		for (TPair<int, T>& pair : weightList)
		{
			pair.Key++;
		}
	}

	template<typename T>
	static int GetTotalWeight(TArray<TPair<int, T>>& weightList)
	{
		int total = 0;
		for (TPair<int, T>& pair : weightList)
		{
			total += pair.Key;
		}
		return total;
	}

	template<typename T>
	static T CalcWeightRate(TArray<TPair<int, T>>& weightList,int totalWeight)
	{
		int total = totalWeight;
		T ret = T();
		int keyWeight = FMath::RandRange(0,totalWeight);
		for (TPair<int, T>& pair : weightList)
		{
			int weight = pair.Key;
			T value = pair.Value;
			total -= weight;
			if (total <= keyWeight)
				return value;
			ret = value;
		}
		return ret;
	}
};

```

###How to

```c++
	TArray<TPair<int, FName>> weightList;
	{
		TPair<int, FName> pair;
		pair.Key = 10;
		pair.Value = TEXT("Action A");
		weightList.Add(pair);
	}
	{
		TPair<int, FName> pair;
		pair.Key = 50;
		pair.Value = TEXT("Action B");
		weightList.Add(pair);
	}
	{
		TPair<int, FName> pair;
		pair.Key = 40;
		pair.Value = TEXT("Action C");
		weightList.Add(pair);
	}
	UJohnnyUtility::AdjustWeight(weightList);
	int totalWeitght = UJohnnyUtility::GetTotalWeight(weightList);
	FName hitName = UJohnnyUtility::CalcWeightRate(weightList, totalWeitght);
	GLog->Log("#####Weight Random");
	GLog->Log(hitName.ToString());

```


#動作確認
上記のコードを面倒なのでTickでぶん回してみました
以下ログです

```
#####Weight Random
Action B
#####Weight Random
Action C
#####Weight Random
Action B
#####Weight Random
Action C
#####Weight Random
Action C
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action C
#####Weight Random
Action C
#####Weight Random
Action B
#####Weight Random
Action C
#####Weight Random
Action C
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action A
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action C
#####Weight Random
Action C
#####Weight Random
Action A
#####Weight Random
Action A
#####Weight Random
Action C
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
#####Weight Random
Action B
```

計30回分のログをコピペしています。割合を見てみましょう

||Action A | Action B | Action C |
|:-----------|------------:|------------:|:------------:|
|**回数**| 3回       | 17回        | 10回         |

それぞれ、10％、50％、40％の期待値なのでかなり期待通りの結果が出ていることがわかります
仮にAction Cが抽選から外されたとしても分母が「10＋50＝60」となり
Action Aは10/60で約16.6%の確率となり、Action Bは50/60で約83.3％の確率となります
（まぁこれを赦すかどうかは仕様次第ですが）