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

[a7s1h1]

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

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

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

[КорДум]

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

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

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

[dimarik]

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

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

Можно попробовать заранее нагенерить паттернов (https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5). Правда, затрудняюсь сказать о затратах памяти и времени.

[a7s1h1]

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

// 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]

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

[a7s1h1]

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

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

Ну а скорее всего, исключил бы вектор с типамы блоков изначально и просто бы в зависимости от условия, когда первый блок сообщает о возможности добавить следующий, рандомнобы выбирал что появится следом
Таким образом можно контролировать выполнение условий расстановки блоков только в пределах двух блоков - это не подходит. Необходимо составлять комбинацию в партии из 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]

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

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

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

[a7s1h1]

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

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

[Tails]

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

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

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

[a7s1h1]

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