Particles System в моделировании толпы

многие идеи, которые приходят ко мне, уже кто-то реализовал или скоро реализует (цитата с просторов интернета)

В далеком 2001 году меня, любителя стратегий реального времени, поразила игра “Казаки”. Поразила ГИГАНТСКИМИ толпами, бродящими по карте. Поразило то, что эти толпы довольно резво бегали на тогдашних маломощных компьютерах. Но в то время я работал на скорой помощи, был далек от программирования, потому восхищением дело это тогда и ограничилось.

Уже в наше время захотелось сделать игрушку с примерно подобным количеством подвижных юнитов — чтоб “эпик” просто зашкаливал(!). И чтоб эти юниты не просто двигались, а двигались внешне(!) осмысленно. И чтоб (главное), все это великолепие работало на слабеньких мобильных платформах.

Встал вопрос — как? С графикой вопросов нет — на любой современной платформе есть разные по-произодительности графические библиотеки, которые займутся выводом толпы на экраны. Главный вопрос — как программно реализовать осмысленное (ну или бессмысленное) нечто, что игроком воспринималось бы однозначно — это подчиняющаяся каким-то стимулам толпа, а не просто набор мельтешащих фигурок.

Уверен, существует куча рекомендаций, литературы, и даже реализаций. Но меня интересовало что-то “простенькое”, что можно применить в незатейливой игрушке для “мобилы” и собрать “на коленке”. Т.е. дешево и сердито, а главное — понятно для меня(!).

Год назад прослушал в записи замечательную лекцию с КРИ 2008 Михаила Блаженова (это АУДИО — печатной версии не нашел) “Специфика конвейерной разработки мобильных игр: планирование, портирование, тестирование”. Важный вывод из статьи для меня — при написании логики приложения с большим количеством данных, надо использовать подход, ориентированный на данные (data-oriented paradigm). (Тадааам!).

Суть, родившейся после прослушивания, идеи была в следущем.

1. Все (ВСЕ) разнообразные “побудительные мотивы индивида” в игре надо описывать системой векторов (приказ, страх, ненависть, лень, глухота, инерция…). В течении одного игрового цикла (или каждого десятого, не суть) проводятся различные манипуляции с этими векторами. Итогом всех манипуляций будет сумма векторов, которая в простейшем случае определит направление движения персонажа (одного из сотен, а то и тысяч).
2. Каждый “индивид” должен обладать одинаковым набором векторов — ради стандартизации вычислений. Тогда определением поведения отдельного “индивида” в толпе может заниматься маленький многократно повторяющийся кусочек кода — конвейер. Прелесть конвейера в том, что ему абсолютно все равно “кого” он обрабатывает — толстяка, катящееся колесо, труп… Ему главное — набор “мотивов”. Благодаря этому мы на выходе получаем не просто толпу, а разнообразную(!) толпу.

Теперь надо было писать сам механизм… Но какого черта?! Ведь если тебя посетила идея, то велика вероятность, что она уже посетила еще сто-миллион человек до тебя. А может кто-то из этого миллиона даже подходящий инструмент создал? Библиотеку какую-нибудь?

Такой инструмент нашелся — система частиц (particles system). Я выбрал FLINT.

1. системе частиц идеально подходит для прототипирования
2. расчеты внутри систмы частиц строятся на законах классической механики — т.е. в наше время уже существует несчислимое множество разнообразных алгоритмов, которые можно адаптировать под собственные программистские нужды
3. к системе частиц можно прикрутить любой рендер из сторонней библиотеки
4. данный варинт системы частиц написан автором Entity System фреймворка Ash by Richard Lord (это отдельная песня).

Кратко опишу базовые инструменты конкретной реализации системы частиц:

1. эмиттер (Emitter2D) — собственно экземпляр класса, который отвечает за генерацию частиц, согласно заданным параметрам, и дальнейшее “сопровождение”
2. Emitter2D.addInitializer( initializer ) — метод, при помощи которого в эмиттер добавлются “свойства”, которые будут присвоены частицам при их генерации.
3. Emitter2D.addAction( action ) — при помощи этого метода в эмиттер добавляются правила управления частицами, которые будут применяться к частицам во время их жизни.

Конечно, в мечтах, мне кажется, что с помощью “векторов мотиваций” можно даже сделать РПГ с кучей “независимых”, со своим мнением персонажей в отряде, но начинать надо с простого. Я выбрал жанр Tower Defence. Только в игре хочу увидеть не жиденький ручеек “танчиков”, а сонмы вражин(!), чтоб их можно было, как щебенку, раскидывать взрывами, крошить, плющить, рассеивать…

Уфф… конец предисловия. Но мне кажется, оно важно.

Реализация идеи

Начнем с простейшей задачи:

