Friam

10,000-boids flocking program

Classic

List

Threaded

5 messages Options

Jochen Fromm

10,000-boids flocking program

You certainly know Craig Reynolds' boids at
http://www.red3d.com/cwr/boids/

But how does flocking with 100,000, or 1,000,000
individuals look like ? Keith Wiley has written
a program named "Mega Flies" to investigate
this question. He has found evidence for
MEGA group behavior :-)
http://www.unm.edu/~keithw/artificialLife/megaFlies.html

There is also a movie here:
http://www.unm.edu/~keithw/artificialLife/gnatCloud.html

Russell Standish

10,000-boids flocking program

Interesting. Large agent-based simulations are challenging - I noticed
that Keith Wiley was proud of achieving a simulation with a few
thousand agents.

With my jellyfish simulation (a model distributed as part nof the
EcoLab package) I have run a simulation with a million jellyfish, and
it has run very effectively. My best result was 90 seconds wallclock
time for an hour of simulation time (about 600 timesteps) for a 2D simulation.
There were a few tricks:

1) Space was divided into a Cartesian grid.
2) Each grid cell held a list of agents residing in the cell
3) Cells were big enough so that agents only needed to check the list
of egents within the current cell, and the neighbouring cells to
determine possible interactions. This limits the number of agents that
need to be checked (so computational complexity = O(N^{1.2}) rather
than O(N^2) or something like that).
4) The magic of EcoLab was used to distribute the whole simulation
across 100 processors of a Beowulf cluster. Being compiled C++ code
means the simulation is very efficient indeed.

Right now I'm working an a 3D version of the code. It doesn't exhibit
as good a scaling for some reason, but I'm quite sure I'll solve the
problem shortly.

Cheers

On Thu, Aug 12, 2004 at 08:33:06PM +0200, Jochen Fromm wrote:

> You certainly know Craig Reynolds' boids at
> http://www.red3d.com/cwr/boids/
>
> But how does flocking with 100,000, or 1,000,000
> individuals look like ? Keith Wiley has written
> a program named "Mega Flies" to investigate
> this question. He has found evidence for
> MEGA group behavior :-)
> http://www.unm.edu/~keithw/artificialLife/megaFlies.html
>
> There is also a movie here:
> http://www.unm.edu/~keithw/artificialLife/gnatCloud.html
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org

--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.

----------------------------------------------------------------------------
A/Prof Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967, 8308 3119 (mobile)
UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")
Australia [hidden email]
Room 2075, Red Centre http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : /pipermail/friam_redfish.com/attachments/20040813/f7ba33b7/attachment.bin

Stephen Guerin

10,000-boids flocking program

Craig Reynolds has a decent description of a binning approach at:
http://www.red3d.com/cwr/papers/2000/pip.pdf

Search toward the end of the paper on "bin-lattice spatial subdivision".
Craig claims a 16 times speed improvement with a system of 1000 boids.

I suspect this is close to what Russell is doing.

We used this binning approach in SwarmEffects:
http://www.redfish.com/projects/SwarmEffects

-Steve

____________________________________________________
http://www.redfish.com [hidden email]
624 Agua Fria Street office: (505)995-0206
Santa Fe, NM 87501 mobile: (505)577-5828

> -----Original Message-----
> From: Russell Standish [mailto:[hidden email]]
> Sent: Thursday, August 12, 2004 5:24 PM
> To: The Friday Morning Applied Complexity Coffee Group
> Cc: [hidden email]
> Subject: Re: [FRIAM] 10,000-boids flocking program
>
>
> Interesting. Large agent-based simulations are challenging - I noticed
> that Keith Wiley was proud of achieving a simulation with a few
> thousand agents.
>
> With my jellyfish simulation (a model distributed as part nof the
> EcoLab package) I have run a simulation with a million jellyfish, and
> it has run very effectively. My best result was 90 seconds wallclock
> time for an hour of simulation time (about 600 timesteps) for a
> 2D simulation.
> There were a few tricks:
>
> 1) Space was divided into a Cartesian grid.
> 2) Each grid cell held a list of agents residing in the cell
> 3) Cells were big enough so that agents only needed to check the list
> of egents within the current cell, and the neighbouring cells to
> determine possible interactions. This limits the number of agents that
> need to be checked (so computational complexity = O(N^{1.2}) rather
> than O(N^2) or something like that).
> 4) The magic of EcoLab was used to distribute the whole simulation
> across 100 processors of a Beowulf cluster. Being compiled C++ code
> means the simulation is very efficient indeed.
>
> Right now I'm working an a 3D version of the code. It doesn't exhibit
> as good a scaling for some reason, but I'm quite sure I'll solve the
> problem shortly.
>
> Cheers
>
> On Thu, Aug 12, 2004 at 08:33:06PM +0200, Jochen Fromm wrote:
> > You certainly know Craig Reynolds' boids at
> > http://www.red3d.com/cwr/boids/
> >
> > But how does flocking with 100,000, or 1,000,000
> > individuals look like ? Keith Wiley has written
> > a program named "Mega Flies" to investigate
> > this question. He has found evidence for
> > MEGA group behavior :-)
> > http://www.unm.edu/~keithw/artificialLife/megaFlies.html
> >
> > There is also a movie here:
> > http://www.unm.edu/~keithw/artificialLife/gnatCloud.html
> >
> >
> > ============================================================
> > FRIAM Applied Complexity Group listserv
> > Meets Fridays 9AM @ Jane's Cafe
> > Lecture schedule, archives, unsubscribe, etc.:
> > http://www.friam.org
>
> --
> *PS: A number of people ask me about the attachment to my email, which
> is of type "application/pgp-signature". Don't worry, it is not a
> virus. It is an electronic signature, that may be used to verify this
> email came from me if you have PGP or GPG installed. Otherwise, you
> may safely ignore this attachment.
>
> ------------------------------------------------------------------
> ----------
> A/Prof Russell Standish Director
> High Performance Computing Support Unit, Phone 9385 6967, 8308
> 3119 (mobile)
> UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")
> Australia [hidden email]
> Room 2075, Red Centre

