Como gerar números aleatórios sem fazer novos objetos aleatórios?

5

Estou usando isso como parte de um jogo, mas não é realmente uma questão de desenvolvimento de jogos, então estou colocando isso em um Stack Exchange mais geral.

O objetivo é gerar saídas "aleatórias" para uma entrada de número inteiro fixo, mas (e este é o argumento decisivo) para gerar a saída aleatória mesma toda vez que o mesmo entrada aleatória é colocada.

A ideia aqui é que a função irá gerar o mundo da mesma maneira todas as vezes, então não precisamos armazenar nada; a função em si é o armazenamento. Infelizmente, a velocidade de acesso é um pouco lenta, porque a única maneira que posso encontrar para gerar números aleatórios é criar um novo objeto Random () com uma semente baseada na entrada, o que é surpreendentemente lento.

Existe uma maneira melhor? Não estou preocupado com a geração segura para criptografia; na verdade, vou escolher uma semente aleatória com antecedência e expô-la publicamente.

O código atual é assim:

private const int seed;

public MapCell GetMapCell(int x, int y)
{
    Random ran = new Random(seed + (x ^ y));
    return new MapCell(ran.NextInt(0, 4));
}

Onde o MapCell é um dos quatro tipos (na verdade, é mais complicado do que isso, mas não muito). O ponto é que isso poderia ser chamado para qualquer parâmetro, a qualquer momento, sem nenhuma ordem específica, mas ele precisa retornar a mesma resposta todas as vezes, se xey forem as mesmas todas as vezes. É por isso que não consigo consertar um determinado objeto aleatório e usá-lo repetidamente.

Eu também não quero armazenar nada, porque eu quero manter o uso da memória RAM muito baixo, mas permitir que o jogador passeie livremente até as bordas de Int.MaxValue

    
por Richard Rast 17.08.2012 / 18:39
fonte

4 respostas

3

O sinal está em boa pista, mas o algoritmo dele está errado. Não é muito aleatório. É realmente muito difícil criar aleatoriamente assim. Eu estava brincando com isso e tudo que eu tentei criou padrões óbvios quando impressos em 2D. No final, consegui criar um algoritmo que não cria padrões visíveis aos olhos. Procurei inspiração em algoritmos aleatórios existentes.

public static uint bitRotate(uint x)
{
    const int bits = 16;
    return (x << bits) | (x >> (32 - bits));
}

public static uint getXYNoise(int x, int y)
{
    UInt32 num = seed;
    for (uint i = 0; i < 16; i++)
    {
        num = num * 541 + (uint)x;
        num = bitRotate(num);
        num = num * 809 + (uint)y;
        num = bitRotate(num);
        num = num * 673 + (uint)i;
        num = bitRotate(num);
    }
    return num % 4;
}

Quando este algoritmo é usado para renderizar 4 tons de imagem cinza, ele cria isto:

Paracomparação,oalgoritmoRandomcriaestepadrão:

O algoritmo do Sign também possui padrões:

    
por 12.02.2014 / 23:33
fonte
3

Por que não apenas combinar os dois números e misturá-los? algo como

private const int seed;

public MapCell GetMapCell(int x, int y)
{
    int combined = seed + (x ^ y);
    return new MapCell(combined.GetHashCode() %5);
}

Você deseja simplesmente mapear cada coordenada X, Y para um MapCell.

    
por 17.08.2012 / 20:33
fonte
3

Em The Art of Computer programming, volume 2, há uma seção dedicada a números aleatórios. Você pode encontrar o que está procurando lá.

O Projeto Euler usa o seguinte gerador de números aleatórios do psuedo em alguns de seus problemas (252 e 375 são os que eu vi primeiro):

  S(0)   = 290797 
  S(n+1) = (S(n))^2 mod 50515093

Obviamente, isso não lhe dá uma caminhada até o maxint, mas oferece uma abordagem que só exige que você salve o último resultado. Se você está trabalhando com longs ao invés de ints, ele deixaria funcionar (pelo que vale, 2 ^ 32-5 = 0xFFFFFFFB = 4.294.967.291 é o maior primo de 32 bits).

Na conversa rand () considerado prejudicial , o apresentador passa por vários diferentes opções para fazer números aleatórios. Enquanto isso fala de C ++, ele fornece informações que podem ser usadas para encontrar um método correto em outros idiomas.

Em particular, para distribuições uniformes de números aleatórios bem conhecidas, o que você quer encontrar é mt19937 , que significa Mersenne twister com parâmetros muito particulares - é baseado em 2 19937 - 1. (~ 11m na palestra).

A chave com o twister Mersenne é que são números pseudo-aleatórios de alta qualidade. Se você pesquisar um pouco, você pode encontrar implementações dele em vários idiomas . A fonte C original

Especificamente, para C # você pode usar StaticRandom para obter números aleatórios de maneira segura, sem necessidade de instanciação de novos objetos ( código ). Uma modificação do código deve permitir que você passe uma semente.

    
por 17.08.2012 / 20:13
fonte
-1

Como comentado por Kyralessa, a classe Random deve ser criada e a sequência solicitada a partir da instância. Isso economiza o tempo de criação de uma nova instância de classe.

//fixed seed of 123
private Random ran = new Random(123);
public MapCell GetMapCell(int x, int y)
{
    //x and y should not be zero
    int r = ran.Next(0,x*y*4)%4;
    return new MapCell(r);
}
    
por 24.08.2016 / 22:35
fonte

Tags