1. генерировать маршрут любой сложности
2. персонажи следуют по заданному маршруту, при этом
   
   • не “налезают” друг на друга
   • “смотрят” по направлению движения

1. генерировать маршрут любой сложности

Т.е. — путь состоит из точек (waypoints). Частицы должны двигаться последовательно от точки к точке. К сожалению, соответствующиего action в библиотеке не оказалось. Но я подсмотрел реализацию в другой библиотеке (которая, кстати писалась на основании выбранной мной) — stardust-particle-engine.

Единствоенное, в найденной реализации мне не нравится, что в точках пути частицы сбиваются в кучу, а не следуют “широким фронтом” вдоль всего маршрута. Поэтому я чуть модифицировал класс под свои нужды

Wayline — имя класса, неуклюжее “наследование” от оригинального Waypoint
суть класса — хранить перпендикуляр к касательной пути. При генерации частицы, с помощью action FollowWaylines, сохраняют данные о своем относительном положении на перпендикуляре. И далее во время движения “стараются” этого положения придерживаться — таким образом они не сбиваются в кучу в узлах пути — они распределяются по-перпендикуляру к касательной в этой точке (кстати, за это отвечает экземпляр класса Line, из замечательнейше-полезной библиотеки для кривых Безье).

package waylines.waypoints { 	import flash.geom.Point; 	import flash.geom.Line; 	 	public class Wayline extends Waypoint 	{ 		public var rotation:Number; 		public var line:Line; 		 		public function Wayline(x : Number = 0, y : Number = 0, segmentLength : Number = 40, rotation:Number=0, strength : Number = 1, attenuationPower : Number = 0, epsilon : Number = 1) 		{ 			super(x, y, segmentLength/2, strength, attenuationPower, epsilon); 			 			this.rotation = rotation; 			this.line = new Line(new Point(x - (radius * Math.cos(rotation)), y - (radius * Math.sin(rotation))), new Point(x + (radius * Math.cos(rotation)), y+(radius * Math.sin(rotation)))); 		} 	} } 

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

