Как вырастить лес на Actionscript3/Flash в несколько* строк кода

    Вот в этом комменте я похвастался, что в своё время написал программу, создающую рендер «пристойно выглядящего» леса в двести строк кода. К сожалению, реальность оказалась немного большей по размеру — раскопанные исходники содержат примерно 2100 строк кода, из которых где-то 700 — комментарии, мысли вслух, старый отброшенный код и попытки документации методов. Размер исполняемого файла SWF, впрочем, оказался 13112 байт.

    Началось всё с того, что на форуме Kongregate.com, где я в то время активно тусил, один из участников предложил посостязаться в процедурной генерации чего-либо, первой темой стал «Лес».



    Естественно, у каждого была своя идея, каким должен быть лес, который они будут выращивать. На тот момент я зачитывался книгами про всякую магию, как следствие, захотел вырастить именно лес. Лес состоит из деревьев — пишем class Tree {...}. Дерево состоит из веток и листьев — пишем class Branch {...} и думаем, а так ли нам нужно учитывать каждый листик на дереве? В итоге «ветка» обзавелась параметром «с листьями», а дерево — парой текстур, одной для веток и ствола, одной для листиков. Текстуру «под дерево» сделать было относительно просто — есть perlin noise, его можно растянуть, завернуть, раскрасить, считай готово, а с листиками пришлось повозиться.

    Однако меня не устроил просто перлиновый шум на текстуре под дерево, вместо него я придумал сделать bumpmapping — т.е. создал карту высот, подправил её под полукруг ветки, видимой сбоку, потом залил основную текстуру коричневым и наложил карту высот с прилаженным сбоку-сприпёку освещением. Итоговый код получился таким:

    private function generateBranch():void {
    			branchBitmap = new BitmapData(512, 512, true, 0xff8080ff);
    			//branchBitmap.perlinNoise(32, 256, 2, 100 + Math.round(Math.random() * 900), true, true, 7, true);
    			var hm:BitmapData = new BitmapData(512, 512, false, 0);
    			var seed:int = 1000 + Math.random() * 2000;
    			hm.perlinNoise(24,192, 2, seed, true, true, BitmapDataChannel.BLUE, false); // blue only. Is a heightmap
    			var i:int;
    			var j:int;
    			for (i = 0; i < 512; i++) {
    				if (Math.abs(i - 256) > 100) r = 0; else
    					r = 200 * Math.sqrt(1 - (i - 256) * (i - 256) / 10000);// square curve
    					//r = 200 * Math.sin(Math.PI * (i - 128) / 256); // sine curve
    				for (j = 0; j < 512; j++) hm.setPixel(i, j, Math.round(r*(500.0 + (hm.getPixel(i, j)-128))*0.002));
    				// now, r means position on the "log", and initial perlin noise is log's texture. 
    				// perlinNoise median 128, highest offset taking as 100, the result offset needs to be ~0.2 in multiplier
    			}
    			
    			var v:Vector.<int> = new Vector.<int>();
    			var vv:Vector.<Number> = new Vector.<Number>(3);
    			for (i = 1; i < 511; i++) {
    				v.length = 0;
    				v.push(hm.getPixel(0, i-1), hm.getPixel(1, i-1), hm.getPixel(2, i-1), hm.getPixel(0, i), hm.getPixel(1, i), hm.getPixel(2, i),
    					hm.getPixel(0, i+i), hm.getPixel(1, i+1), hm.getPixel(2, i+1));
    				for (j = 1; j < 510; j++) {
    					var g:int = -1 * v[0] - 2 * v[1] - 1 * v[2] + 1 * v[8] + 2 * v[7] + 1 * v[6]; // gradient by Y
    					var r:int = -1 * v[0] - 2 * v[3] - 1 * v[6] + 1 * v[2] + 2 * v[5] + 1 * v[8]; // gradient by X
    					//if ((i > 50) && (i < 55) && (j > 50) && (j < 55)) trace(g, r);
    					var b:int = v[5];
    					r += 128;
    					g += 128;
    					var p:uint = r *0x10000 + g*0x100 + b;
    					branchBitmap.setPixel(j, i, p);
    					v.shift();
    					v.push(hm.getPixel(j + 2, i + 1));
    					v[2] = hm.getPixel(j + 2, i - 1);
    					v[5] = hm.getPixel(j + 2, i);
    				}
    			}
    			var bf:BlurFilter = new BlurFilter(2,8);							//  ___
    			// bevelFilter is not what I need, it bevels a rectangle and just that [___]
    			// dropShadowFilter requires empty alpha I believe
    			// convolution filter works best on self, while it can do what I need
    			branchBitmap.applyFilter(branchBitmap, branchBitmap.rect, P0, bf);
    			hm.copyPixels(branchBitmap, branchBitmap.rect, P0); 
    			//branchBitmap.perlinNoise(32, 256, 0, seed, true, true, 7, true); // naked grayscale
    			// 0 octaves means 50% gray filling
    			branchBitmap.fillRect(branchBitmap.rect, 0xff808080); // it looks like I'll have enough details just by perlin-noising the heightmap
    			var inc:Number = Math.PI / 3;
    			var azi:Number = -Math.PI * 1 / 4;
    			var cx:Number = Math.cos(inc) * Math.cos(azi);
    			var cy:Number = Math.cos(inc) * Math.sin(azi);
    			var cz:Number = Math.sin(inc);
    			azi = 1 - 2 * cz;
    			inc = 1 / cz; // cos(lighting) to be normalized into (0..1) via cz
    			for (i = 0; i < 512; i++) for (j = 0; j < 512; j++) {
    				p = branchBitmap.getPixel(j, i);
    				var h:uint = hm.getPixel(j, i);
    				// give a vector here somewhere
    				vv[0]= (h >> 16)-128;
    				vv[1] = ((h >> 8) & 255)-128;
    				vv[2] = 26; // balance constant, a normal is always pointing upwards, 
    				Basis.Normalize(vv);
    				var m:Number = inc*(cx * vv[0] + cy * vv[1] + cz * vv[2]); // cos(lightangle)
    				r = (p >> 16) & 255;
    				g = (p >> 8) & 255;
    				b = p & 255;
    				r = Math.max(0,Math.min(255, r * m));
    				g = Math.max(0,Math.min(255, g * m));
    				b = Math.max(0,Math.min(255, b * m));
    				branchBitmap.setPixel(j, i, 0x10000 * r + 0x100 * g + b);
    			}
    			branchBitmap.applyFilter(branchBitmap, branchBitmap.rect,  P0,bf); // should be here, without blurring it's liney
    			hm = new BitmapData(192, 512, false);
    			hm.copyPixels(branchBitmap, new Rectangle(160, 0, 192, 512), P0);
    			branchBitmap = hm;
    		}

    «Basis» — вспомогательный класс для векторов а-ля Vector3D, но так как писался код тогда под Flash 10.1, там ещё не было таких векторов, или я предпочел сделать свой велосипед. Текстура под ветку с листьями рисовалась так: вначале делался один лист, затем определялось, будет ли у веток центральный лист, этим определялась длина куска ветки, к которой крепились листья, затем по вычисленной ширине листа они крепились (рисовались на текстуре) под углом к ветке. Форма листа задавалась как искаженный круг с несколькими опорными точками, смещенными относительно круга радиусом пол-листа, и отдельно задавалась длина черенка, всё это рисовалось на текстуре листика в черно-белом виде и сохранялось на будущее. (Точнее, текстур «ветка с листьями» было две, одна для концов, т.е. веток, у которых из «конца» ничего не растет, но они с листьями, на ней был нарисован лист в конце ветки, вторая для «середин» без концевого листа.)

    Дальше самое сложное — как будет выглядеть дерево? Здесь я долго думал и экспериментировал. Я решил сделать так, что дерево в самом деле растет — ветки вытягиваются в длину (на самом деле наращиваются с конца), иногда порождают ветки вбок, ветки тянутся к солнцу (вверх) и ещё пара условий. Получилась страшная мешанина, лучший вариант, которым удалось поделиться, выглядел вот так:

    image
    (Как ни странно, diary.ru — отличный фотохостинг, до сих пор ничего не протухло!)

    Я пришел к выводу, что нужно как-то уменьшать плотность веток. Вначале идея была ограничить их гравитационно — т.е. слишком «тяжелые» ветки просто обламываются и падают. Начал считать момент силы на изгиб, сопоставляя с прочностью дерева (откуда-то потащил значения, забил как константы и стал тестировать) — получилось плохо, иной раз ломался ствол, даже несмотря на то, что по факту не должен был, и дерево благополучно загибалось, иной раз ломалась вначале одна большая ветка, результат приводил к разбалансировке ствола и он опять ломался, на сей раз уже из-за потери вертикального баланса, а иной раз вполне нормальная по структуре ветка, вырастая в толщине, вначале прогиалась под своим весом, потом ломалась, даже если ничего на ней больше не вырастало. Забил, потому что у челленджа был дедлайн.

    Второй попыткой было ограничивать как рост новых веток, так и выживаемость старых/предыдущих с помощью освещения. С третьей попытки реализации (первые две остались в виде закомментированных функций) получилось так: я строил трехмерную воксельную решетку со стороной 0.5 метра (угу, все величины там были в метрах и килограммах — я тогда очень хотел настоящую физику для настоящего леса), которая заполнялась вначале нулями, потом при обходе дерева каждая ветка давала вклад в заполнение решетки в виде своего объема, деленного на один или два вокселя. Дело в том, что все ветки (во всяком случае, почти все) как отдельные куски вычисляемого каркаса были короче 0.5м, что позволяло использовать грубое приближение. Помимо заполнения, каждая ветка «отбрасывала тень» на нижележащие воксели в виде дополнительного заполнения вокселей под и слегка вокруг вокселя с веткой (итоговая форма — квадратная пирамида, но маяться с кругом было влом, и так уже не освещение получалось а невесть что). Эта решетка использовалась в качестве ограничителя, если какая-то из веток затеет вырасти в середину дерева — ей там будет меньше света, она будет короче и может не вырасти вовсе или помереть от недостатка освещения. Мертвые ветки потом отваливались.

    Такой вариант позволил получить относительно прозрачные при просмотре и относительно компактные с точки зрения размаха деревья, первый рабочий вариант выглядел вот так:



    В этой версии я ещё отлаживал сам механизм роста дерева, и дерево можно было рассмотреть со всех сторон. Рисовалось дерево по одной ветке за раз, массив веток вначале сортировался по удалению от наблюдателя, как в старом добром ВМКшном курсе по трехмерной графике от 1996 года, цвета для прорисовки я в рамках косметических фишек выбирал из диапазона HSB на каждый вызов «нарисуй мне дерево», чтобы лес был не монотонным, также скелет дерева случайным образом поворачивался для прорисовки. Всего моделей деревьев за прорисовку было от шести до восьми, каждая вырастала под своим собственным RNG-влиянием, ландшафт земли задавал ещё один перлиновый шум, а место, где растить дерево, выбиралось случайным образом с помощью набора диапазонов разрешенных точек для роста на сдвигающейся в сторону наблюдателя дистанции. В случае, если дерево сажалось в точке А, а радиус у выбранного для «выращивания» дерева R, то значения (A-R, A+R) становились запрещенными для роста на текущей дистанции, при переходе к следующей (-0.05) этот интервал уменьшался на 0.1, и убирался, когда сокращался до нуля.

    Последний (а по факту первый и сразу учтенный) нюанс всего этого алгоритма — он ОЧЕНЬ ДОЛГИЙ. Чтобы обойти «взрослое» дерево, требуется несколько секунд, чтоы нарисовать, ещё несколько, чтобы нарисовать текстуры одного дерева, уходит от полусекунды до двух, а Adobe Flash не рассчитан на настолько долгие промежутки вычислений без обновления экрана (точнее, без возврата управления движку). Следовательно, нужен был алгоритм, который умеет сохранять состояние между вызовами, продолжать работу с места, где прервался и контролировать своё время выполнения, и одновременно не паниковать сам и не давать паниковать движку флэша. Сохранение состояния было реализовано в виде пары свойств класса Main, разбиение на этапы — через выделение функций «расти дерево один раз», «нарисуй готовое дерево» и «нарисуй кусок земли» и замер затраченного времени, соответственно, как только очередной «один раз» для дерева занимал больше нескольких секунд, дерево считалось «готовым» и откладывалось в сторону. Получилось три больших фазы: создание текстур, «выращивание» деревьев, размещение готовых деревьев на экране.

    Результат выглядит так:



    Поиграться можно вот здесь. Оптимизировано (точнее, написано) под Flash 10.1, с учетом кучи обновлений флэша в части безопасности может ужасно тормозить — в этом случае советую скачать debug-версию Adobe Flash Player 11.5 и открывать в ней оффлайн. Вся прорисовка занимает 5-6 минут, после первых двух на экране начинает происходить некоторая движуха, за которой может оказаться интересным понаблюдать. После завершения прорисовки можно нажать Ctrl+click, чтобы сохранить результат как PNG-файл учетверенного по сравнению с окном размера.
    Поделиться публикацией
    Комментарии 23
      0
      Спасибо большое за статью.
      Первый раз вижу код на флеше, кстати. Интересненько.
        0
        Он чем-то похож на С++ и Джаву, без переусложненностей джавы и шаблонов сиплюсплюса. Что интересно, третья (она же последняя, похоже) версия куда как серьезнее уклоняется в ООП, чем вторая и тем более первая.
        0
        Началось всё с того, что на форуме Kongregate.com, где я в то время активно тусил, один из участников предложил посостязаться в процедурной генерации чего-либо, первой темой стал «Лес».


        В итоге Вы выиграли состязание? :)
          0
          Нет, но где-то третье место занял. Может, четвертое. Победитель сгенерировал лес из 4 двухмерных слоев с красивыми шапками, который не требовал слишком больших затрат на рендер и как следствие был пригоден к чему-либо ещё, кроме как покрасоваться.
            0

            2д? Тема была просто "лес"? Не 3д? (даже без физики) P.S. Помнится, у НВидии была интересная интерактивная демка процедурной генерации дерева.

              0
              Ну, его визуализация создавала эффект параллакса в том числе, то есть этакое 2.5D. Да, тема была просто «лес». Таких соревнований там было в итоге три, с темами «лес», «города» и «планеты», планетная была ИМХО интереснее остальных, потом все участники разбежались.
          0
          А почему не на фракталах?
            –1
            Я не знаю такого фрактала, который способен породить дерево.
              +3
                –1
                Да, потом вспомнил. В их сторону и не смотрел, потому что они детерминированы, а мне нужно было, чтобы результат был случайным, но «похожим на дерево». Спасибо все равно.
                  +1
                  L-системы не обязательно должны быть детерминированы, вся суть сводится к рекурсивной замене отдельных символов в строке (палочек веток) на подстроки (ветви). Что на что заменять описывается правилами, которые могут быть какими угодно, например заменить одну палку на три случайной длины под случайными углами, либо выбрать случайную ветвь из заранее подобранных комбинаций.
                  Собственно, коммерческие решения вроде SpeedTree примерно так и делают.
                0

                Фракталы "родились" из необходимости сгенерировать изображения ландшафтов максимально похожих на настоящие.

              +2
              Жаль что умирая flash с собой и actionscript 3 прихватил…
                0
                Есть же TypeScript
                  +1
                  Там дело не только в языке но и в прекрасном API. Чтобы его спасти, энтузиасты сделали Haxe и OpenFL.org но похоже эти штуки уже не взлетят :(
                    0
                    openfl уже можно юзать и в typescript (https://www.npmjs.com/package/openfl)
                      0
                      Ого, какие они молодцы! Не знал.
                    –2
                    Не знаю… мне вот этот майкрософтовский привкус не понравился совсем… Но это только мне конечно… Жду реальных применений котлина в ВЕБ…
                    0
                    Можно попробовать сконвертировать в html5 с помощью этой тулзы Guepard Flash to HTML5 converter
                    0
                    Я пришел к выводу, что нужно как-то уменьшать плотность веток.

                    Кстати, Леонардо да Винчи в свое время вывел эмпирическое правило:
                    Толщина всех веток дерева на любой его высоте, сложенная вместе, дает толщину ствола

                    В наше время ближе всех к доказательству этого правила приблизился физик Эллой:
                    Для обоснования своей версии ученый создал математическую модель, которая связывает площадь листвы дерева с действующей на излом силой ветра. Дерево в ней описывалось, как закрепленное лишь в одной точке (месте условного ухода ствола под землю), и представляющее собой ветвящуюся фрактальную структуру (т.е. такую, в которой каждый меньший элемент представляет собой более или менее точную копию старшего).

                    Добавив к этой модели давление ветра, Эллой ввел определенный постоянный показатель его предельной величины, после которой ветви начинают ломаться. Исходя из этого, он произвел расчеты, которые показали бы оптимальную толщину разветвляющихся веток, такую, при которой сопротивление силе ветра было бы наилучшим. И что же — он пришел ровно к той же зависимости, причем идеальное значение той же величины лежало между 1,8 и 2,3.

                    Подробнее можно почитать здесь: masterok.livejournal.com/2643089.html
                      0
                      Любопытная тема. Здесь это, очевидно, не соблюдается, хотя из структуры без толщины можно попытаться вывести толщину каждой ветви. Но что-то мне кажется, что в лучшем случае получится баобаб :) Дело в том, что толщина ветки у меня величина переменная и влиявшая только на отображение, а также мне не был известен закон, по которому у дерева растет толщина ветки, помимо толщины ствола, растущей плюс-минус равномерно. Его и реализовал.
                      0
                      Есть некоторая теория, как рисовать деревья и фракталы, придумал биолог Линдемайер
                      gen.lib.rus.ec/search.php?req=Lindenmayer+Systems&lg_topic=libgen&open=0&view=simple&res=25&phrase=1&column=def
                        0
                        Да, любопытные системы. Когда-то интересовался тоже, но не под эту задачу, а просто так.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое