Russian Qt Forum

Добрый день

Нужно случайно расставить (или раскидать) N заданных объектов (напр 100 чайников) на поверхности другого заданного (хоть просто плоскость). Юзер имеет "кисточку" чтобы покрасить поверхность (плоскость), напр цвет в данной точке 100% - макс плотность, 0% - вообще здесь не ставить, 50% - ставить вдвое меньше. Плюс чекбокс "Skip Collided" - расставленные (чайники) не должны пересекаться.

Ну сделал прямолинейно: N раз выбираю место на поверхности, выбрасываю случайное число и сравниваю его с цветом (от 0 до 1), если число больше - чайник не ставлю. Потом проверяю на пересечения (с помощью движка физики). Пересекается - опять не ставлю.

Это работает, но появляется неприятный момент: число расставленных чайников оказывается намного меньше заданного. Т.е. чтобы получить 100 юзер должен заказать 1000, что не очень удобно. Как это обойти?

Спасибо

Да, и по ходу дела интересно получил по дюнделю

C++ (Qt)
// вектор индексов полигонов - случайно перемешан
void RandomIndex( std::vector<int> & vec )
{
  for (size_t i = 0; i < vec.size(); ++i)
   vec[i] = i;  
 
  for (size_t i = 0; i < vec.size(); ++i)
   std::swap(vec[qrand() % vec.size()], vec[qrand() % vec.size()])  
}
 

Оказывается это работает неверно, правильно random_shuffle, ну или исправить ошибку  :)
 

Ну самое очевидное - вместо цикла со счётчиком сделать цикл с постусловием. Т.е. подсчитывать число реально поставленных на плиту чайников, и выходить, когда 100 будет достигнуто.

Разумеется, при этом придётся ввести дополнительное условие, чтобы избежать зацикливания (мало ли что там не так с поверхностью, ГСЧ и физикой). Т.е. если количество итераций превышает некое предельно-разумное число - прерываемся и пишем (обязательно) сообщение об ошибке. Вот как это предельно-разумное число выбрать - вопрос отдельный. Я бы заказанное юзером число чайников умножил на 100 (всё равно в нормальных условиях цикл прервётся раньше) и посмотрел, работает ли это. И этот множитель (100) тоже можно сделать переменной и унести глубоко в настройки программы. В самом крайнем случае, если страшное случится у юзера вдали от программиста и исходников, можно будет предложить ему в эти настройки залезть и множитель увеличить.

Можно, наоборот, оставить цикл со счётчиком, только вместо i<N написать i<100*N, а в цикле завести дополнительный счётчик реально поставленных чайников и сравнивать его с N, по достижении N - делать break. Первый вариант более "физичен" (по виду соответствует задаче), второй более успокаивающе действует на читающего программу другого программиста, по логике они эквивалентны.

Ну добавить "супер-счетчик" - дело нехитрое, можно и в преференсы, можно и прямо в UI, не суть. Фактически юзер и сейчас это делает руками. Однако

1. Добавление объекта в движок физики - удовольствие дорогое (как и удаление его в случае пересечений). Поэтому множитель 100 - ну это вряд ли.

2. Просто "пробовать ставить больше" создает новые проблемы. Пусть напр левая сторона "плиты" (удачная аналогия) имеет маску 100%, а правая - только 50%. Если хорошо задрать счетчик, то обе части будут заставлены одинаково, т.е. впечатление что маска не работает. В самом деле - слева все время пересечения, а справа место найдется. И даже без всякой маски (плотность везде 100%) свободные места остаются, видно что "вот тут можно воткнуть" но random это место не выбирал

И это все надо как-то объяснять "простому человеку" который заказал 100, а получил всего 10, чтоо за фигня? Напрашивается опция типа "Auto", мол, "поставить сколько влезет" - но тогда как ставить?

В общем, нужны (плодотворные) идеи  :)

Igors, глубоко в суть задачи не влезал, но если дело в том, что нужно создать случайную последовательность неповторяющихся чисел, то тут есть некоторые разработки.
Если количество возможных значений равно или немного больше, то тут есть известный алгоритм https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%99%D0%B5%D1%82%D1%81%D0%B0
Если же возможных значений много больше, то тут тоже есть некоторые разработки. Кое-что опубликовано на другом форуме, но тут, кажется, как и повсюду, ссылки на чужие форумы запрещены.
Если дело действительно в этом, подумаем, как вам помочь.

Нет, дело не в этом, это давно решено (использовал random_shuffle), просто момент интересный.

Я (наивно) полагал что как-нибудь "взболтать" массив вполне достаточно. Мой первый вариант был

C++ (Qt)
 for (size_t i = 0; i < vec.size(); ++i)
   std::swap(vec[i], vec[qrand() % vec.size()])  
 

Ну а че? Ведь "перемешан" же! Да, но так получаемые паттерны получаются "похожими", т.е. юзер дал другой seed и ожидает другого расклада, а чайники "кучкуются" примерно в том же месте.

Насколько я понял (немного копнув), такое перемешивание "неравновероятно", т.е. у каких-то эл-тов шансов занять первые места больше. В этом можно убедиться просчитав на бумажке для 3 эл-тов. Насколько я понял, правильно так: если i-й эл-т обменян, то больше его не трогать. Собсно так и сказано в ссылке что Вы привели