Swarming BIODs (or not)

I just write arcade games as a hobby. In my new game I wanted to include a visual effect of swarming in the alien creatures. I’ve seen BIOD swarming algorithms which look perfect but I can’t see how to translate them into the data structures I use elsewhere in the code. The published algorithm speaks about a general heading for the local flock mates but I just have an X & Y delta for each alien rather than a heading as such. Also, they talk about local flock mates but if I have say 50 aliens, would that mean I’d have to work out which alien is closest and then which aliens are then all together. This seems like a lot of processing for something that’s not central to the game. I just can’t quite see the best way to approach the problem.

The rules for swarming BIODs are :

  • separation: steer to avoid crowding local flockmates
  • alignment: steer towards the average heading of local flockmates
  • cohesion: steer to move towards the average position (center of mass) of local flockmates

Thanks for any suggestions

Mike

Very great stuff. i really appreicate this!
Vex 4

Mykayla
Unfortunately it appears all your posts are just spam to link to your site.
Bit sad really.
Mike

Hey Mike,

By heading they probably mean a normalized directional vector. The x and y deltas you have are more like a direction and a scale, it tells you which direction and how far in that direction the alien is going to move. To get the heading you want to take the scale out of your deltas by normalizing them so that they just represent a direction. That is a linear algebra term that just mean so make the scale of the vector equal to 1. So you can use any vector2d class and put your delta x and y into it and then call the normalize function on the vector2d.

For finding out the neighbor aliens I would recommend starting out by just calculating the distance to each other alien and picking the closest ones. Then when you know the algorithm is working for a handful of boids you can put in optimizations like using a fixed size grid and only checking the distances to boids that are in the same grid box or in on the the 8 surrounding grid boxes.

I remember watching this video several months ago on implementing simple flocking. You may find it helpful as he walks through implementing boids in JavaScript and then discusses some potential optimizations/extensions at the end.

mhjuuHl6qHM

Like ewg suggested, a fixed sized grid would be a useful optimization. I also think that a Quadtree would be beneficial to learn about and use as they are useful in many situations.

Thanks for the ideas and video. There’s quite a lot to understand there. I’ll have to put my thinking cap on.

Excellent post. Please keep up the great work. You may check our website also Visit: Transformice