확률 기반 아이템 뽑기 알고리즘

목차

    소개글

    확률 기반 아이템 뽑기 알고리즘

    내용 정리

 

소개글

확률에 기반하여 아이템을 뽑는 알고리즘에 관하여 이 글을 통해 알려드리고 싶습니다.

실제로 작동을 시켜보면 사전에 맞추어둔 확률에 매우 근사한 결과값을 얻으실 수 있으실거예요.

우선 이 알고리즘에 관한 내용은 예전에 어떤 글에서 읽었었는데 지금 찾으려니까 못찾겠네요..

그때 당시에 저가 읽은바로는 그냥 의사코드도 없이 딱 이렇게저렇게 하면 된다,

이런식으로 이론만 설명이 되있긴했지만 이번에 제 주 언어인 C++로 변환한뒤 최적화까지 해놨으니 게임개발하시는분들은 참고하시면 좋겠습니다.

 

 

확률 기반 아이템 뽑기 알고리즘

위와 같이 한 아이템 뽑기상자에 일정한 확률을 가지는 여러종류의 아이템이 들어있습니다.

그러면 이 확률에 최대한 근사하여 아이템을 뽑는 방법은 어떻게 될까요?

 

사실 여기서 살짝의 관점을 변환하면 해답을 알수있습니다.

확률을 퍼센트대신 "가중치"로 보겠습니다.

 

우선 여기서 Epic의 가중치는 30이며, Legendary의 가중치는 10, Normal의 가중치는 60입니다.

모든 아이템의 가중치합은 100이며, 이제 0부터 가중치합인 100까지의 수를 랜덤으로 뽑겠습니다.

그러면 [0, 모든 아이템의 가중치합] 범위를 가지는 임의의 수를 얻을 수 있습니다.

 

마지막으로 아이템박스의 모든아이템(Epic, Legendary, Normal)을 순회하면서 초기값이 0인 임의의 변수에다가 이 가중치들을 더해가면서 만약 현재 임의의 변수값이 아까 위에서 뽑은 랜덤수보다 같거나 커지면 그때의 아이템을 반환합니다.

이 부분의 의사코드입니다.

real randomValue = Random(0.0, WeightSum)
real accumulator = 0.0;

for each (item in itemBox)
{
	accumulator += item.weight;

	if(randomValue <= accumulator)
		return item.item;
}

 

여기서 accumulator라는 변수에다가 값을 축적하면서 랜덤값보다 큰거나 같은값인지 확인하는 이유는 우리가 뽑은값이 현재 가중치에 해당하는 범위안에 존재하는지 알기위해서입니다.

위 그림처럼 특정 가중치를 가진 아이템은 그 가중치만큼의 확률공간을 가지게 되는것입니다.

예를들어서 랜덤값이 "45"가 나오게된다면 45라는 수는 Normal블럭의 크기보다 작으므로 위 코드블럭

if(randomValue <= accumulator)

해당 부분에 의해 최종적으로 Normal을 반환할 것입니다.

반대로 90~100사이의 수가 나온다면 위 조건에 의해 축적되면서 Legendary가 반환될것입니다.

 

만약 여러분이 좀 더 랜덤한 느낌을 더 주고싶다면 여기서 아이템박스의 아이템들을 랜덤으로 정렬시켜도 됩니다.

 

내용 정리

알고리즘의 작동순서입니다.

1. 아이템박스의 모든 아이템의 가중치합을 구한다.

2. [0, 가중치합] 사이의 값을 랜덤으로 뽑는다.

3. 아이템박스의 내용을 순회하면서 만약 현재까지 아이템의 가중치 축적값이 랜덤으로 뽑은 값보다 크거나 같으면 그때의 아이템을 반환한다.

 

마지막으로 C++코드로 변환한뒤 마치겠습니다.

#include <vector>
#include <utility>
#include <string>
#include <random>
#include <ctime>

template <typename T>
inline T RandomMt19937(T min, T max)
{
    static std::default_random_engine rd{static_cast<long unsigned int>(std::time(0))};
    static std::mt19937 mt(rd());
    static std::uniform_real_distribution<> dist(min, max);
 
    return dist(mt);
}

std::string WeightedRandom(const std::vector<std::pair<std::string, double>>& items_old)
{
	double totalWeights = 0.0;
	std::vector<std::pair<std::string, double>> item = items_old;
	
	for(auto& i : item)
		totalWeights += i.second;
		
	double rdValue = RandomMt19937<double>(0.0, totalWeights);
	double accumulator = 0.0;
	
	for(auto& i : item)
	{
		accumulator += i.second;
		
		if(rdValue <= accumulator)
			return i.first;
	}
	
	return "";
}