Comments 14
Спасибо, искал алгоритмы для упаковки текстур игры.
Это совершенно другая задача, для генерации текстурных атласов существуют более эффективные алгоритмы.
Надписи отрендеренные из вектора так можно укладывать в большую текстуру-кэш. Ну и любой другой пререндер плавающего размера, который не сразу, а по требованию делается.
А для атласов какие алгоритмы посмотреть можно?
А для атласов какие алгоритмы посмотреть можно?
Для динамического заполнения атласа без удаления в моём случае очень хорошо работал крайне простой метод (до которого, к своему стыду, я догадался не сам, а подсмотрел у кого-то в бложике).
Сейчас, увы, не смог найти ссылку на оригинал, поэтому попытаюсь по памяти воспроизвести идею алгоритма:
Да, его можно запороть (откажется добавлять, хотя физически место будет) специально подготовленными данными, но на практике такое мне не попадалось.
Сейчас, увы, не смог найти ссылку на оригинал, поэтому попытаюсь по памяти воспроизвести идею алгоритма:
- Инициализируем список свободных прямоугольных зон одной записью размером со всю текстуру (да, с её размером нужно угадать)
- При добавлении элемента проходим по списку зон последовательно, пока не найдём такую, в которую влезет наш фрагмент.
- Если ширина зоны больше ширины нового фрагмента, то делим зону на две новые зоны так, чтобы ширина первой из них была равна ширине нового фрагмента. Новые полученные зоны вставляем в список на место старой зоны (это важно).
- --//-- высота --//--
- В этом месте размеры зоны и нового фрагмента равны. Блитим, удаляем зону из списка свободных зон.
- PORBLEM SOVLED
Да, его можно запороть (откажется добавлять, хотя физически место будет) специально подготовленными данными, но на практике такое мне не попадалось.
Ага вот этот метод Packing Lightmaps
Для чего такая специфическая задача?
Все задачи что я мог придумать (тот же атлас текстур, резка листового материала с наименьшим количеством остатков и другие) не нуждаются в том условии, который взят за основу изначально — неперемещаемости элементов после их постановки (а также выбранного порядка).
Все задачи что я мог придумать (тот же атлас текстур, резка листового материала с наименьшим количеством остатков и другие) не нуждаются в том условии, который взят за основу изначально — неперемещаемости элементов после их постановки (а также выбранного порядка).
Для разумной вычислительной сложности. Или для того, чтобы элементы обрабатывались немедленно, как те же задачи на кластере: получил — разместил — запустил и не трогаешь.
Вопрос в том, есть ли смысл элементы перемещать после упаковки. Идеального решения может и не существовать. Задача об упаковке тем и примечательна, что при своей NP-трудности имеет неплохие алгоритмы решения, и даже асимптотические схемы приближения к конкретному желаемому качеству упаковки.
Вопрос в том, есть ли смысл элементы перемещать после упаковки. Идеального решения может и не существовать. Задача об упаковке тем и примечательна, что при своей NP-трудности имеет неплохие алгоритмы решения, и даже асимптотические схемы приближения к конкретному желаемому качеству упаковки.
Ну а всё-таки, физически для каких целей могут понадобиться такие алгоритмы?
Я привел пример задач при условии что элементы после постановки перемещать можно, но данные алгоритмы не подходят для этих задач. Для чего же они нужны?
Исключая идеальные условия, алгоритмы с перемещением элементов после перестановки будут эффективнее обозреваемых в статье.
Я привел пример задач при условии что элементы после постановки перемещать можно, но данные алгоритмы не подходят для этих задач. Для чего же они нужны?
Исключая идеальные условия, алгоритмы с перемещением элементов после перестановки будут эффективнее обозреваемых в статье.
Вроде неплохая задачка для google AI contest. А то они в этом году отморозились что-то…
Писал в молодости на 80286-м тетрис, где можно было играть против компьютера (в два стакана, при стирании ряда в твоём стакане делается какая-то подлянка в чужом). Долго возился с тем, чтобы придумать компьютеру более-менее адекватный алгоритм размещения кусочков, но всё было без толку: либо алгоритм невозможно тормозил, либо компьютер безнадёжно проигрывал человеку. В конце концов один умный человек подсказал подсыпать компьютеру в стакан удобные кусочки, а человеку случайные. После этого игра удалась на славу :-)
Странно. Я тоже в школе в 11-м классе писал на 8086 («Мазовия» у меня была) тоже тетрис. Правда не против компьютера, а просто был тетрис, с возможностью игры компьютера. Вроде бы использовал несложный алгоритм, работал он очень быстро, и можно было выставить скорость («сложность») тетриса очень высокой — компьютр все равно справлялся. Писал на Turbo Pascal. Но фигуры можно было вращать, как в обычном тетрисе. По-моему, перебирались все возможные комбинации (4 поворота * число смещений), так как стакан сам по себе не очень широкий, ну, скажем комбинаций 20-30 по ширине, с учетом вращений, давало где-то 80-120 комбинаций всего. И для каждой комбинации считалась штрафная функция — чем меньше она, тем выгоднее позиция. Там, кажется, штраф был за «закрытый» пузырь внутри, за «открытый» пузырь штраф был меньше. Детали уже не помню. Но работало практически моментально — даже на 8086 перебрать 120 комбинаций — не проблема.
читер
Sign up to leave a comment.
Про двумерную упаковку: online алгоритмы