раннер: процедурная генерация платформ различных типов

a7s1h1 · 15.03.2016, 18:20

Здравствуйте!
Делаю раннер-скроллер с бесконечной картой. Бесконечность эту реализовал пока таким образом:
- ГГ движется слева направо, но фактически остаётся на месте, т.к. все объекты движутся со скоростью "скорость ГГ*-1"
- Платформы, оказавшиеся за левым краем экрана, убираются со сцены и из массива платформ
- В кадре стоит проверка количества платформ в соответствующем массиве. Когда платформ становится меньше 12, за правым краем создаётся ещё 8. Учитывая то, что одновременно на экране видно только 9 платформ, этого достаточно, чтобы процесс удаления/создания не был виден

Для генерации партий платформ по 8 штук я использую вектор со значениями uint, т.к. у каждой платформы есть свой тип, выраженный целым числом. Например, партия одинаковых платформ выглядит как [0,0,0,0,0,0,0,0]. При создании платформ через цикл я просто присваиваю им соответствующий тип из массива. Но позже типов становится больше и необходимо расставить их случайно, но с рядом ограничений. Например, когда типа всего 2: 0 и 1, необходимо, чтобы из 8 ячеек единицами было не более 6 и чтобы не больше 3х единиц подряд. Алгоритм создания такого массива я написал, хоть и получилась некрасивая простыня. Но теперь каждый раз, когда мне необходимо добавить очередную партию платформ, из-за этих рассчётов игра подтормаживает (это даже сейчас, когда у меня всего 2 типа, а что будет, когда их будет больше?..)

