Blue Theme Orange Theme Green Theme Red Theme
 
Home | Forums | Videos | Photos | Downloads | Blogs | Interviews | Jobs | Beginners | Training
 | Consulting  
Submit an Article Submit a Blog 
 Login Close
User Id:
Password:
 
Forgot Password
Forgot Username
Why Register
 Jump to
Skip Navigation Links
TechnologyExpand Technology
WebsiteExpand Website
World Class ASP.NET Hosting – Click Here for 3 Months Free/NO Setup Fee!
 Resources  
Close
 Our Network  
Close
Search :       Advanced Search »
Home » Algorithms & AI » Simulating a Swarm Algorithm in C#

Simulating a Swarm Algorithm in C#

Rather than reinvent the wheel, I took this code and translated it into C# to demonstrate the swarm behavior in a Windows Form using GDI+. The algorithm is exactly the same and also a fairly simple one.

Author Rank:
Total page views :  28209
Total downloads :  782
   Print Read/Post comments Post a comment  Similar Articles  
   Email to a friend  Bookmark  Author's other articles  
Download Files:
SwarmSim.zip
 
Become a Sponsor

I just finished reading Michael Crichton's Science Fiction/Horror book Prey and I admit I could not put the book down. The book combines the concepts of the Swarm Algorithm with nanotechnology to create a very frightening concept( I won't go into detail, because I don't want to spoil it for the reader). What is so fascinating about some of Michael Crichton's books is that he mixes and explains real state of the art technology with his storyline. He also presents possible inventions and breakthroughs in the current technology to fill the implausible gaps of the story, the mark of a great science fiction writer. After reading the book, I decided to go out on the web and see what has been done with modeling swarms in the computer world. (There is also an impressive bibliography of papers and texts in the back of Prey pointing to references on artificial life, genetic algorithms, and intelligent agents).

Figure 1 - The Swarm Algorithm Coming to Life

In my short-lived research I found an article that embeds a java app simulating swarm behavior written by Alex Vulliamy and Jeff Cragg. Rather than reinvent the wheel, I took this code and translated it into C# to demonstrate the swarm behavior in a Windows Form using GDI+. The algorithm is exactly the same and also a fairly simple one.  In order to understand the algorithm let's first talk a little bit about the social behavior of birds in a flock.

