Я пытаюсь сделать что-то вроде игры, в которой у меня есть сетка 20х20, и я показываю игрока (P), цель (T) и трех врагов (X). Все они имеют координаты X и Y, которые назначаются с помощью rand()
. Проблема в том, что если я пытаюсь получить больше очков в игре (пополнение для энергии и т. Д.), Они перекрываются с одним или несколькими другими точками, потому что диапазон небольшой (от 1 до 20 включительно).
Это мои переменные и то, как я присваиваю им значения: ( COORD
это struct
просто X и 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;
}
Я хочу добавить в игру больше вещей, но вероятность совпадения увеличивается, когда я это делаю. Есть ли способ это исправить?
rand()
это жалкий ГСЧ, и в любом случае с таким небольшим диапазоном, вам не нужно просто ожидать столкновений, они почти гарантированы.rand()
это паршивая ГСЧ, она, вероятно, подходит для одиночной игры, и качество ГСЧ здесь не проблема.rand()
похоже, неактуально. Криптография не задействована, и любой ГСЧ, скорее всего, вызовет коллизии на такой маленькой карте.Ответы:
Хотя пользователи, которые жалуются
rand()
и рекомендуют более качественные ГСЧ, правы в отношении качества случайных чисел, им также не хватает более широкой картины. Нельзя избежать дубликатов в потоках случайных чисел, это факт жизни. Это урок проблемы дня рождения .На сетке из 20 * 20 = 400 возможных позиций появления следует ожидать дублирующую точку появления (вероятность 50%), даже если порождает только 24 объекта. С 50 объектами (все еще только 12,5% всей сетки) вероятность дублирования превышает 95%. Вы должны иметь дело со столкновениями.
Иногда вы можете нарисовать все образцы одновременно, тогда вы можете использовать алгоритм перемешивания, чтобы нарисовать
n
гарантированно отличные элементы. Вам просто нужно сформировать список всех возможностей. Если полный список возможностей слишком велик для хранения, вы можете генерировать позиции возрождения по одной за раз, как вы это делаете сейчас (только с лучшим ГСЧ), и просто заново генерировать, когда происходит столкновение. Даже если некоторые столкновения вероятны, многие столкновения подряд экспоненциально маловероятны, даже если большая часть сетки заполнена.источник
Если вы всегда хотите избежать воспроизведения новой сущности в месте, которое уже было выделено для чего-то другого, вы можете немного изменить процесс. Это гарантирует уникальные местоположения, но требует немного больше накладных расходов. Вот шаги:
Пока вы удаляете местоположение из набора, из которого вы выбираете, у второго объекта не должно быть шансов получить такое же местоположение (если только вы не выбираете местоположения из более чем одного потока одновременно).
Реальным аналогом этого будет вытягивание карты из колоды карт. В настоящее время вы перетасовываете колоду, вытягиваете карту и размечаете ее, кладете вытянутую карту обратно в колоду, повторно перемешиваете и снова рисуете. Приведенный выше подход пропускает помещение карты обратно в колоду.
источник
Относительно того, чтобы
rand() % n
быть менее чем идеальнымВедение
rand() % n
имеет неравномерное распределение. Вы получите непропорциональное количество определенных значений, потому что число значений не кратно 20Затем,
rand()
как правило, это линейный конгруэнтный генератор (есть много других , только наиболее вероятно, что он реализован - и с параметрами, меньшими, чем идеальные (есть много способов выбора параметров)). Самая большая проблема в этом состоит в том, что часто младшие биты в нем (те, которые вы получаете с% 20
выражением типа) не настолько случайны. Я вспоминаю одинrand()
из прошлых лет, когда младший бит чередовался с1
на0
каждый вызовrand()
- это было не очень случайно.Из справочной страницы rand (3):
Теперь это можно отнести к истории, но вполне возможно, что у вас все еще есть плохая реализация rand (), скрывающаяся где-то в стеке. В этом случае его все еще вполне применимо.
Нужно просто использовать хорошую библиотеку случайных чисел (которая дает хорошие случайные числа), а затем запрашивать случайные числа в нужном диапазоне.
Пример хорошего кода случайного числа (с 13:00 в связанном видео)
Сравните это с:
Запустите обе эти программы и сравните, как часто определенные числа появляются (или не появляются) в этом выводе.
Видео по теме: rand () считается вредным
Некоторые исторические аспекты rand (), вызывающие ошибки в Nethack, которые следует наблюдать и учитывать в собственных реализациях:
Nethack RNG Проблема
Хотя вышесказанное относится к 2003 году, об этом следует помнить, поскольку, возможно, дело не в том, что все системы, на которых установлена ваша игра, будут современной системой Linux с хорошей функцией rand ().
Если вы просто делаете это для себя, вы можете проверить, насколько хорош ваш генератор случайных чисел, написав некоторый код и протестировав вывод с помощью ent .
О свойствах случайных чисел
Существуют и другие интерпретации «случайного», которые не совсем случайны. В случайном потоке данных вполне возможно получить одно и то же число дважды. Если вы подбросите монету (случайно), вполне возможно получить две головы подряд. Или бросьте кубик дважды и получите одно и то же число дважды подряд. Или вращая колесо рулетки и получая одно и то же число дважды там.
Распределение чисел
При воспроизведении списка песен люди ожидают, что «случайный» означает, что одна и та же песня или исполнитель не будут воспроизводиться второй раз подряд. Имея список воспроизведения играть The Beatles дважды подряд считается «не случайным» (хотя это является случайным). Восприятие, что для списка воспроизведения из четырех песен играли в общей сложности восемь раз:
является более «случайным», чем:
Подробнее об этом для «перемешивания» песен: как перемешать песни?
На повторных значениях
Если вы не хотите повторять значения, следует рассмотреть другой подход. Сгенерируйте все возможные значения и перемешайте их.
Если вы звоните
rand()
(или любой другой генератор случайных чисел), вы звоните с заменой. Вы всегда можете получить один и тот же номер дважды. Один из вариантов - отбрасывать значения снова и снова, пока вы не выберете то, что соответствует вашим требованиям. Я укажу, что это имеет недетерминированное время выполнения, и возможно, что вы окажетесь в ситуации, когда есть бесконечный цикл, если вы не начнете выполнять более сложную обратную трассировку.Список и выбор
Другой вариант - создать список всех возможных допустимых состояний и затем выбрать случайный элемент из этого списка. Найдите все пустые места (которые соответствуют некоторым правилам) в комнате, а затем выберите случайное место из этого списка. И затем делайте это снова и снова, пока не закончите.
шарканье
Другой подход - перетасовать, как если бы это была колода карт. Начните со всех пустых пятен в комнате, а затем начните назначать их, раздавая пустые пятна, по одному, каждому правилу / процессу, запрашивая пустое место. Вы закончили, когда у вас закончились карты или вещи перестали просить их.
источник
Next, rand() is typically a linear congruential generator
Это не так на многих платформах сейчас. Из справочной страницы raux (3) в linux: «Версии rand () и srand () в библиотеке Linux C используют тот же генератор случайных чисел, что и random (3) и srandom (3), поэтому биты младшего разряда должен быть случайным, как биты старшего разряда. " Кроме того, как отмечает @delnan, качество PRNG здесь не является реальной проблемой.RAND_MAX
32767 разница составляет 1638 возможных способов получения одних чисел против 1639 для других. Кажется, вряд ли будет иметь большое практическое значение для ОП.Простейшее решение этой проблемы было процитировано в предыдущих ответах: это составить список случайных значений рядом с каждой из ваших 400 ячеек, а затем отсортировать этот случайный список. Ваш список ячеек будет отсортирован как случайный список, и, таким образом, будет перемешан.
Этот метод имеет то преимущество, что полностью избегает перекрытия случайно выбранных ячеек.
Недостатком является то, что вы должны вычислить случайное значение в отдельном списке для каждой из ваших ячеек. Таким образом, вы не хотели бы делать это, пока игра началась.
Вот пример того, как вы можете это сделать:
Результат:
Просто измените NUMBER_OF_SPAWNS, чтобы получить больше или меньше случайных ячеек, это не изменит время вычисления, необходимое для задачи.
источник