O uso de conteúdo aleatório é uma prática comum em games. Seja para criar mapas, decidir atributos de personagens ou determinar o loot que o jogador irá ganhar. Em alguns casos, queremos criar algo completamente novo ou selecionar algo de uma lista. Em outros, queremos apenas mudar a ordem dos itens de uma lista, como é o caso, por exemplo, de embaralhar cartas.
E é aqui que entra o algoritmo de Fisher-Yates. Criado por Ronald Fisher e Frank Yates. O algoritmo foi aprimorado por Donald Knuth. Fisher-Yates é um algoritmo eficiente e garante que todas as possibilidades tenham a mesma chance de acontecer. Isso evita a formação de padrões que poderiam ser adivinhados, o que é essencial em jogos de cartas, por exemplo.
Neste tutorial, vamos aprender o como o algoritmo de Fisher-Yates funciona e vamos implementar uma versão dele usando C#. Por ser um apenas um algoritmo ele pode ser facilmente adaptado para outras linguagens. Vamos começar?
Como o algoritmo funciona
Basicamente, o algoritmo de Fisher-Yates é utilizado para embaralhar os itens de uma lista, tornando-a completamente aleatória. A principal vantagem desse algoritmo em relação a outros métodos é que ele garante uma sequência sem viés, isto é, todas as combinações possíveis da lista tem a mesma probabilidade de acontecer. Além disso, o algoritmo é simples e eficiente.
Para entendermos como o algoritmo de Fisher-Yates funciona, vamos imaginar que temos uma sequência qualquer, por exemplo as letras da palavra “Unity”.
Para embaralhar esta sequência, primeiro selecionamos o último elemento da sequência e, de forma aleatória, escolhemos outro elemento da sequência para trocar de lugar com ele.
Em seguida, selecionamos o próximo elemento da sequência e trocamos ele de lugar com outro elemento. Repetimos esse processo até que todos os elementos da sequência tenham trocado de lugar.
O algoritmo na prática
Agora que entendemos como o algoritmo funciona, vamos colocá-lo em prática. Para isso, vou criar um aplicativo para Console utilizando o Visual Studio 2022 e C#. No entanto, lembre-se de que o algoritmo é independente de ferramenta ou linguagem. E você pode implementá-lo utilizando a opção de sua preferência.
É fundamental lembrar que o algoritmo de Fisher-Yates não cria uma nova lista, já que ele opera diretamente na lista existente, modificando sua ordem. Se você precisar preservar a sequência original da lista, é recomendável fazer uma cópia antes de utilizar o algoritmo.
Criando um novo projeto no Visual Studio
Primeiramente, iremos abrir o Visual Studio. Na janela inicial, clique no botão “Create a new project”.
Na próxima tela, selecione o template “Console Application”. Clique no botão “Next”.
Em seguida, nomeie o projeto como “FisherYatesShuffle”, e escolha a pasta onde deseja salvá-lo. Clique no botão “Next”.
Por fim, selecione .NET 6.0 como o framework do projeto e deixe a opção “Do not use top-level statement” marcado. Clique no botão “Next” para criar o projeto.
Implementando o algoritmo de Fisher-Yates
Com o projeto criado, abra o arquivo “Program.cs” e crie um método chamado Shuffle. Neste primeiro exemplo o método receberá um array de strings, e mais tarde faremos melhorias.
static void Shuffle(string[] words)
No método Shuffle, a primeira coisa que precisamos fazer é criar uma instância da classe Random. Essa classe será utilizada para gerar números aleatórios e selecionar os diferentes elementos do array.
static void Shuffle(string[] words)
{
Random random = new Random();
}Aqui é preciso ficar atento e criar a instância da classe Random fora de loops. Isso é importante porque a classe utiliza a hora do sistema como seed do gerador. Como resultado, números gerados podem se repetir em diferentes iterações que ocorram em um curto período de tempo. Portanto, é recomendável criar a instância da classe Random apenas uma vez e utilizá-la ao longo do processo para garantir a obtenção de números verdadeiramente aleatórios.
Em seguida, criaremos um loop for que começa do último elemento do array e decrementa a contagem a cada iteração. Isto garante que todos os elementos tenham uma chance igual de serem selecionados para a troca.
static void Shuffle(string[] words)
{
Random random = new Random();
for (int i = words.Length - 1; i > 0; i--)
{
}
}O próximo passo é gerar o índice de um elemento do array utilizando o gerador de número aleatório. Na sequência, podemos guardar referências a ambos os elementos em variáveis temporárias. E por fim, trocamos os elementos de posição.
static void Shuffle(string[] words)
{
Random random = new Random();
for (int i = words.Length - 1; i > 0; i--)
{
int randomIndex = random.Next(i + 1);
string a = words[i];
string b = words[randomIndex];
words[i] = b;
words[randomIndex] = a;
}
}Depois disso, vá para o método Main. Aqui criaremos um array de strings e utilizaremos o método Shuffle para embaralhar os elementos. Por fim, utilizamos o método Console.WriteLine para escrever no console o resultado.
static void Main(string[] args)
{
string[] cities = { "Ubatuba", "Taubaté", "São José dos Campos" };
Shuffle(cities);
Console.WriteLine(string.Join(", ", cities));
Console.ReadLine();
}O código completo pode ser visto abaixo.
namespace FisherYatesShuffle
{
internal class Program
{
static void Main(string[] args)
{
string[] cities = { "Ubatuba", "Taubaté", "São José dos Campos" };
Shuffle(cities);
Console.WriteLine(string.Join(", ", cities));
Console.ReadLine();
}
static void Shuffle(string[] words)
{
Random random = new Random();
for (int i = words.Length - 1; i > 0; i--)
{
int randomIndex = random.Next(i + 1);
string a = words[i];
string b = words[randomIndex];
words[i] = b;
words[randomIndex] = a;
}
}
}
}Aqui estão alguns exemplos dos resultados gerados.
- Taubaté, Ubatuba, São José dos Campos
- Ubatuba, Taubaté, São José dos Campos
- São José dos Campos, Taubaté, Ubatuba
Turbinando o método Shuffle
Como você pode imaginar o método Shuffle está bem limitado no momento, uma vez que, basicamente, só pode embaralhar listas de palavras. Porém utilizando algumas funcionalidades que C# nos fornece, como métodos genéricos, métodos de extensão e interfaces podemos turbinar o método. Não entrarei em detalhes sobre essas funcionalidades mas a Microsoft oferece documentação completa caso você queira saber mais.
Antes de mais nada, vamos criar um novo arquivo e nomeá-lo como “IListExtensions.cs”. Neste arquivo vamos criar uma classe estática com o mesmo nome, isso fará duas coisas para a gente, a primeira é que só poderemos criar métodos estáticos nessa classe, o segundo, e mais interessante, é que poderemos acessar essa classe e seus métodos públicos de qualquer classe sem a necessidade de criar uma instância dela.
namespace FisherYatesShuffle
{
internal static class IListExtensions
{
}
}
Agora iremos copiar o método Shuffle do arquivo “Program.cs” para este novo arquivo, não se esqueça de marcar o método como estático e torná-lo público.
No momento o método recebe um array de strings como parâmetro, o que o torna limitado porque caso quiséssemos embaralhar um tipo diferente de array, teríamos que criar um método novo. Para resolver esse problema, podemos utilizar métodos genéricos. Essa funcionalidade do C# nos permite definir um método em que o tipo do parâmetro será inferido durante a execução do programa.
public static void Shuffle<T>(T[] words)
{
Random random = new Random();
for (int i = words.Length - 1; i > 0; i--)
{
int randomIndex = random.Next(i + 1);
T a = words[i];
T b = words[randomIndex];
words[i] = b;
words[randomIndex] = a;
}
}Com essa mudança o método agora pode receber qualquer tipo de array. Mas podemos fazer mais, ao invés de usar um array, podemos usar a interface IList. Dessa forma, podemos passar como argumento ao método qualquer classe que implementa essa interface, o que inclui o próprio array e a classe List, por exemplo.
public static void Shuffle<T>(IList<T> words)
{
Random random = new Random();
for (int i = words.Count - 1; i > 0; i--)
{
int randomIndex = random.Next(i + 1);
T a = words[i];
T b = words[randomIndex];
words[i] = b;
words[randomIndex] = a;
}
}Por último podemos usar a palavra-chave this antes do parâmetro do método. Com isso, criamos um método de extensão. Na prática isso nos permite utilizar esse método como um método da própria classe. Em outras palavras, métodos de extensão nos permite adicionar métodos a uma classe que normalmente não poderíamos modificar. A versão final da classe IListExtensions ficará assim.
namespace FisherYatesShuffle
{
internal static class IListExtensions
{
public static void Shuffle<T>(this IList<T> list)
{
Random random = new Random();
for (int i = list.Count - 1; i > 0; i--)
{
int randomIndex = random.Next(i + 1);
T a = list[i];
T b = list[randomIndex];
list[i] = b;
list[randomIndex] = a;
}
}
}
}O resultado é que ao invés de usarmos IListExtensions.Shuffle(listToShuffle) podemos usar simplesmente listToShuffle.Shuffle(). Como podemos ver no “Program.cs”.
namespace FisherYatesShuffle
{
internal class Program
{
static void Main(string[] args)
{
string[] cities = { "Ubatuba", "Taubaté", "São José dos Campos" };
cities.Shuffle();
Console.WriteLine(string.Join(", ", cities));
Console.ReadLine();
}
}
}Conclusão
Como dito antes, o algoritmo Fisher-Yates é simplesmente um algoritmo, o que significa que não requer nenhuma etapa especial para ser usado na Unity ou em outras engines. Sendo necessário apenas adaptá-lo para a linguagem de sua preferência.
Em relação a Unity especificamente, ou em outras engines que utilizem C#, sequer são necessárias adaptações. Devido ao poder dos métodos genéricos e interfaces, podemos utilizar o método para embaralhar a lista de tipos específicos da engine de sua escolha.
Outro ponto importante é que a classe Random tem um limite para a quantidade de números que pode gerar, o que pode resultar em algumas sequências não aparecendo ao embaralhar a lista. No entanto, podemos encontrar uma solução para esse problema ao ler o final deste artigo, que também aborda essa questão. Porém, ao criar jogos apenas para entretenimento, não acredito que esse seja um problema relevante.