http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------

Russell Standish

10,000-boids flocking program

Yep, sounds like it to me! Great minds think alike, n'est-ce pas? :)

If anyone is really interested in a million boid simulation, it
wouldn't take long to knock up something in EcoLab.

Cheers

On Thu, Aug 12, 2004 at 10:59:58PM -0600, Stephen Guerin wrote:

> Craig Reynolds has a decent description of a binning approach at:
> http://www.red3d.com/cwr/papers/2000/pip.pdf
>
> Search toward the end of the paper on "bin-lattice spatial subdivision".
> Craig claims a 16 times speed improvement with a system of 1000 boids.
>
> I suspect this is close to what Russell is doing.
>
> We used this binning approach in SwarmEffects:
> http://www.redfish.com/projects/SwarmEffects
>
> -Steve
>
> ____________________________________________________
> http://www.redfish.com [hidden email]
> 624 Agua Fria Street office: (505)995-0206
> Santa Fe, NM 87501 mobile: (505)577-5828
>
> > -----Original Message-----
> > From: Russell Standish [mailto:[hidden email]]
> > Sent: Thursday, August 12, 2004 5:24 PM
> > To: The Friday Morning Applied Complexity Coffee Group
> > Cc: [hidden email]
> > Subject: Re: [FRIAM] 10,000-boids flocking program
> >
> >
> > Interesting. Large agent-based simulations are challenging - I noticed
> > that Keith Wiley was proud of achieving a simulation with a few
> > thousand agents.
> >
> > With my jellyfish simulation (a model distributed as part nof the
> > EcoLab package) I have run a simulation with a million jellyfish, and
> > it has run very effectively. My best result was 90 seconds wallclock
> > time for an hour of simulation time (about 600 timesteps) for a
> > 2D simulation.
> > There were a few tricks:
> >
> > 1) Space was divided into a Cartesian grid.
> > 2) Each grid cell held a list of agents residing in the cell
> > 3) Cells were big enough so that agents only needed to check the list
> > of egents within the current cell, and the neighbouring cells to
> > determine possible interactions. This limits the number of agents that
> > need to be checked (so computational complexity = O(N^{1.2}) rather
> > than O(N^2) or something like that).
> > 4) The magic of EcoLab was used to distribute the whole simulation
> > across 100 processors of a Beowulf cluster. Being compiled C++ code
> > means the simulation is very efficient indeed.
> >
> > Right now I'm working an a 3D version of the code. It doesn't exhibit
> > as good a scaling for some reason, but I'm quite sure I'll solve the
> > problem shortly.
> >
> > Cheers
> >
> > On Thu, Aug 12, 2004 at 08:33:06PM +0200, Jochen Fromm wrote:
> > > You certainly know Craig Reynolds' boids at
> > > http://www.red3d.com/cwr/boids/
> > >
> > > But how does flocking with 100,000, or 1,000,000
> > > individuals look like ? Keith Wiley has written
> > > a program named "Mega Flies" to investigate
> > > this question. He has found evidence for
> > > MEGA group behavior :-)
> > > http://www.unm.edu/~keithw/artificialLife/megaFlies.html
> > >
> > > There is also a movie here:
> > > http://www.unm.edu/~keithw/artificialLife/gnatCloud.html
> > >
> > >
> > > ============================================================
> > > FRIAM Applied Complexity Group listserv
> > > Meets Fridays 9AM @ Jane's Cafe
> > > Lecture schedule, archives, unsubscribe, etc.:
> > > http://www.friam.org
> >
> > --
> > *PS: A number of people ask me about the attachment to my email, which
> > is of type "application/pgp-signature". Don't worry, it is not a
> > virus. It is an electronic signature, that may be used to verify this
> > email came from me if you have PGP or GPG installed. Otherwise, you
> > may safely ignore this attachment.
> >
> > ------------------------------------------------------------------
> > ----------
> > A/Prof Russell Standish Director
> > High Performance Computing Support Unit, Phone 9385 6967, 8308
> > 3119 (mobile)
> > UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")
> > Australia [hidden email]
> > Room 2075, Red Centre
> http://parallel.hpc.unsw.edu.au/rks
> International prefix +612, Interstate prefix 02
> ----------------------------------------------------------------------------
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org

Roger Critchlow-2

10,000-boids flocking program

In reply to this post by Stephen Guerin

Stephen Guerin wrote:

Binning has been used to speed up molecular dynamics computations of
non-bonded interactions between atoms for so long that it wasn't even
remarked as a feature when I first saw it more than a decade ago.

-- rec --