Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 17.03.2016, 13:17
a7s1h1 вне форума Посмотреть профиль Отправить личное сообщение для a7s1h1 Найти все сообщения от a7s1h1
  № 1  
Ответить с цитированием
a7s1h1

Регистрация: Oct 2013
Сообщений: 126
По умолчанию алгоритм расстановки случайных чисел в одномерном массиве с условиями

Здравствуйте!
Пытаюсь разработать алгоритм расстановки случайных чисел в одномерном массиве, ограниченной определёнными условиями. Планировал делать это простым перебором:
1. Присваиваю ячейке случайное число, чтобы проверить, подходит ли оно
2. Проверяю условия (в-основном, это сравнение с другими ячейками)
3. Если условие выполняется - перехожу к следующему условию. Если не выполняется, уменьшаю число на 1 и повторяю проверку всех условий с самого начала
4. Если все условия выполнились, ставлю триггер успеха проверки и перехожу к следующей ячейке.

Однако прежде, чем вставлять какие-то условия, я решил на примитивном примере оценить быстродействие такой схемы:
Код AS3:
var ok:Boolean = false
trace('ok='+ok)
var n:uint = 100;
while (!ok) {
	trace('n='+n)
	if (n > 0) {
		n--
	} else {
		ok=true
	}
}
trace('ok='+ok)
Тут единственное условие, чтобы n было не больше 0. Если условие не выполняется, уменьшаем n на 1 и повторяем проверку. Получается "Число 100 равно нулю? Нет? А 99? Нет? А 98?", и т.д. В итоге получается 100 проверок.
Казалось бы, элементарные вычисления (проверок 100, но условие всего одно), но каждый раз, когда они происходят, игра зависает на пару секунд.
Объясните, пожалуйста, почему так, и какой способ циклической проверки будет более эффективен? Заранее спасибо!


Последний раз редактировалось a7s1h1; 17.03.2016 в 17:42. Причина: уточнение заголовка
Старый 17.03.2016, 13:20
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 2  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
Здесь на форуме есть теги AS3 подсветки, нужно пользоваться ими для оформления своего кода. Такой одноцветный код даже читать не охото.

Не нужно делать циклы типа while(!ok). В as3 все выполняется в одном потоке и циклы не исключение. Подобное условие может либо очень долго не выполниться, либо вообще не выполниться. Зависание в этом случае гарантировано. Циклы нужно ограничивать в количестве итераций.
Но конкретно об этом цикле, я сомневаюсь, что из-за него игра зависает на пару секунд. Это просто невозможно. 100 простых итераций он отработает мгновенно. Явно дело в чем-то другом.
__________________
Ко мне можно и нужно обращаться на ты)

Старый 17.03.2016, 13:24
a7s1h1 вне форума Посмотреть профиль Отправить личное сообщение для a7s1h1 Найти все сообщения от a7s1h1
  № 3  
Ответить с цитированием
a7s1h1

Регистрация: Oct 2013
Сообщений: 126
Цитата:
Сообщение от caseyryan Посмотреть сообщение
Здесь на форуме есть теги AS3 подсветки, нужно пользоваться ими для оформления своего кода. Такой одноцветный код даже читать не охото.
Прошу прощения, не обращал внимания на этот тег. Исправил

Старый 17.03.2016, 13:25
caseyryan вне форума Посмотреть профиль Отправить личное сообщение для caseyryan Найти все сообщения от caseyryan
  № 4  
Ответить с цитированием
caseyryan
 
Аватар для caseyryan

Регистрация: Jun 2012
Адрес: Новосибирск
Сообщений: 6,644
Записей в блоге: 4
дополнил свой ответ
__________________
Ко мне можно и нужно обращаться на ты)

Старый 17.03.2016, 13:39
a7s1h1 вне форума Посмотреть профиль Отправить личное сообщение для a7s1h1 Найти все сообщения от a7s1h1
  № 5  
Ответить с цитированием
a7s1h1

