Форум Flasher.ru - мат кол-во невидимых блоков

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

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

- - мат кол-во невидимых блоков (http://www.flasher.ru/forum/showthread.php?t=174344)

мат кол-во невидимых блоков

Собственно как то давно создавал похожую тему, просто щас конкретно допер где глюк.

Задача : есть допустим 100 спрайтов, разной высоты, они помещаются в контейнер таким образом, что если общая высота спрайтов превышает контейнер, то спрайты переносятся на след страницу ( но не наглядно, а в памяти так сказать ).

Как считал кол-во страниц :

Код AS3:

private function getListCount():Number {

 

                        var h:int = 0;

                        var h1:int = _stage.stageHeight - _mainContainer.y;

 

                        for (var i:int = 0; i < _eVector.length; i++) {

 

                                if (i) h += _eVector[i].height + 15;

                                else   h += _eVector[i].height;

                        }

 

                        var lists:Number = h / h1;

 

                        if (lists < 0) lists = 1;

                        else if ( int(lists) < lists ) lists = int(lists) + 1;

 

                        return lists;

                }

Считало поидее верно, но есть нюанс о котором я не знал до этого :
Допустим на первой странице поместилось 3 спрайта, а 4 спрайт очень большой и занял всю вторую страницу, на 3й странице появился маленький спрайт, но фишка в том, что этот маленький спрайт совершенно легко мог быть помещен на 1 страницу в свободное место, поэтому такая система считает, что страниц всего 2, а не 3.
Вот думаю как лучше решить, наверное стоит сначала сортировать вектор по мин > макс высоте , а потом только прогонять в цикле. или есть лучше решение?

Где-то была тема по наиболее оптимальному заполнению прямоугольной области фигурами. Там это было необходимо для текстурирования, и там давали ссылки на алгоритмы. Думаю это должно помочь.

Upd. а вообще можно так реализовать
из массива значений берем максимальное, если место осталось - перебираем максимальное из подходящих и так далее. А при переходе на новую страницу просто page++.

может лучше считать листы при их формировании а не отдельной функцией?

Данные динамические постоянно обновляются значит и листы постоянно обновляются.

TanaTiX - а разве вариант сортировки не поможет, как я предложил?

Сортировка не спасет.

Например есть спрайты с размерами:
5
4
3
2

Отсортированные.
Размер страницы восемь.
Туда влезет 5 + 3, но не 5+4. В итоге упрешься в то же что у тебя сейчас.

Наверное немного не так
сортируем 2,3,4,5 размер 8.
страница 1 : 2 + 3
страница 2 : 4 ( ибо 4 + 5 не выйдет, а 2 и 3 уже просчитано )
страница 3: 5
все четко

В зависимости от количества элементов, разница между реальностью и расчетным количеством может накапливаться. Поэтому лучше это делать при построении страниц. К тому же алгоритм практически одинаков.

Добавлено через 23 минуты
Наверняка не самый лучший вариант, но на скорую руку...

Код AS3:

var h:int = 8;

var arr = [2,4,5,3];

var list:int=0;

arr.sort(Array.DESCENDING);

getList();

function getList():void{

        if(arr.length==0){

                trace("length", list);

                return;

        }

        if(arr[0]>h){

                list++;

                arr.shift();

        }else{

                if(arr.length==2){

                        arr.pop();

                }else{

                        if(arr.length>1){

                                for(var i:int=arr.length - 1; i>1; i--){

                                        if(arr[0]+arr[i]==h || (arr[0]+arr[i]>h && i!=arr.length - 1)){

                                                arr.splice(i, 1);

                                                break;

                                        }

                                }

                        }

                }

                arr.shift();

                list++;

        }

        getList();

}

Задача о рюкзаке?

TanaTiX да, алгоритм тяжелый получился :) если лучше не придумаю придется наверное так

Цитата:

алгоритм тяжелый получился

При желании можно и без рекурсии одним проходом. Допиливать наверняка есть что. Но по сути будет тоже самое. В плане производительности нужно иметь хотя бы альтернативу для сравнения.

Привет TanaTix снова. Че то я сел за алгоритм, и решил его еще проще чем было изначально , вот как все вышло

Код AS3:

private function getListCount():Number {

 

                        var h:int = 0;

                        var h1:int = _stage.stageHeight - _mainContainer.y; // область куда могут влезть блоки

 

                        var pages:int = 1; // сразу заявляем что у нас 1 страница, ибо 0 быть не может

                        var len:int = _eVector.length;

 

                        for (var i:int = 0; i < len; i++) {

 

                                var h3:Number = _eVector[i].height;

 

                                if (h > 0) h += h3 + 15; 

                                else        h += h3 ;  // первый блок всегда идет без разделителя, тоесть с 0 координаты

 

                                if      ( h > h1  ) pages++ , h = 0 ,  i--; // если высота уже заявленных блоков + высота этого блока больше высоты области, добавляем страницу, обнуляем высоту для селд страницы, и со след итерации снова проверим этот блок, так как он попадает на новую страницу

                                else if ( h == h1 ) pages++ , h = 0; // если высоты равны, значит все поместилось, но явно будет след страница, а вот этот блок переносить уже не надо

                        }

 

                        return pages;

                }