There is many ways in which you can improve the algorithm. I have seen flocks of 10,000 birds being rendered real-time on a laptop by Hanno Hildenbrandt, theoretical biology Utrecht.
http://www.rug.nl/biologie/onderzoek/onderzoekgroepen/theoreticalbiology/peoplePages/hannoPage Also, Craig Reynolds himself has been working on speeding up crowd behaviour (was in contact with him a while ago about Hanno's model). http://www.research.scea.com/pscrowd/ I think the basic theory of speeding up the whole simulation is to just let the birds react to nearby birds. The biological reasoning behind it is that the bird has to pay attention to gather the information, and will only do so for a fixed number of birds, favoring those birds that are nearby. I think there is a whole field in game engine design devoted to that, but the basic idea is to split up your sky into boxes, in such a way that you can quickly gather which birds are nearby one particular bird, and thus which birds influence this single birth. I think there's also some fun you can have thinking about how to deal with two birds that are nearby: it would be foolish to drop all the 'birds nearby bird A' information, if you know that bird A and bird B are close by, and you still need to calculate bird B. The one drawback is that these kind of algorithm optimizations might make your program look less neat :). Have fun! On Jan 28, 5:00 am, Eric Lavigne <lavigne.e...@gmail.com> wrote: > > The technique was first described by Craig Reynolds in the 1980s and has > > since then made it's way into many contemporary games. The algorithm is > > interesting in that it's fairly computationally intensive. Each boid's > > motion is determined by calculating it's distance from every other boid. If > > the other boids are within a threshold, 3 different vector values (cohesion, > > alignment, separation) are calculated based on the location and velocites > > from all other boids that are within the said neighborhood. There's a lot > > of interation, 67500 (150x150x3) iterations for 150 boids per update/render > > loop. > > For the purpose of game development, I think it is a mistake to perform > these calculations for every pair of birds. If you had an error of 1% in > each of the three characteristics (cohesion, alignment, separation) would > that still be good enough? Would this be an acceptable loss if you got a > factor of 100 performance improvement? > > In "Objective CAML for Scientists" [1] pages 92-101 Jon Harrop demonstrates > a rapid numerical solution for a multibody gravitation problem, which looks > similar to the problem you are solving. He refers to the method as Fast > Multipole Method [2,3]. It trades a little accuracy for a big performance > gain. Oh, and his implementation in OCaml uses only immutable data > structures. No guarantees, but I have a feeling that this would completely > eliminate your performance issues. > > [1]http://www.ffconsultancy.com/products/ocaml_for_scientists/ > [2] W. Rankin and J. Board, "A portable distributed implementation of the > parallel multipole tree algorithm," in IEEE Symposium on High Performance > Distributed Computing, (Los Alamitos), pp. 17-22, IEEE Computer Society > Press, 1995. > [3]http://en.wikipedia.org/wiki/Fast_Multipole_Method > > Sorry for the long post, definitely interested in how I could close the gap. > > > Of course I'm totally ready to accept the fact that this particular > > algorithm is best suited for having parts written in Java, but I really > > don't like Java and I love Clojure ;) > > I think Clojure can handle this. Good luck :-D > > -- > Education is what survives when what has been learned has been forgotten. > > - B. F. Skinner --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
