rand () retorna os mesmos números novamente para um pequeno intervalo

Estou tentando fazer uma espécie de jogo em que tenho uma grade de 20x20 e mostro um jogador (P), um alvo (T) e três inimigos (X). Todos estes têm uma coordenada X e Y que são atribuídos usando rand(). O problema é que, se eu tentar obter mais pontos no jogo (recargas de energia, etc.), eles se sobrepõem a um ou mais dos outros pontos porque o alcance é pequeno (de 1 a 20, inclusive).

Estas são minhas variáveis ​​e como estou atribuindo valores a elas: ( COORDé um structcom apenas um X e um Y)

const int gridSize = 20;
COORD player;
COORD target;
COORD enemy1;
COORD enemy2;
COORD enemy3;

//generate player
srand ( time ( NULL ) );
spawn(&player);
//generate target
spawn(&target);
//generate enemies
spawn(&enemy1);
spawn(&enemy2);
spawn(&enemy3);

void spawn(COORD *point)
{
    //allot X and Y coordinate to a point
    point->X = randNum();
    point->Y = randNum();
}

int randNum()
{
    //generate a random number between 1 and gridSize
    return (rand() % gridSize) + 1;
}

Quero adicionar mais coisas ao jogo, mas a probabilidade de sobreposição aumenta quando faço isso. Existe alguma maneira de corrigir isso?

Enquanto os usuários que reclamam rand()e recomendam melhores RNGs estão certos sobre a qualidade dos números aleatórios, eles também estão perdendo o quadro geral. Duplicatas em fluxos de números aleatórios não podem ser evitadas, elas são um fato da vida. Esta é a lição do problema do aniversário .

Em uma grade de 20 * 20 = 400 posições possíveis de spawn, é esperado um ponto duplicado de spawn (probabilidade de 50%), mesmo ao gerar apenas 24 entidades. Com 50 entidades (ainda apenas 12,5% de toda a grade), a probabilidade de uma duplicata é superior a 95%. Você tem que lidar com colisões.

Às vezes, você pode desenhar todas as amostras de uma só vez e usar um algoritmo de reprodução aleatória para desenhar nitens distintos garantidos. Você só precisa gerar a lista de todas as possibilidades. Se a lista completa de possibilidades for muito grande para armazenar, você poderá gerar posições de reprodução uma de cada vez, como faz agora (apenas com um RNG melhor) e simplesmente gerar novamente quando ocorrer uma colisão. Embora seja provável haver algumas colisões, muitas colisões consecutivas são exponencialmente improváveis, mesmo que a maior parte da grade seja preenchida.

Se você sempre deseja evitar reproduzir uma nova entidade em um local que já foi alocado para outra coisa, você pode mudar um pouco o processo. Isso garantiria locais únicos, mas requer um pouco mais de sobrecarga. Aqui estão os passos:

1. Configure uma coleção de referências para todos os locais possíveis no mapa (para o mapa de 20x20, seriam 400 locais)
2. Escolha um local aleatoriamente nesta coleção de 400 (rand () funcionaria bem para isso)
3. Remova essa possibilidade da coleção de locais possíveis (agora ela possui 399 possibilidades)
4. Repita até que todas as entidades tenham um local especificado

Desde que você esteja removendo o local do conjunto do qual está escolhendo, não haverá chance de uma segunda entidade receber o mesmo local (a menos que esteja escolhendo os locais em mais de um segmento de uma vez).

Um análogo do mundo real a isso seria tirar uma carta de um baralho de cartas. Atualmente, você está embaralhando o baralho, comprando uma carta e marcando-a, colocando a carta comprada de volta no baralho, re-embaralhando e comprando novamente. A abordagem acima pula a colocação do cartão de volta no baralho.

Pertencente a rand() % nser inferior ao ideal

Doing rand() % ntem uma distribuição não uniforme. Você receberá um número desproporcional de certos valores porque o número de valores não é múltiplo de 20

Em seguida, rand()normalmente é um gerador congruencial linear (existem muitos outros , apenas esse é o mais provável implementado - e com parâmetros abaixo do ideal (existem várias maneiras de selecionar os parâmetros)). O maior problema com isso é que geralmente os bits baixos (os que você obtém com uma % 20expressão de tipo) não são tão aleatórios. Lembro-me de um rand()de anos atrás, onde o bit mais baixo alternava de 1para 0cada chamada para rand()- não era muito aleatório.

Na página do manual rand (3):

