Сейчас 13:43:37 Понедельник, 8 августа, 2022 год
[ x ] Главная ⇒ Форум ⇐ RSS Файлы Cтатьи Картинки В о й т и   или   з а р е г и с т р и р о в а т ь с я


[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: PUVer, SirNikolas, Ty3uK  
Форум о Warcraft 3 » Раздел для картостроителей » Вопросы по картостроению » Рандомизация числа без цикла перегенерации
Рандомизация числа без цикла перегенерации
DuosoraДата: Вторник, 03 Марта 2015, 00:19:46 | Сообщение # 1
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Здравствуйте. Я к вам с довольно интересным вопросом из области псевдослучайных чисел.
Существует некоторая прямоугольная область типа rect. Условно назовём её R. В ней находится другая прямоугольная область типа rect, условно названная S, имеющая центральную точку, которая совпадает с центральной точкой области R, но область S своими размерами намного меньше области R. От области S есть равноудалённые от неё области типа rect, условно названные T, U, V и W, одного и того же размера (см. рисунок ниже).



Требуется, не используя циклов, сгенерировать случайную точку в области R, которая бы не находилась ни в области S, ни в области Т, ни в области U, ни в области V, ни в области W.
Как это возможно сделать? Заранее благодарен плюсами в репутацию за любую попытку ответа либо полноценный ответ.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.


Сообщение отредактировал Duosora - Вторник, 03 Марта 2015, 00:20:50
 

SreziДата: Вторник, 03 Марта 2015, 00:34:01 | Сообщение # 2
7 уровень
Группа: Проверенные
Сообщений: 414
Награды: 0
Репутация: 116
Блокировки:
без циклов о_О ну... проверять не относится ли твоя точка к ректам. Вернее создавать случайную точку и условием проверять По информатике такое изучали)
Либо добавлять области ректа в условие.
Например

set x=GetRandomReal(minXкарты,maxXкарты)
if x в промежутке одного из rect(S,T,U,V,W), то
set x=GetRandomReal(maxX(ректа в который точка попала),maxX(карты))

И так далее...

Без циклов делать данную вещь как то необычно скучно и...


Нет места чести на войне,
Враг церемониться не будет,
Убей его любым путём,
Ведь победителей не судят.
 

DuosoraДата: Вторник, 03 Марта 2015, 00:57:24 | Сообщение # 3
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Всё дело в том, что количество витков такого цикла так же рандомно, как и само число. А цикл-то может затянуться.
Такими ифами тут не отделаешься - это развёртка цикла.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

SreziДата: Вторник, 03 Марта 2015, 01:46:47 | Сообщение # 4
7 уровень
Группа: Проверенные
Сообщений: 414
Награды: 0
Репутация: 116
Блокировки:
Используй математику. Находи по обеим координатам координаты внутри Областей и вырезай. If и endif там обязательно будут.

Нет места чести на войне,
Враг церемониться не будет,
Убей его любым путём,
Ведь победителей не судят.
 

sumertДата: Вторник, 03 Марта 2015, 04:10:35 | Сообщение # 5
10 уровень
Группа: Проверенные
Сообщений: 2330
Награды: 2
Репутация: 1094
Блокировки:
Если без циклов, то надо создавать новые области, которые не лежат в (S,T,U,V,W) и выбирать случайную точку там.
 

ExtrematorДата: Вторник, 03 Марта 2015, 12:50:58 | Сообщение # 6
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки:
задаёшь точке случаные координаты внутри области
а потом если эту точка попала в одну из ненужных областей - перемещаешь её в другое место, за края области

если например размер малых областей хотя бы 500 по строне
то можно в таком случаи сдвигать точку на ~500 центра этой области, в рандомном направлении
типа выбор выпал в ней, но был выдвинут из неё...

Ну и с большой так же
Можно циклом все 5 областей чекать

. . .

А вообще наверняка там координатами расчёт идёт
Поэтому можно просто задать X случайно от minX до maxX области
а далее уже выдать случайный Y, но уже от minY и до maxY, при этом не более чем некоторые пересекающиеся значения

. . .

Либо вариант очень простой, но топорный
Создать во всех остальных местах новые области, которые покроют общую область, будет как пазл с забаненными деталями
И при выборе случайно выбирать точку на одной из случайно выбранных областей (не забаненных).

Добавлено (03 Марта 2015, 12:50:58)
---------------------------------------------
Хотя не думаю что то что описал топик-стартер для него вообще является вопросом.
Скорее всего он пилит что-то более сложное, и более грузящее...
И для простоты объяснения выбрал вот такой интерпретацию.
У него может таких областей штук 50 будет, и они в добавок будут ещё динамическими х))

 

