Particles System in crowd modeling

many of the ideas that come to me have already been implemented or will be implemented soon (quoted from the Internet)

Back in 2001, I, a fan of real-time strategy, was struck by the game “Cossacks” . I was amazed by the GIANT crowds wandering around the map. It was striking that these crowds were running briskly on the low-power computers of that time. But at that time I was working in an ambulance, I was far from programming, because this was the only thing that delighted me then.

Already in our time, I wanted to make a toy with approximately the same number of mobile units - so that the “epic” just rolls over (!). And so that these units do not just move, but move outwardly (!) Meaningfully. And so (most importantly), all this magnificence worked on weak mobile platforms.
')
There was a question - how? There are no questions with graphics - on any modern platform there are different graphic libraries of performance that will be engaged in displaying the crowd on the screens. The main question is how to programmatically implement a meaningful (well, or meaningless) something that the player would perceive unambiguously - this is a crowd submitting to some stimuli, and not just a set of flickering figures.

I am sure there are a lot of recommendations, literature, and even implementations. But I was interested in something “unpretentious” that can be used in a simple toy for “mobile” and assembled “on the knee”. Those. cheap and cheerful, and most importantly - understandable to me (!).


A year ago I listened to a remarkable lecture with KRI 2008 by Mikhail Blazhenov (this is AUDIO - I did not find the printed version) “Specificity of conveyor development of mobile games: planning, porting, testing” . An important conclusion from the article is for me - when writing application logic with a large amount of data, one should use a data-oriented paradigm approach. (Tadaaam!).

The essence, born after listening, the idea was as follows.

1. All (ALL) various “incentives of an individual” in the game should be described by a system of vectors (order, fear, hatred, laziness, deafness, inertia ...). During one game cycle (or every tenth, not the essence) various manipulations with these vectors are carried out. The result of all the manipulations will be the sum of the vectors, which in the simplest case will determine the direction of movement of the character (one of hundreds, and even thousands).
2. Each “individual” should have the same set of vectors - for the sake of standardizing calculations. Then the definition of the behavior of an individual “individual” in a crowd can be dealt with by a small repeatedly repeated piece of code — the pipeline. The beauty of the conveyor is that he doesn’t care at all whom he handles - the fat man, the rolling wheel, the corpse ... The main thing for him is the set of “motives”. Due to this, at the exit we get not just a crowd, but a diverse (!) Crowd.

Now it was necessary to write the mechanism itself ... But what the hell ?! After all, if an idea came to you, then it is likely that she has already visited another hundred-million people before you. And maybe one of this million even created a suitable tool? Any library?

Such a tool was found - a system of particles (particles system) . I chose FLINT .

1. particle system is ideal for prototyping
2. the calculations inside the particle system are built on the laws of classical mechanics - i.e. Nowadays, there are already countless different algorithms that can be adapted to your own programmer needs.
3. Any render from a third-party library can be screwed to the particle system.
4. This particle system variation was written by the Entity System author Ash framework by Richard Lord (this is a separate song).

I will briefly describe the basic tools of a specific implementation of a particle system:

1. emitter ( Emitter2D ) - the actual instance of the class, which is responsible for the generation of particles, according to the specified parameters, and further "support"
2. Emitter2D.addInitializer (initializer) is the method by which “properties” are added to the emitter, which will be assigned to particles when they are generated.
3. Emitter2D.addAction (action) - using this method, particle control rules are added to the emitter, which will be applied to the particles during their lifetime.

Of course, in dreams, it seems to me that with the help of “motivation vectors” you can even make an RPG with a bunch of “independent”, with your own opinion of the characters in the squad, but you need to start with a simple one. I chose the Tower Defense genre. Only in the game I want to see not a thin stream of “tanchiki”, but the hosts of the enemy (!), So that they can be scattered like explosives, chop, crush, dissipate ...

Whew ... the end of the preface. But it seems to me, it is important.

Implementation of the idea

Let's start with the simplest task:

1. generate a route of any complexity
2. characters follow a given route, while
   
   • do not "fit" on each other
   • “Look” in the direction of travel
   
   

1. generate a route of any complexity

Those. - the way consists of points ( waypoints ). The particles must move sequentially from point to point. Unfortunately, there was no corresponding action in the library. But I spied the implementation in another library (which, by the way, was written on the basis of my choice) - stardust-particle-engine .



Unified, in the found implementation, I don’t like that at the points of the path the particles are knocked together and not followed by a “wide front” along the entire route. Therefore, I slightly modified the class to fit my needs.

Wayline - class name, awkward “inheritance” from the original Waypoint
the essence of the class is to keep perpendicular to the tangent path. When generating a particle, using the action, FollowWaylines saves data about its relative position on the perpendicular. And then, during the movement, they “try” to adhere to this position — in this way, they do not pile up at the nodes of the path — they are distributed perpendicular to the tangent at this point (by the way, an instance of the Line class is responsible for this; Bezier ).

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)))); } } } 

then generate a path consisting of node points

 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. characters follow a given route, while

• do not "fit" on each other
• “Look” in the direction of travel

This item is implemented using the settings of the particle system itself. Those. - set up the emitter

 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(); } 

So, as a result of the search for the libraries necessary for our task and the minimum “dopilivaniya”, it turned out quite acceptable result with a good ratio of time-expenditure-efficiency (and even, I’m not afraid of this word, showiness!). And this is just a prototype running in the debug player.
With the release, you can (even need) to optimize the code:

1. combine some actions (for example, DeathZone and FollowWaylines , as well as Move and RotateToDirection and ActionResistance ). Those. - optimizing one action , we thus reduce the number of iterations by at least the number of particles in the emitter.
2. on straight sections of the route remove intermediate waypoints

The code is available on google code .

PS: In the next part I want to complicate the task. I will add:

1. explosions (with body scattering)
2. slow characters (these will be big shots)
3. rounding in the way of slow arrows fast

PPS: In another article I port the code to javascript (I’ll have a little more experience to not have to kill a lot of time)