Вопросы следующие:
- Подскажите, пожалуйста, доходчивый ресурс, где можно почитать про алгоритмы создания случайных комбинаций с заданными ограничениями - мне ничего путного найти не удалось(
- Если расставлять случайные числа по массивам заранее, это поможет избежать "тормозов", но тогда карта не будет бесконечной. В моём же случае каждый раз, когда добавляется новая партия платформ, происходят новые расчёты и появляются лаги. Может быть, есть какой-то лучший способ добиться "бесконечности" карты, кроме удаления и создания за пределами экрана на ходу?

КорДум · 15.03.2016, 18:29

Во-первых, алгоритм создания платформ в данном случае требует реализацию пула, чтобы не тратить драгоценные тики на вызов конструктора.

Во-вторых, что за расчеты у вас такие, что дают лаги?
Покажите код, уверен, Вам укажут на его слабые места.

В-третьих, почему в массиве платформ хранятся типы платформ, а не ссылки на платформы?

dimarik · 15.03.2016, 20:19

Цитата:

Сообщение от a7s1h1

из-за этих рассчётов игра подтормаживает (это даже сейчас, когда у меня всего 2 типа, а что будет, когда их будет больше?..)

Присоединяюсь к КорДуму и спрашиваю за лагающую простыню.
Там делов-то должно быть с гулькин нос.

Можно попробовать заранее нагенерить паттернов. Правда, затрудняюсь сказать о затратах памяти и времени.

a7s1h1 · 16.03.2016, 00:03

Функция движения и удаления блоков, вызывается в кадре:

Код:

// UPDATE BLOCKS
		private function update_blocks(): void {
			// двигаем и удаляем блоки
			var bl:uint = _blocks.length - 1;
			var b:Block;
			// двигаем и удаляем блоки
			for (var i:int=bl;i>=0;i--){
				b = _blocks[i];
				b.x-=_hero.vx //вместо героя двигаем блоки со скоростью героя *-1

				//удаляем блоки, которые оказались за пределами экрана, из массива и со cцены
				if (b.x < -180) {
					b.free(); // внутренняя чистка блока
					_blocks.splice(i, 1); 
					i--;
					//каждый раз при удалении блока проверяем количество оставшихся блоков
					if (bl<14) {addWave()} // если блоков меньше 14 - создаём новую партию блоков
				}
			}
		}

Партии (в коде я называю их волнами) блоков при создании записываются в массив
private var _waves:Vector.<Vector.<uint>>; //двухмерный вектор с числами
Это нужно для того, чтобы при необходимости создать заново уже удалённые блоки (т.е. вернуться к какому-нибудь чекпойнту).
За 1 раз создаётся 10 блоков - это и есть волна. Каждому из 10 блоков случайным образом (но с некоторыми ограничениями) присваивается определённый тип:

Код:

// Создание волны
		private function addWave():void {
			// максимальный тип блока (пока рассматриваем только типы 0 и 1. Чем дальше играть, тем больше будет типов)
			var maxType:uint;
			
			// проверяем номер волны
			var waveNumber:uint = _waves.length; // в начале игры массив волн пуст
			// в первых трёх волнах все блоки (т.е. первые 30 блоков) типа 0
			if (waveNumber == 0) {
				maxType = 0; // тип блока может быть только 0
                                //заполняем первые три ячейки массива волн векторами с 10 типами для присвоения создаваемым функцией addBlocks() блокам
				for (var k:int = 0; k < 3; k++) {
					_waves[_waves.length] = new <uint>[0,0,0,0,0,0,0,0,0,0];
					addBlocks(_waves.length-1);
				}
			} else {
				// проверка доступных типов по номеру волны
				if (waveNumber >= 3) { maxType = 1 }; // с четвёртой волны появлется тип 1
				
				// временный вектор для вычислений (потом приравняем его к вектору волн)
				var tempVector:Vector.<uint> = new < uint > [0,0,0,0,0,0,0,0,0,0];
				var tvl:uint = tempVector.length; // длина вектора
				var testee:uint; // число-кандидат
				var traps:uint = 0; // общее количество типов, отличных от 0 (ловушек)
				var traps1:uint = 0; // количество единиц
				
trace('Проверяем каждый блок')
				// перебор каждого блока
				for (var j:int = 0; j < tvl; j++) {
trace('Блок '+j)
					// выбираем случайное число в пределах доступного максимума типа
					testee = MyMath.randomRange(0, maxType);
trace('Случайно выпало число '+testee+', проверяем, подойдёт ли оно')
					
					// допустимое количество ловушек подряд зависит от выпавшего типа
					var inarow:uint; 
					switch (testee) {
						case 1: inarow=3; break; // блоков типа 1 может быть только 3 подряд 
						default: inarow = 0; break;
					}
trace('Максимальное число ловушек типа '+testee+' - '+inarow)
					
					// если выпал ноль, оставляем так, если нет - проверяем дальше
					if (testee != 0) {
trace('Выпал не ноль, поэтому продолжаем проверку')	
						// если это первая или последняя ячейка, то ставим ноль
						if ((j == 0) || (j == tvl - 1)) {
trace('Ячейка является первой или последней (вот доказательство: j='+j+'), поэтому ставим ноль')	
							testee = 0;
						} else {
trace('Ячейка не является первой или последней (вот доказательство: j='+j+'), поэтому продолжаем')	
							// если ловушек меньше шести - проверяем дальше
							if (traps < 6) {
trace('Ловушек ещё меньше 6 (их на самом деле '+traps+'), поэтому продолжаем')	
								// если блоков типа 1 меньше 6 - проверяем дальше
								if (traps1 < 6) {
trace('Блоковтипа 1 меньше 6 (их на самом деле '+traps1+'), поэтому продолжаем')	
									// проверяем предыдущие клетки (если подряд уже стоит нужное количество - ставим 0)
									// нет смысла проверять ячейки 0-2, т.к. 0 всегда пустая, а 1 и 2 никогда не будут третьей подряд
									// начинаем проверять с ячейки 3, если максимум подряд 2, с 4, если 3 и т.д.
									if (j > (1 + inarow)) {
trace('Индекс проверяемой ячейки ' + j + ', а максимально в ряд может быть ' + inarow + ', поэтому имеет смысл проверять текущую ячейку, т.к. перед ней стоит ' + j + ' ячеек, одна из которых точно нулевая (первая)')
										traps++
										traps1++
trace('Но пока не стал проверять предыдущие ячейки, а просто оставил всё как есть и прибавил счётчик ловушек - теперь их '+traps+', a блоков типа 1 - '+traps1)
									
									// в противном случае не проверяем предыдущие ячейки
									} else {
trace('Индекс проверяемой ячейки ' + j + ', а максимально в ряд может быть ' + inarow + ', поэтому нет смысла проверять текущую ячейку, т.к. перед ней стоит ' + j + ' ячеек, одна из которых точно нулевая (первая)')
										traps++;
									}
								// если блоков с номером 1 уже 6 - ставим 0
								} else {
trace('Блоков типа 1 уже '+traps1+', поэтому мы ставим ноль')
									testee = 0;
								}
							// если ловушек уже 6 - ставим ноль
							} else {
trace('Ловушек всего уже '+traps+', поэтому мы ставим ноль')
								testee = 0;	
							}
						}
					} else {
trace('Так как выпал ноль, мы просто оставили всё, как есть')
					}
trace('В итоге, после всех проверок проверяемое число testee='+testee)
					
					// присваиваем ячейке тестового вектора получившееся значение
					tempVector[j] = testee;
trace('Ячейке временного вектора tempVector[j] присвоено полученное значение, теперь tempVector[j]=' + tempVector[j])
trace('Весь временный вектор на данном этапе выглядит вот так: tempVector='+tempVector)
				}
				// после того, как присвоили значения всем ячейкам, приравниваем очередную волну из массива волн к расчётному вектору
				_waves[_waves.length] = tempVector;
				addBlocks(_waves.length - 1); // добавляем 10 блоков, передав ссылку на нужный вектор, который будет картой типов для создаваемой волны
			}
			
// проверяем список волн и типы блоков в них
for (var i:int = 0; i < _waves.length; i++) { trace('wave ' + i + ': ' + _waves[i]) };
			
			// при создании объектов героя ставим всегда наверх
			setChildIndex(DisplayObject(_hero), numChildren-1);
		}

Таким образом, в вектор с волнами мы добавили волну (вектор с числами), которую будем использовать как карту типов при создании блоков:

Код:

// Создание блоков по указанному массиву вектора волн
		/**
		 * 
		 * @param	wl номер волны для присвоения типа
		 */
		private function addBlocks(wl:uint):void {
			// точка отсчёта для создаваемой волны: либо 0 (если первая), либо x последнего блока
			var sx:int = (_blocks.length>0)?(_blocks[_blocks.length-1].x):(0); 
			// помещаем в массив блоков 10 экземпляров блоков
			for (var b:uint = 0; b < 10; b++) {
                                // суём в массив новый блок, смещая его по x относительно предыдущего, а по оси y просто ставим на уровень земли
				// присваиваем создаваемому блоку тип из массива волн
				_blocks.push(addChild(new Block(sx+BlockW*(b+1), GL,_waves[wl][b])));
			};
		}

Буду признателен за советы по оптимизации системы генерации блоков и их типов.
Про использование пула понял, пока читаю про него и пытаюсь понять, как им пользоваться.

neonoviiwolf · 16.03.2016, 01:20

Ух, по хорошему всё это в классы, а не простыню. Очень много объявляется временных переменных, GC будет часто срабатывать, будут и тормоза. Дальше стоит сделать пул(гуглим, даж тут мои первые попытки найдутся) этих блоков, один раз в начале игры создали и всё. Убрать множество проверок помогут собственные событие(гуглим), но тут увы, только в классах писать (хотя как код перевалил за 800 строк, сами перейдёте на классы и всю игру перепишите и не раз).
Ну а вообще, сходу бы я написал логику типо такой:
раз блоки ограничены изначально, то if (Math.random() > 0.5) vector.push(1) else vector.push(0)
это к примеру, 3 и т.д. соответственно меняем условия (>0.33<0.66)- итого волны будут разные каждый раз.
Дабы блоки не накладывались, есть множество вариантов, я бы сделал через событие, чтобы блок, который на сцене, сообщал сам, когда достаточно места для появления следующего. Ну а скорее всего, исключил бы вектор с типамы блоков изначально и просто бы в зависимости от условия, когда первый блок сообщает о возможности добавить следующий, рандомнобы выбирал что появится следом, меньше переменных - > меньше возни.
Ну и обязательно создать пул для каждого типа блоков

a7s1h1 · 16.03.2016, 09:42

Цитата:

Сообщение от neonoviiwolf

Ух, по хорошему всё это в классы, а не простыню.

Цитата:

Сообщение от neonoviiwolf

Убрать множество проверок помогут собственные событие(гуглим), но тут увы, только в классах писать (хотя как код перевалил за 800 строк, сами перейдёте на классы и всю игру перепишите и не раз).

Возможно, я не так вас понял, но весь вышеописанный код находится в классе Room - это комната-родитель всех находящихся в ней объектов. Чтобы проверять своих детей, родитель должен сам "видеть" их, а не ловить от них события, поэтому код должен быть именно в родителе.

Цитата:

Сообщение от neonoviiwolf

стоит сделать пул

С пулом буду разбираться, в данном случае он необходим, это я понимаю. Но пул решит (надеюсь) только проблему постоянного создания-удаления экземпляров, а проблема с расчётом комбинаций остаётся.

Цитата:

Сообщение от neonoviiwolf

Ну а скорее всего, исключил бы вектор с типамы блоков изначально и просто бы в зависимости от условия, когда первый блок сообщает о возможности добавить следующий, рандомнобы выбирал что появится следом

Таким образом можно контролировать выполнение условий расстановки блоков только в пределах двух блоков - это не подходит. Необходимо составлять комбинацию в партии из 10 блоков.

Итак, допустим, от тормозов из-за создания-удаления объектов я избавлюсь при помощи пула. Теперь, для создания пачки из 10 блоков мне необходим вектор uint с комбинацией случайных чисел, расстановка которых в этом векторе подчинена определённым правилам. Остаётся вопрос:
1. Каков наиболее оптимальный алгоритм такой расстановки?
(Сейчас у меня алгоритм такой: присваиваем ячейке случайное число и проверяем уже созданные ячейки: если разрешение получено, оставляем в проверяемой ячейке выпавшее число, если нет - ставим по умолчанию 0)
(Я думал ещё присваивать числа сразу всем ячейкам, а затем проверять всю комбинацию на выполнение условий, но ведь для этого всё равно придётся проверять каждую из них, поэтому лучше уж решать вопрос о том, можно ли оставлять в ячейке выпавшее число, сразу, при проверке данной ячейки)
(Ещё думал на вариантом: в начале игры вычислить все возможные комбинации всех используемых чисел, затем отсортировать комбинации по различным критериям и распихать по соответствующим массивам, а затем при создании просто брать из массива произвольную комбинацию. К примеру, условия для блока типа 1 в пачке из 10 блоков такие: не больше 6 единиц, не занимать 1 и последнюю ячейки, не ставить 3 единицы подряд. С такими условиями у меня получится несколько комбинаций: [0,1,1,1,0,1,1,1,0,0], [0,0,1,0,0,1,0,1,1,0] и т.д. Я их всех заношу в вектор _combinations1:Vector.<Vector.<uint>>, а при создании выбираю случайную из них MyMath.random(0,_combinations1.length-1))

Tails · 16.03.2016, 10:03

Всё печально.
Вместо того, что-бы двигать каждый блок по отдельности, проще двигать контейнер, содержащий все эти блоки и прочие элементы мира.

А если подойти к делу профессионально, то двигаться должны герой в мире и камера, которая показывает какую то часть этого мира (Например героя). Во флеше нет класса камеры из коробки, но её совсем не сложно сделать самостоятельно, там от силы строк 100-200 кода. По сути, камера это конечная матрица трансформаций, на которую умножаются все дисплей объекты, перед отрисовкой на экране.

Если с камерой совсем не понятно, то сделайте хотя бы контейнер для мира и двигайте его. (По сути это и будет примитивная камера)

a7s1h1 · 16.03.2016, 11:34

Цитата:

Сообщение от Tails

Вместо того, что-бы двигать каждый блок по отдельности, проще двигать контейнер, содержащий все эти блоки и прочие элементы мира.

Вы совершенно правы, но как в этом случае быть со столкновениями? Если я двигаю не блоки, а контейнер с ними, то как герой будет сталкиваться с конкретным блоком?

Tails · 16.03.2016, 12:10

Поместите героя в этот же контейнер с блоками, пусть он там бегает, прыгает и сталкивается.

А теперь внимание!
Чтоб герой всегда был на экране, двигаете контейнер с миром (в котором герой, блоки и всё остальное) вот так:

Код AS3:

world.x = -player.x;

Всё. Герой бегает, блоки двигаются (относительно героя) и при этом герой всегда на экране.

a7s1h1 · 17.03.2016, 13:04

В теме задавалось сразу несколько вопросов, на большинство из которых я, благодаря советам откликнувшихся, нашёл ответы. Всем большое спасибо! Прошу модераторов закрыть тему - более конкретные вопросы лучше задам в отдельно созданных темах.