Gr0mДата: Вторник, 03 Марта 2015, 13:20:13 | Сообщение # 7
8 уровень
Группа: Проверенные
Сообщений: 729
Награды: 0
Репутация: 249
Блокировки:
Интересна я тема! создавать точку случайно каждый раз игнорируя ненужные нам области, она может создаваться в другой такой же области довольно много раз и будет это повторяться, можно проверить если точка входит в координаты (STUVW) области дать ей новую координату где-то с краю области в которую вошла точка.
Примитивный метод
 

DuosoraДата: Вторник, 03 Марта 2015, 14:27:27 | Сообщение # 8
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Gr0m,
Это вновь предложение цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле. Это говорит уже само понятие "каждый раз". Но за попытку благодарочка плюсом)

Extremator,
Цитата Extremator ()
А вообще наверняка там координатами расчёт идёт
Поэтому можно просто задать X случайно от minX до maxX области
а далее уже выдать случайный Y, но уже от minY и до maxY, при этом не более чем некоторые пересекающиеся значения

Ты пришёл практически к тому же решению, какое подумывал использовать я, но, если областей вдруг станет больше, то вариант внезапно станет куда затратнее. =)
Цитата Extremator ()
Либо вариант очень простой, но топорный
Создать во всех остальных местах новые области, которые покроют общую область, будет как пазл с забаненными деталями
И при выборе случайно выбирать точку на одной из случайно выбранных областей (не забаненных).

Что-то мне кажется, что такой вариант сожрёт гораздо больше, да ещё и потребует дополнительную память для его реализации (в памяти как rect, так и ссылку на него надо где-то хранить). Действительно, топор.
Цитата Extremator ()
Скорее всего он пилит что-то более сложное, и более грузящее...

Немного открою карты - пилю достаточно навороченный боссфайт. =)


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

ExtrematorДата: Вторник, 03 Марта 2015, 14:51:58 | Сообщение # 9
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки:
Ну тогда наверняка всё же будет проще при попадании точки в ненужную область - просто выталкивать точку за край области, вот и всё

Будет например 12 областей таких по кругу, и в центре 13я
Задашь точке случайную позицию.
Циклом от 1 до 13 проверишь чтобы точка не была в областях
если вдруг оказалась - берём эту область, и выпихиваем точку на некое расстояние из области.

в итоге - если рандомнуло в область, то точка будет около области, а не в ней х)
помойму это будет самый лучший вариант

(ну вместо точек координаты там сравнивать как полагается)
 

DuosoraДата: Вторник, 03 Марта 2015, 15:00:16 | Сообщение # 10
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Extremator,
Кстати, отличная идея! Спасибо огромное =)
Но не откажусь послушать ещё варианты. =)


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

BorodachДата: Вторник, 03 Марта 2015, 15:52:43 | Сообщение # 11
9 уровень
Группа: Проверенные
Сообщений: 930
Награды: 0
Репутация: 422
Блокировки:
Еще вариант перепрыгивать области

Первый рандом для указания направления. Второй промежутки прыжков...


Karamba


Сообщение отредактировал Borodach - Вторник, 03 Марта 2015, 15:55:27
 

ImpregnableДата: Вторник, 03 Марта 2015, 16:19:36 | Сообщение # 12
6 уровень
Группа: Проверенные
Сообщений: 231
Награды: 0
Репутация: 92
Блокировки:
Находим смещение искомой точки по X от центра R, S:
Код

   xOffset = <ширина S>*0.5 + случайное число в диапазоне (0; (<ширина R> - <ширина S> - <ширина T> - <ширина U>)*0.5]
   if( xOffset > <расстояние от центра S до края T по X> )
    xOffset += <Ширина T>
   На данный момент мы имеем абсолютное значение смещения. Чтобы получить само смещение необходимо сменить знак xOffset или оставить как есть.


По аналогии проделываем то же самое и с Y.


Если долго мучиться, то может,
все равно нихуя не получится.


Сообщение отредактировал Impregnable - Вторник, 03 Марта 2015, 16:23:39
 

ExtrematorДата: Вторник, 03 Марта 2015, 16:23:27 | Сообщение # 13
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки:
http://rghost.ru/6znNZgn7m

 

sumertДата: Вторник, 03 Марта 2015, 19:06:39 | Сообщение # 14
10 уровень
Группа: Проверенные
Сообщений: 2330
Награды: 2
Репутация: 1094
Блокировки:
Цитата Duosora ()
Это вновь предложение цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле. Это говорит уже само понятие "каждый раз". Но за попытку благодарочка плюсом)

Можно сделать ограниченное кол-во итераций. Скажем, разделить главную область на, скажем. 12 областей (главное, чтобы хотя бы одна не входила в область S,W итд), которые полностью покрывают главную область. Затем в каждой из области создавать случайную точку и пихать в массив, если она удовлетворяет начальным условиям. Затем из этого массива выбирать случайную точку..
 