I think we can all agree that birds are not exactly the brightest of animals (hence the term "bird-brain"), so how do they know how to fly so organized in a flock? (This question was pointed out in Crichton's book by the way).  The way each individual bird determines how he will fly is simply by seeing where its neighbors are in the flock and adjusting its velocity so as not to collide with the bird in front of it. If you put this series of simple behavior together for all birds, the combined result is birds flying in a nice formation. Another words, its not like these birds got together and said, "Hey let's form a big V, like the cheerleaders for Villanova". No, they simply rely on their neighbor to determine their behavior.

So how does this all pan out as a mathematical algorithm? Well, let's say you are a bee. You would then obey  the following rules (according to this particular program): 

  1. Accelerate towards your two closest neighbors.
  2. If you get too close, repel your neighbor.
  3. Don't ever exceed your maximum speed (after all you are a bee, not a rocket ship).
  4. If you hit a wall, reverse your direction.
  5. Try to have a tendency to accelerate towards the center of the enclosed space
  6. Check the proximity of your neighbors' neighbors. If they are closer, follow them.
  7. Every once in a while randomly choose some other set of neighbors to follow.

That's all there is too using your limited intelligence as a bee. Just follow a few simple rules and the combined result produces an interesting effect shown in figure 2.

Figure 2 - Simulated bee swarm following each other around

The "bees" seem to follow each other around in a group in a 3D mass not unlike a real bee swarm. (Its hard to tell much from the picture because you can't really see the motion, so you'll just have to run the simulation ;-)

Below is the UML design of our simple Swarm Simulation. It consists of only two classes: the Form and Swarm3D.  The Form displays the simulation, and the Swarm3D class contains the Simulation thread, simulation rules, and the code to draw the bees inside the form:

Figure 3 - UML Design of Simulation Program reversed using WithClass 2000

The architecture goes something like this: The Form constructs an instance of the Swarm3D class and calls start to kick off the swarm simulation thread. Each time the simulation needs to update the screen with new swarm positions, it invalidates the form so it will repaint itself. When the form repaints, it calls the Draw method of the Swarm3D class.

The swarm algorithm is implemented in the run routine of the Swarm3D class shown in Listing 1 below. The listing follows all of the rules we have listed above. Most of the rules (1-5), such as follow your neighbor, avoid colliding with your neighbor, don't exceed maximum speed, and bounce off the walls are handled in the processfly method. doneighbors checks the proximity of the neighbors' neighbors and applies rule # 6. Rule #7 is handled by the randomize method in order to pick new neighbors every once in a while. 

Listing 1 - run method simulating the swarm:

public void run()
{
int c=0;
// continue with the simulation as long as the thread is running
while (Thread.CurrentThread ==runner)
{
for (int i=0;i<NF;i++)
{
// determine if there are closer neighbors (rule #6)
doneighbours(i);
// alter the velocity vectors of the bees according to the algorithm rules (Rules #1-5)
processfly(i);
}
// increment a counter to track the number of frames
c++;
// every once in a while, change the neighbors around to new random neighbors (rule # 7)
if (rand(20)==0) randomize();
try
{
// Delay the new positioning so the simulation is not too fast for the eye
Thread.Sleep(delay);
}
catch (Exception e)
{
}
// Force the form to redraw the new positions of the bee
TheForm.Invalidate();
}
}

The most interesting method as it applies to our swarm algorithm is the processfly method which invokes a majority of the rules (1-5) shown in Listing 2. In this method, we compute a 3D Velocity vector for the bee based on the swarm rules.  Then we add the velocity vector to the 3D position vector of the bee to determine its new position in the swarm. Note that we need to check each of the x,y, and z directions vectors against the rules of the algorithm.

Listing 2 - processfly method applying rules 1 - 4

public void processfly(int tick)
{
// rev determines whether the neighbour attracts or repels, ACC is the acceleration amount
// lpx & lpy are the last positions of the bee for drawing purposes.
// REVDIST is the minimum distance squared that the flies can get to without repelling
// tick is the bee number being processed. flyvx&y are the velocities in x and y directions
// ACCTOMID is the acceleration towards the middle to attempt to keep the flies in the
// middle of the display.
lpx[tick]=flyx[tick];
lpy[tick]=flyy[tick];
lpz[tick]=flyz[tick];
int rev=1;
// check the distance between the bee and its neighbors
// use the Acceleration constant and relationship to neighbors to
// compute the velocity of the bee.
// reduce the velocity vector if the bee is getting too close to the neighbor
// if the neighbor is closer than the minimum distance allowed, reverse the direction of the bee
if (dist(tick,flyn[tick,0])<REVDIST)
rev=-1;
// Accelerate towards your neighbor (rule #1)
// if you get too close, repel your neighbor (rule #2)
if (flyx[tick]<flyx[flyn[tick,0]])
flyvx[tick]+=ACC*rev;
else
flyvx[tick]-=ACC*rev;
if (flyy[tick]<flyy[flyn[tick,0]])
flyvy[tick]+=ACC*rev;
else
flyvy[tick]-=ACC*rev;
if (flyz[tick]<flyz[flyn[tick,0]])
flyvz[tick]+=ACC*rev;
else
flyvz[tick]-=ACC*rev;
rev=1;
if (dist(tick,flyn[tick,1])<REVDIST)
rev=-1;
if (flyx[tick]<flyx[flyn[tick,1]])
flyvx[tick]+=ACC*rev;
else
flyvx[tick]-=ACC*rev;
if (flyy[tick]<flyy[flyn[tick,1]])
flyvy[tick]+=ACC*rev;
else
flyvy[tick]-=ACC*rev;
if (flyz[tick]<flyz[flyn[tick,1]])
flyvz[tick]+=ACC*rev;
else
flyvz[tick]-=ACC*rev;
// make sure that the bee's velocity never exceeds the maximum speed (Rule #3)
if (flyvx[tick]>MAXSPEED) flyvx[tick]=MAXSPEED;
if (flyvx[tick]<-MAXSPEED) flyvx[tick]=-MAXSPEED;
if (flyvy[tick]>MAXSPEED) flyvy[tick]=MAXSPEED;
if (flyvy[tick]<-MAXSPEED) flyvy[tick]=-MAXSPEED;
if (flyvz[tick]>MAXSPEED) flyvz[tick]=MAXSPEED;
if (flyvz[tick]<-MAXSPEED) flyvz[tick]=-MAXSPEED;
// make sure the bee's position never exceeds the boundaries of the cube (Rule #4)
if (flyx[tick]<0) flyvx[tick]=BOUNCESPEED;
if (flyx[tick]>WIDTH*100) flyvx[tick]=-BOUNCESPEED;
if (flyy[tick]<0) flyvy[tick]=BOUNCESPEED;
if (flyy[tick]>HEIGHT*100) flyvy[tick]=-BOUNCESPEED;
if (flyz[tick]<0) flyvz[tick]=BOUNCESPEED;
if (flyz[tick]>DEPTH*100) flyvz[tick]=-BOUNCESPEED;
// make sure the bees tend to travel towards the middle of the cube (Rule #5)
if (flyx[tick]<WIDTH*50) flyvx[tick]+=ACCTOMID;
if (flyx[tick]>WIDTH*50) flyvx[tick]-=ACCTOMID;
if (flyy[tick]<HEIGHT*50) flyvy[tick]+=ACCTOMID;
if (flyy[tick]>HEIGHT*50) flyvy[tick]-=ACCTOMID;
if (flyz[tick]<DEPTH*50) flyvz[tick]+=ACCTOMID;
if (flyz[tick]>DEPTH*50) flyvz[tick]-=ACCTOMID;
// compute the new bee position based on the computed velocity
flyx[tick]+=flyvx[tick];
flyy[tick]+=flyvy[tick];
flyz[tick]+=flyvz[tick];
}

Conclusion

The swarm algorithm may seem like a novelty, but it is actually useful for optimization problems in physics, economics, and chemistry. You can add a genetic algorithm to the swarming algorithm to produce emergent behaviors or generate "new rules" to follow in order to achieve a particular goal. Just make sure the goal doesn't exceed its boundary's as they did in Michael Crichton's unfolding tale. 

References

Michael Crichton's Prey on Amazon
Simulating Social Behavior
Alex Vulliamy's Home Page
Ariel Dolan's ALife Experiments

AI Depot
 


Login to add your contents and source code to this article
 About the author
 
Mike Gold
Michael Gold is President of Microgold Software Inc., makers of the WithClass UML Tool. His company is a Microsoft VBA Partner and Borland Partner. Mike is a Microsoft MVP and founding member of C# Corner. He has a BSEE and MEng EE from Cornell University and has consulted for Chase Manhattan Bank, JP Morgan, Merrill Lynch, and Charles Schwab. Currently he is a senior developer at Finisar Corp. He has been involved in several .NET book projects, and is currently working on a book for using .NET with embedded systems. He can be reached at mike@c-sharpcorner.com
Looking for C# Consulting?
C# Consulting is founded in 2002 by the founders of C# Corner. Unlike a traditional consulting company, our consultants are well-known experts in .NET and many of them are MVPs, authors, and trainers. We specialize in Microsoft .NET development and utilize Agile Development and Extreme Programming practices to provide fast pace quick turnaround results. Our software development model is a mix of Agile Development, traditional SDLC, and Waterfall models.
Click here to learn more about C# Consulting.
 
Introducing MaxV - one click. infinite control. Hyper-V Hosting from MaximumASP.
Finally – a virtual platform that delivers next-generation Windows Server 2008 Hyper-V virtualization technology from a managed hosting partner you can truly depend on. Visit www.maximumasp.com/max for a FREE 30 day trial. Hurry offer ends soon. Climb aboard the MaxV platform and take advantage of High Availability, Intelligent Monitoring, Recurrent Backups, and Scalability – with no hassle or hidden fees. As a managed hosting partner focused solely on Microsoft technologies since 2000, MaximumASP is uniquely qualified to provide the superior support that our business is built on. Unparalleled expertise with Microsoft technologies lead to working directly with Microsoft as first to offer IIS 7 and SQL 2008 betas in a hosted environment; partnering in the Go Live Program for Hyper-V; and product co-launches built on WS 2008 with Hyper-V technology.
Dynamic PDF
ceTE software specializes in components for dynamic PDF generation and manipulation. The DynamicPDF™ product line allows you to dynamically generate PDF documents, merge PDF documents and new content to existing PDF documents from within your applications.
Go.NET
Build custom interactive diagrams, network, workflow editors, flowcharts, or software design tools. Includes many predefined kinds of nodes, links, and basic shapes. Supports layers, scrolling, zooming, selection, drag-and-drop, clipboard, in-place editing, tooltips, grids, printing, overview window, palette. 100% implemented in C# as a managed .NET Control. Document/View/Tool architecture with many properties&events. Optional automatic layout.
Dundas Software
Dundas Chart for .NET is the most advanced .NET charting package available today.  With an extremely complete feature set, elegant architecture and easy implementation, Dundas Chart can quickly add advanced Charting functionality to enhance and transform ASP.NET and Windows Forms applications.  Whether you are implementing charting into internal projects, or building applications for clients, Dundas Chart offers advanced technology and advanced results to get the most out of data.
Clickatell's SMS Gateway
Clickatell's Developer Solutions allow you to SMS enable any website or application via a range of API's. Learn More about our API connections.
Free access to .NET Memory Management video
Everything you need to know about Garbage Collection, Temporary Objects, Fragmentation, Finalization and common causes of memory leaks in .NET. Watch the video here.
Microsoft Visual Studio 2010 Professional
Microsoft Visual Studio 2010 Professional will launch on April 12, but you can beat the rush and secure your copy today by pre-ordering at the affordable estimated retail price of $549 (US). Pre-order now.
Nevron Chart for .NET 2010.1 Now Available
The leading .NET charting control now features PDF, Flash and Silverlight export, visualization of large datasets and more. Deliver true charting functionality to your BI, Scorecard, Presentation or Scientific apps. Download evaluation now.
Developer-Ready ASP.NET 2.0 Web Hosting with 3 MONTHS FREE
Now supporting .NET 3.0 Framework with Windows Workflow Foundation, Windows Communication Foundation (WCF), Windows Presentation Foundation (WPF), windows CardSpace (WCS)! Providing more flexibility for Developers with Web Services Support and a User/Permission Manger. Also supporting MS SQL 2005/2000 with Real-Time Backups, FREE Automated Attach .MDF Tool, FREE SQL Restore and Shrink SQL DB Tools, and SQL
 
   Print Read/Post comments Post a comment  Similar Articles  
   Email to a friend  Bookmark  Author's other articles  
Download Files:
SwarmSim.zip
 
 Post a Feedback, Comment, or Question about this article
Subject:  
Comment:  
Become a Sponsor
 Comments
question by jenifer On January 23, 2007

the download file is not opening.. Is there any way to open it.

mail me soon plz

jenifer

Reply | Email | Delete | Modify | 
thank's mike by bouslah On August 28, 2007
excellent work,i hope for u a good luck for your lifejob
Reply | Email | Delete | Modify | 
Overflow error by Jonathon On November 18, 2007
Every time i try to run your program,using visual studio 05, the program hits an overflow error on the fillpolygon. I thought I would let you know about it.
Reply | Email | Delete | Modify | 
Download by Matthew On October 8, 2008
This looks really intersting. I'd love to see it work, but the download file returns an error. Anyway I can get the zip file?
Reply | Email | Delete | Modify | 
error by priya On November 17, 2008
I tried to run the java code. but i am getting the following code. Note: flies3d.java uses or overrides a deprecated API. Note: Recompile with -Xlint:deprecation for details. please help. Thanking you in advance Priya
Reply | Email | Delete | Modify | 
creating the flyer shapes in openGL by john On July 2, 2009
I'm currently trying to do the same simulation in openGL and I'm having a hard time trying to figure out how to create those shapes in openGL. Any advice?
Reply | Email | Delete | Modify | 

 Hosted by MaximumASP  |  Found a broken link?  |  Contact Us  |  Terms & conditions  |  Privacy Policy  |  Site Map  |  Suggest an Idea  |  Media Kit
Current Version: 5.2009.6.2
 © 2010  contents copyright of their authors. Rest everything copyright Mindcracker. All rights reserved.