Регистрация: Oct 2013
Сообщений: 126
Цитата:
Сообщение от caseyryan Посмотреть сообщение
Но конкретно об этом цикле, я сомневаюсь, что из-за него игра зависает на пару секунд. Это просто невозможно. 100 простых итераций он отработает мгновенно. Явно дело в чем-то другом.
Я стараюсь по возможности избегать while, просто решил проверить. Действительно, попереставлял этот кусок кода в разные места, иногда тормозит, иногда нет.

Тем не менее, остаётся вопрос: какой алгоритм использовать для расстановки случайных чисел (допустим, от 0 до 9) в одномерном массиве длиной в 8 ячеек, со следующими ограничениями:
- не больше 6 чисел, отличных от 0;
- не больше 4 одинаковых чисел;
- не больше 2 одинаковых числе подряд.
Мне на ум приходит 2 варианта:
1. Присваивать по-очереди каждой ячейке случайное число и проверять, подходит ли оно, уменьшая на 1 в случае неудачи, вплоть до 0;
2. Присвоить случайные числа сразу всем ячейкам, затем проверять условия сразу по всем и, если где-то косяк, присвоить новую комбинацию - и так до тех пор, пока комбинация не окажется удачной.
Какой подход лучше: 1, 2 или есть другие?

Старый 17.03.2016, 13:54
Wolsh вне форума Посмотреть профиль Отправить личное сообщение для Wolsh Найти все сообщения от Wolsh
  № 6  
Ответить с цитированием
Wolsh
Нуб нубам
 
Аватар для Wolsh

модератор форума
Регистрация: Jan 2006
Адрес: Бердск, НСО
Сообщений: 6,445
У Вас всего 6 ячеек, на которые 9 цифр (1..9). Так что пункты 2 и 3 можно вообще откинуть и использовать ВСЕ разные цифры по одной (кроме заранее забитых двух нулей).
Создаете массив [1, 2, 3, 4, 5, 6, 7, 8, 9], это будет массив-"пул", из которого Вы просто дергаете по рандомному индексу число (удаляете его из пула!) и добавляете в свой массив блоков. Затем рандомно вставляете два нолика.
__________________
Reality.getBounds(this);

Старый 17.03.2016, 14:02
a7s1h1 вне форума Посмотреть профиль Отправить личное сообщение для a7s1h1 Найти все сообщения от a7s1h1
  № 7  
Ответить с цитированием
a7s1h1

Регистрация: Oct 2013
Сообщений: 126
Цитата:
Сообщение от Wolsh Посмотреть сообщение
использовать ВСЕ разные цифры по одной (кроме заранее забитых двух нулей)
так не пойдёт, нужно, чтобы цифры могли повторяться (но не более 2х подряд и не более 4 одинаковых)

Старый 17.03.2016, 15:11
Wolsh вне форума Посмотреть профиль Отправить личное сообщение для Wolsh Найти все сообщения от Wolsh
  № 8  
Ответить с цитированием
Wolsh
Нуб нубам
 
Аватар для Wolsh

модератор форума
Регистрация: Jan 2006
Адрес: Бердск, НСО
Сообщений: 6,445
"не более 4 одинаковых" — добавляйте в пул по 4 одинаковых.
"не более 2х подряд" — Узнать, что две предыдущие равны добавляемой не проблема. Проверяете последнюю в блоках, если равна то проверяете предыдущую. Последнюю можно даже хранить в переменной чтоб "далеко не ходить". Это поможет также избежать лишнего повтора на стыках "волн".
__________________
Reality.getBounds(this);

Старый 17.03.2016, 18:28
a7s1h1 вне форума Посмотреть профиль Отправить личное сообщение для a7s1h1 Найти все сообщения от a7s1h1
  № 9  
Ответить с цитированием
a7s1h1

Регистрация: Oct 2013
Сообщений: 126
Попробовал сделать, как вы сказали.
Напоминаю условия:
- массив из 10 ячеек необходимо заполнить случайными цифрами от 0 до 9 с соблюдением ряда условий
- первая и последняя ячейка всегда 0
- максимальное количество не нолей - 6
- максимальная цифра известна заранее
- максимальное количество одинаковых цифр: единиц, двоек, троек по 4, 4-6 максимум по 3, 7-8 максимум по 2, девятка только одна
- максимальное количество одинаковых цифр подряд - 2

