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

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

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

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

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

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

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

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

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

Цитата:

Сообщение от a7s1h1 (Сообщение 1192632)

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

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

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

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

Код:

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

                        };

                }

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

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

Цитата:

Сообщение от neonoviiwolf (Сообщение 1192648)

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

Цитата:

Сообщение от neonoviiwolf (Сообщение 1192648)

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

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

Цитата:

Сообщение от neonoviiwolf (Сообщение 1192648)

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

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

Цитата:

Сообщение от neonoviiwolf (Сообщение 1192648)

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

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

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

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

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

Цитата:

Сообщение от Tails (Сообщение 1192651)

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

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

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

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

Код AS3:

world.x = -player.x;

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

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