As versões de rand () e srand () na Linux C Library usam o mesmo
gerador de números aleatórios como random () e srandom (), portanto, a ordem inferior
bits devem ser tão aleatórios quanto os bits de ordem superior. No entanto, em
implementações rand () e nas implementações atuais em diferentes
sistemas, os bits de ordem inferior são muito menos aleatórios do que os
encomendar bits. Não use esta função em aplicativos destinados a
portátil quando boa aleatoriedade é necessária.

Agora isso pode ser relegado à história, mas é bem possível que você ainda tenha uma implementação ruim do rand () oculta em algum lugar da pilha. Nesse caso, ainda é bastante aplicável.

A coisa a fazer é realmente usar uma boa biblioteca de números aleatórios (que fornece bons números aleatórios) e depois pedir números aleatórios dentro do intervalo desejado.

Um exemplo de um bom número de código aleatório (a partir das 13:00 no vídeo vinculado)

#include <iostream>
#include <random>
int main() {
    std::mt19937 mt(1729); // yes, this is a fixed seed
    std::uniform_int_distribution<int> dist(0, 99);
    for (int i = 0; i < 10000; i++) {
        std::cout << dist(mt) << " ";
    }
    std::cout << std::endl;
}

Compare isso com:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    srand(time(NULL));
    for (int i = 0; i < 10000; i++) {
        printf("%d ", rand() % 100);
    }
    printf("\n");
}

Execute esses dois programas e compare com que frequência determinados números aparecem (ou não aparecem) nessa saída.

Vídeo relacionado: rand () considerado prejudicial

Alguns aspectos históricos do rand () causando bugs no Nethack que você deve observar e considerar em suas próprias implementações:

• Problema do Nethack RNG

  Rand () é uma função muito fundamental para a geração de números aleatórios do Nethack. O modo como o Nethack o usa é incorreto ou pode-se argumentar que lrand48 () produz números pseudo-aleatórios ruins. (No entanto, lrand48 () é uma função de biblioteca que usa um método PRNG definido e qualquer programa que o utilize deve levar em consideração os pontos fracos desse método.)

  O problema é que o Nethack depende (às vezes exclusivamente como é o caso em rn (2)) nos bits mais baixos dos resultados de lrand48 (). Por esse motivo, o RNG em todo o jogo funciona mal. Isso é especialmente perceptível antes que as ações do usuário introduzam mais aleatoriedade, ou seja, na geração de personagens e na criação de primeiro nível.

Enquanto o anterior foi de 2003, ainda deve ser lembrado, pois pode não ser o caso de todos os sistemas que executam o jogo pretendido serem um sistema Linux atualizado com uma boa função rand ().

Se você está fazendo isso sozinho, pode testar o quão bom é o seu gerador de números aleatórios escrevendo algum código e testando a saída com ent .

Sobre as propriedades de números aleatórios

Existem outras interpretações de 'aleatório' que não são exatamente aleatórias. Em um fluxo aleatório de dados, é bem possível obter o mesmo número duas vezes. Se você jogar uma moeda (aleatória), é bem possível obter duas caras seguidas. Ou jogue um dado duas vezes e obtenha o mesmo número duas vezes seguidas. Ou girando uma roleta e obtendo o mesmo número duas vezes lá.

A distribuição de números

Ao reproduzir uma lista de músicas, as pessoas esperam que 'aleatório' signifique que a mesma música ou artista não será tocado pela segunda vez consecutiva. Jogar uma lista de reprodução The Beatles duas vezes seguidas é considerado 'não aleatório' (embora seja aleatório). A percepção de que para uma lista de reprodução de quatro músicas tocou um total de oito vezes:

1 3 2 4 1 2 4 3

é mais 'aleatório' do que:

1 3 3 2 1 4 4 2

Mais sobre isso para o 'embaralhar' de músicas: Como embaralhar as músicas?

Em valores repetidos

Se você não deseja repetir valores, há uma abordagem diferente que deve ser considerada. Gere todos os valores possíveis e embaralhe-os.

Se você está ligando rand()(ou qualquer outro gerador de números aleatórios), está ligando para substituição. Você sempre pode obter o mesmo número duas vezes. Uma opção é descartar os valores repetidamente até selecionar um que atenda aos seus requisitos. Vou salientar que isso tem um tempo de execução não-determinístico e é possível que você se encontre em uma situação em que há um loop infinito, a menos que comece a fazer um rastreio mais complexo.