Вот что получилось:
Код AS3:
var max_level:uint = 9; // максимальная цифра - пусть сейчас это будет 9
 
// вектор, который необходимо заполнить. Заполняем его нулями
var temp_vector:Vector.<uint> = new < uint > [0,0,0,0,0,0,0,0,0,0];
 
// если максимальный уровень = 0, то ничего не проверяем, везде остаются нули
if (max_level > 0) {
	// создаём мешок с цифрами, откуда будем их вытаскивать
	var bag:Vector.<uint>;
	// в мешок суём все цифры до максимальной
	// количество каждой цифы ставим максимальное (т.к. из 10 ячеек первая и последняя точно нули, то будем проверять только 8 ячеек, соответственно суём в мешок максимально возможное количество каждой цифры: 8 нолей, остальные смотря по цифре)
	switch (max_level) {
		case 1: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1]; break; //1 не более 4
		case 2: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2]; break; //2 не более 4
		case 3: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3]; break; //3 не более 4
		case 4: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4]; break; //4 не более 3
		case 5: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5]; break; //5 не более 3
		case 6: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6]; break; //6 не более 3
		case 7: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7]; break; 		//7 не более 2
		case 8: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8]; break; 	//8 не более 2
		case 9: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8,9]; break; 	//9 не более 1
	}
 
	var testee:uint=0; 	// проверяемая цифра
	var previous1:uint = 0; // предыдущая цифра
	var previous2:uint = 0; // предпредыдущая цифра
	var tvl:int = temp_vector.length; // длина временного вектора для ссылки в цикле
 
 
 
	// перебор каждой ячейки, кроме первой и последней (получается 8)
	for (var i:int = 1; i < tvl - 1; i++) {
		var bag_length:uint = bag.length; // длина мешка для ссылки в цикле
		// достаём из мешка случайную цифру, пока не выпадет та, которая не совпадает с предыдущими двумя
		while (testee == previous1) {
			testee = bag[MyMath.randomRange(0, bag_length - 1)]
			if (testee != previous2) {break	}
		}
 
		// найдя подходящую цифру,
		temp_vector[i] = testee; // заносим её в соответствующую ячейку временного вектора
		previous2 = previous1; // записываем предыдущие цифры
		previous1 = testee; // записываем предыдущие цифры
		bag.splice(i, 1); // удаляем выбранную цифру из мешка
	}
}
//проверяем, что получилось
trace('temp_vector='+temp_vector)
Код работает, как надо, только есть две проблемы:
1. Выглядит не очень, поможете оптимизировать?
2. Не соблюдается правило "не больше 6 цифр, отличных от нуля". В какой момент и как
Цитата:
Сообщение от Wolsh Посмотреть сообщение
рандомно вставляете два нолика.
, пока не смекнул Подскажите, пожалуйста

Старый 17.03.2016, 22:09
Wolsh вне форума Посмотреть профиль Отправить личное сообщение для Wolsh Найти все сообщения от Wolsh
  № 10  
Ответить с цитированием
Wolsh
Нуб нубам
 
Аватар для Wolsh

модератор форума
Регистрация: Jan 2006
Адрес: Бердск, НСО
Сообщений: 6,445
1. Конечно. Надо взять только последний, самый длинный вариант bag. А вот чтобы не брать из него дальше нужного индекса, надо всего-лишь ограничить рандом не реальной длиной массива, а максимальным для данного левела индексом (для первого — 11, для второго — 15 и тд.). Ах да, тогда придется с каждым вынутым числом менять и максимум(( Не очень красиво наверно)))
2. "Не больше шести..." — так если Вы будете брать из мешка всего шесть чисел, включая ноли, то "ненолей" больше шести никак и не получится. Берете шесть чисел из мешка, а ПОТОМ вставляете еще два ноля в рандомные индексы от 2 до 7 (чтобы не касались нолей по краям массива). И так у Вас в массиве будет минимум 4 ноля и максимум 6 ненолей.
__________________
Reality.getBounds(this);

Создать новую тему Ответ Часовой пояс GMT +4, время: 13:25.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 13:25.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.