VladSekretДата: Среда, 04 Марта 2015, 21:41:29 | Сообщение # 15
6 уровень
Группа: Проверенные
Сообщений: 198
Награды: 0
Репутация: -50
Блокировки:
Цитата Duosora ()
Требуется, не используя циклов, сгенерировать случайную точку в области R, которая бы не находилась ни в области S, ни в области Т, ни в области U, ни в области V, ни в области W.

Ты что-то имеешь против циклов? B)


Сообщение отредактировал VladSekret - Среда, 04 Марта 2015, 21:44:13
 

DuosoraДата: Четверг, 05 Марта 2015, 09:33:26 | Сообщение # 16
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Цитата VladSekret ()
Ты что-то имеешь против циклов? B)

Смотря как, где и для чего используются.
Конкретно здесь...
Цитата Duosora ()
цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

MelodiaДата: Суббота, 07 Марта 2015, 10:14:15 | Сообщение # 17
Группа: Проверенные
Сообщений: 8026
Награды: 5
Репутация: 5041
Блокировки:
Создаём юнит ЮНИТ в области R.

Событие ЮНИТ входит в области S T U W
Действие - б.е. - двинуть юнит в случайную точку в регионе R
Установить ТОЧКА - позиция ЮНИТа.

Добавлено (05 Марта 2015, 11:34:53)
---------------------------------------------
Если кто не понял. Вводим непустое сообщение и наблюдаем

Добавлено (07 Марта 2015, 10:14:15)
---------------------------------------------
че не доехало чтоль?
Ну дуос ты даёшь.


CM wars 1.15
ЭПОХА АНИМИРОВАННЫХ ТРИГГИРАФ ПРЕШЛА
 

BiboДата: Суббота, 07 Марта 2015, 19:05:42 | Сообщение # 18
Группа: Проверенные
Сообщений: 741
Награды: 0
Блокировки:
Самый простой:
Получить случайную точку, проверить ее принадлежность недопустимым областям, в случае совпадения - сдвинуть в случайном направлении к краю (или как душе угодно).
Минус:
В случае возможности нахлеста одной недопустимой области на другую(либо их плотного стыка), после сдвига в случайном направлении, придется снова проверять точку на вхождение, что приводит к заявленной проблеме циклов.

Тяжелый вариант:
Исходить из набора допустимых областей. Сразу за появлением новой недопустимой области, произвести расчет нового набора допустимых областей, создав его триггерно и уничтожив старый набор. После чего выбрать случайную область из набора допустимых и уже затем точку внутри выбранной области.

Ну и третий вариант:
Разделить большую область R на множество очень маленьких, определить в массив допустимых областей. Прямоугольники же T, S, U, V и W удалять из массива допустимых областей R.


Сообщение отредактировал Bibo - Суббота, 07 Марта 2015, 19:09:07
 

SirNikolasДата: Вторник, 10 Марта 2015, 17:44:41 | Сообщение # 19
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Прагматичный ответ: ключевые слова в вопросе - "своими размерами намного меньше области R", а так как областей всего пять, ими можно пренебречь. Посчитай мат. ожидание геометрического распределения при p = 1 - μ(S ∪ T ∪ U ∪ V ∪ W) / μ(R). Графики справа показывают, что даже при p = 50% вероятность получить шесть итераций ничтожно мала.

Математическое решение: пусть у нас есть множество доступных областей, изначально включающее только область R. При "вырезании" каждой из областей S, T, U, V, W проделаем следующее: "разрежем" каждую область из множества доступных по четырем прямым, совпадающим со сторонами текущей области, и удалим те, которые попали "в середину".





Затем подсчитаем площадь каждой получившейся части и заполним массив частичных сумм: a[0] = 0; a[i] = a[i - 1] + (площадь i-той части). Сгенерируем случайное число x = random(0, a[n]). Бинарным поиском найдем элемент a[i], в котором находится x: a[i - 1] < x ≤ a[i]. Теперь мы знаем i ∈ 1, n - индекс части, выбранной наугад со "справедливой" (т. е. зависящей от площади) вероятностью. Бросаем в нее точку.

В этом решении наибольшая часть времени тратится на составление массива частей, то есть оно будет эффективным, если области двигаются значительно реже, чем бросаются точки.


 

Форум о Warcraft 3 » Раздел для картостроителей » Вопросы по картостроению » Рандомизация числа без цикла перегенерации
  • Страница 1 из 1
  • 1
Поиск:

Copyright © 2006 - 2022 Warcraft3FT.info При копировании материалов c сайта ставьте, пожалуйста, активную обратную ссылку на нас • Design by gReeB04ki ©
Хостинг от uCoz