Lista e Escolha

Outra opção é gerar uma lista de todos os possíveis estados válidos e, em seguida, selecionar um elemento aleatório nessa lista. Encontre todos os pontos vazios (que atendem a algumas regras) na sala e escolha um aleatório nessa lista. E depois faça isso repetidamente até terminar.

Aleatório

A outra abordagem é embaralhar como se fosse um baralho de cartas. Comece com todos os pontos vazios da sala e comece a atribuí-los, distribuindo os pontos vazios, um de cada vez, para cada regra / processo solicitando um ponto vazio. Você termina quando fica sem cartas ou as coisas param de pedir por elas.

A solução mais simples para esse problema foi citada nas respostas anteriores: é fazer uma lista de valores aleatórios ao lado de cada uma das suas 400 células e, em seguida, classificar essa lista aleatória. Sua lista de células será classificada como a lista aleatória e, dessa forma, será embaralhada.

Este método tem a vantagem de evitar totalmente a sobreposição de células selecionadas aleatoriamente.

A desvantagem é que você precisa calcular um valor aleatório em uma lista separada para cada uma de suas células. Então, você prefere não fazê-lo enquanto o jogo começa.

Aqui está um exemplo de como você pode fazer isso:

#include <algorithm>
#include <iostream>
#include <vector>

#define NUMBER_OF_SPAWNS 20
#define WIDTH 20
#define HEIGHT 20

typedef struct _COORD
{
  int x;
  int y;
  _COORD() : x(0), y(0) {}
  _COORD(int xp, int yp) : x(xp), y(yp) {}
} COORD;

typedef struct _spawnCOORD
{
  float rndValue;
  COORD*coord;
  _spawnCOORD() : rndValue(0.) {}
} spawnCOORD;

struct byRndValue {
  bool operator()(spawnCOORD const &a, spawnCOORD const &b) {
    return a.rndValue < b.rndValue;
  }
};

int main(int argc, char** argv)
{
  COORD map[WIDTH][HEIGHT];
  std::vector<spawnCOORD>       rndSpawns(WIDTH * HEIGHT);

  for (int x = 0; x < WIDTH; ++x)
    for (int y = 0; y < HEIGHT; ++y)
      {
        map[x][y].x = x;
        map[x][y].y = y;
        rndSpawns[x + y * WIDTH].coord = &(map[x][y]);
        rndSpawns[x + y * WIDTH].rndValue = rand();
      }

  std::sort(rndSpawns.begin(), rndSpawns.end(), byRndValue());

  for (int i = 0; i < NUMBER_OF_SPAWNS; ++i)
    std::cout << "Case selected for spawn : " << rndSpawns[i].coord->x << "x"
              << rndSpawns[i].coord->y << " (rnd=" << rndSpawns[i].rndValue << ")\n";
  return 0;
}

Resultado:

root@debian6:/home/eh/testa# ./exe 
Case selected for spawn : 11x15 (rnd=6.93951e+06)
Case selected for spawn : 14x1 (rnd=7.68493e+06)
Case selected for spawn : 8x12 (rnd=8.93699e+06)
Case selected for spawn : 18x13 (rnd=1.16148e+07)
Case selected for spawn : 1x0 (rnd=3.50052e+07)
Case selected for spawn : 2x17 (rnd=4.29992e+07)
Case selected for spawn : 9x14 (rnd=7.60658e+07)
Case selected for spawn : 3x11 (rnd=8.43539e+07)
Case selected for spawn : 12x7 (rnd=8.77554e+07)
Case selected for spawn : 19x0 (rnd=1.05576e+08)
Case selected for spawn : 19x14 (rnd=1.10613e+08)
Case selected for spawn : 8x2 (rnd=1.11538e+08)
Case selected for spawn : 7x2 (rnd=1.12806e+08)
Case selected for spawn : 19x15 (rnd=1.14724e+08)
Case selected for spawn : 8x9 (rnd=1.16088e+08)
Case selected for spawn : 2x19 (rnd=1.35497e+08)
Case selected for spawn : 2x16 (rnd=1.37807e+08)
Case selected for spawn : 2x8 (rnd=1.49798e+08)
Case selected for spawn : 7x16 (rnd=1.50123e+08)
Case selected for spawn : 8x11 (rnd=1.55325e+08)

Basta alterar NUMBER_OF_SPAWNS para obter células mais ou menos aleatórias, isso não altera o tempo de computação necessário para a tarefa.