protected function setupWaylines():void 		{ 			_waylines = []; 			 			var w:Number = stage.stageWidth; 			var h:Number = stage.stageHeight; 			/* 			 * 1. это я на глаз накидал координаты, просто доли умножая на ширину и высоту экрана 			 * 2. первую и последнюю точку расположил за пределами экрана, чтоб частицы появлялись из-за края экрана, а не из пустоты  			 */   			//var points:Array = [new Point(-9,h*.6), new Point(w*.3,h*.3), new Point(w*.5,h*.25), new Point(w*.6,h*.45), new Point(w*.7,h*.7), new Point(w*.8, h*.75), new Point(w*.9, h*.6), new Point(w*1.3, h*.5)]; 			var points:Array = [new Point(-9,h*.4), new Point(w*.3,h*.4), new Point(w*.5,h*.1), new Point(w*.8,h*.1), new Point(w*.8,h*.9), new Point(w*.5, h*.9), new Point(w*.3, h*.8), new Point(-40, h*.8)]; 			/* 			 * проблемы: 			 * 1. экземпляры Wayline должны быть выставлены перпендикулярно к касательной пути 			 * 2. количества первоначальных точек маловато для обеспечения плавности пути 			 * 3. лень вручную выставлять все необходимые параметры 			 * решение: 			 * взять нужный кусочек из полезнейшей библиотеки http://silin.su/#AS3, где 			 * 1. FitLine - класс, который "сглаживает" ломаные кривые 			 * 2. Path - класс, сохраняющий последовательность кривых Безье, которыми можно оперировать, как единым целым. Например - найти точку на пути. 			 * 3. "нарезать" получившийся сглаженный путь на нужное число точек 			 */ 			var fitline:FitLine = new FitLine(points); 			var path:Path = new Path(fitline.fitPoints); 			/* 			 * ВАЖНО! - величине шага желательно должно быть больше скорости движния частицы - это ради упрощения расчетов.  			 * Иначе, частица на скорости может "проскочить" следующую точку на пути, и "захочет" вернуться, или не впишется в резкий поворот.  			 * В общем - будет выглядеть так, будто частица слетает с рельсов, или круги наматывает... Можете поэкспериментировать 			 */  			var step:Number = path.length / 40; 			/* 			 * сила притяжения точки на пути - помните, система частиц работает "на классической механике"? 			 * т.е. внутри системы частиц, частицу последовательно ускоряет к следующему узлу пути - как в адронном коллайдере 			 */ 			var strength:Number = 100; 			// расставляем ноды на местности 			for(var i:int=0; i<path.length; i+=step) 			{ 				// можно поиграться с рандомными размерами узлов на пути 				var segmentLength:int = 60;//*Math.random()+10; 				var pathpoint:PathPoint = path.getPathPoint(i); 				var wayline:Wayline = new Wayline(pathpoint.x, pathpoint.y, segmentLength, pathpoint.rotation-Math.PI/2, strength); 				_waylines.push(wayline); 			} 		} 

2. персонажи следуют заданному маршруту, при этом

• не “налезают” друг на друга
• “смотрят” по направлению движения

этот пункт реализуется при помощи настроек самой системы частиц. Т.е. — настроим эмиттер

protected function setupEmitter():void 		{ 			// --- создаем экземпляр класса и задаем параметры, которые которые будут применяться к частицам при их генерации ------------- 			var emitter:Emitter2D = new Emitter2D(); 			// это счетчик - генерирует определенное количество частиц в секунду 				emitter.counter = new Steady(60); 			// берем начало пути 				var wayline:Wayline = _waylines[0]; 			// позиционируем зону генерации эмиттера LineZone таким образом, чтоб она совпадала с линией "внутри" Wayline 			 				emitter.addInitializer( new Position( new LineZone( new Point(wayline.x - wayline.radius*Math.cos(wayline.rotation), wayline.y - wayline.radius*Math.sin(wayline.rotation)), new Point(wayline.x + wayline.radius*Math.cos(wayline.rotation), wayline.y + wayline.radius*Math.sin(wayline.rotation)) ) ) ); 			// сообщаем, какую картинку использовать рендеру при отрисовке частицы 				//emitter.addInitializer( new ImageClass( ArrowBitmap, [4] ) ); 				emitter.addInitializer( new ImageClass( Arrow, [4] ) ); 				 			// --- добавляем actions, которые в совокупности будут определять поведение частиц --------------------------------------------- 			// определяем зону вне которой частицы будут автоматически(!) уничтожаться. Т.е. области организации движения составляют своеобразную матрёшку 			// 1. снаружи (больше всех) - мёртвая зона - вне прямоугольника частицы автоматически уничтожаются 			// 2. посредине - узлы маршрута частиц (вне экрана устройства концы, при этом внутри "прямоугольника жизни") 			// 3. внутри матрёшки - экран устройства - с одной стороны частицы входят, с другой - выходят 			// на самом деле этот action можно не добавлять, потому что уничтожение частиц в конце пути осуществляет "главный" action FollowWaylines  				emitter.addAction( new DeathZone( new RectangleZone( -30, -30, stage.stageWidth+60, stage.stageHeight + 60 ), true ) ); 			// new Move() - дает возможность обновлять позицию частицы каждый фрейм. Т.е. - чтоб частица двигалась, к эмиттеру надо прицепить этот action 				emitter.addAction( new Move() ); 			// это, чтоб персонажи были повернуты по направлению к движению  				emitter.addAction( new RotateToDirection() ); 			// определяет МИНИМАЛЬНУЮ дистанцию между частицами 				emitter.addAction( new MinimumDistance( 7, 600 ) );			 			// пришлось написать специальный action для ограничения скорости (есть и "родной" SpeedLimit, но он меня не устраивает - об этом в следующей статье расскажу) 				emitter.addAction( new ActionResistance(.4)); 			// наш "доморощенный" action, который непосредственно и контролирует движение частицы по заданному маршруту 				emitter.addAction( new FollowWaylines(_waylines) ); 		   	 		   	// создаем рендерер 		   	//var	renderer:BitmapRenderer = new BitmapRenderer(new Rectangle(0, 0, stage.stageWidth, stage.stageHeight)); 		   	var	renderer:DisplayObjectRenderer = new DisplayObjectRenderer(); 		   	// цепляем его на сцену 		   		addChild( renderer ); 		   	// передаем в качестве параметра настроенный эмиттер 		   		renderer.addEmitter( emitter ); 			// командуем старт 				emitterWaylines = emitter;			 				emitterWaylines.start(); 		} 

Итак, в результате поиска необходимых для нашей задачи библиотек и минимальнейшего “допиливания”, получился вполне приемлемый результат при хорошем соотношении времязатраты-эффективность (и даже, не побоюсь этого слова, эффектность!). И это только прототип, запущенный в дебаг-плеере.
При релизе можно (даже нужно) оптимизировать код:

1. объединить некоторые actions (например DeathZone и FollowWaylines, а также Move и RotateToDirection и ActionResistance). Т.е. — оптимизируя один action, мы таким образом уменьшаем число итераций минимум на число частиц в эмиттере.
2. на прямых участках пути убрать промежуточные точки маршрута

Код доступен на google code.

PS: В следующей части хочу усложнить задачу. Добавлю:

1. взрывы (с разбрасыванием тел)
2. медленные персонажи (это будут крупные стрЕлки)
3. огибание в пути медленных стрелок быстрыми

PPS: В еще какой-нибудь статье портирую код на яваскрипт (чуть опыта поднаберусь, чтоб времени не убивать много)