Вот в этом комменте я похвастался, что в своё время написал программу, создающую рендер «пристойно выглядящего» леса в двести строк кода. К сожалению, реальность оказалась немного большей по размеру — раскопанные исходники содержат примерно 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, там ещё не было таких векторов, или я предпочел сделать свой велосипед. Текстура под ветку с листьями рисовалась так: вначале делался один лист, затем определялось, будет ли у веток центральный лист, этим определялась длина куска ветки, к которой крепились листья, затем по вычисленной ширине листа они крепились (рисовались на текстуре) под углом к ветке. Форма листа задавалась как искаженный круг с несколькими опорными точками, смещенными относительно круга радиусом пол-листа, и отдельно задавалась длина черенка, всё это рисовалось на текстуре листика в черно-белом виде и сохранялось на будущее. (Точнее, текстур «ветка с листьями» было две, одна для концов, т.е. веток, у которых из «конца» ничего не растет, но они с листьями, на ней был нарисован лист в конце ветки, вторая для «середин» без концевого листа.)

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


(Как ни странно, 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-файл учетверенного по сравнению с окном размера.