VB:Tutorials:Flocking

From GDWiki

Have you ever wished that you could get a group of objects to move as though they had a collective mind, like a school of fish or a herd of buffalo? You've probably realized that it's a flocking problem! I'll show you the flocking solution to the whole flocking thing!

There are a number of different ways to go about this, but in general, these are the rules that a flock must follow to exhibit convincing behaviour:

• Objects must attempt to move towards the center of the group
• Objects must maintain some minimum distance between themselves and others
• Objects must move at a speed relative to the speed of the flock

This makes sense intuitively; think about a herd of zebra in Africa. The safest zebra are those in the middle of the herd, but they must maintain a practical distance between each other, and also match speeds (or be left behind). Zebra on the outside want to get inside (so they're as far away from lions as possible!), but won't run over other zebra to do it.

The way you implement these rules is really not important, but I'll show you how I've done it anyway, as an example:

Little Bo-Peep has lost her sheep!

We'll call our objects "sheep" (because I think sheep are funny). Now, lets randomize the locations of the starting positions of the sheep, as we can see has been done in the image above.

Private Type SHEEPTYPE
    sngX As Single
    sngY As Single
    sngXSpeed As Single
    sngYSpeed As Single
End Type
Dim mudtSheep() As SHEEPTYPE
 
Const NUM_SHEEP = 19
Const MIN_SEPERATION = 15
 
Dim i As Integer
Dim j As Integer
Dim blnSeperation As Boolean
 
    ReDim mudtSheep(NUM_SHEEP - 1)
 
    Randomize
    For i = 0 To UBound(mudtSheep)
        blnSeperation = False
        Do While Not (blnSeperation)
            mudtSheep(i).sngX = Rnd() * frmFlock.ScaleWidth
            mudtSheep(i).sngY = Rnd() * frmFlock.ScaleHeight
            blnSeperation = True
            For j = 0 To i - 1
                If CalcDist(i, j) <= MIN_SEPERATION Then
                    blnSeperation = False
                    Exit For
                End If
            Next j
        Loop
    Next i

A lot of code just to disperse some sheep! First, we set up the UDT (User Defined Type) for our sheep data, and then create a dynamic array and size it according to the value of the NUM_SHEEP constant. Easy, right? Then we step through each sheep with a For loop and assign it a random location. It is imperative that the sheep don't overlap however, so we need ANOTHER For loop to check this! The process continues within a While loop until success is achieved.

Sheep of a feather flock together?

Ooooh, now they're all in a clump! How did that happen?

Private Function CalcDist(intIndex1 As Integer, intIndex2 As Integer) As Single
 
    CalcDist = Sqr((mudtSheep(intIndex1).sngX - mudtSheep(intIndex2).sngX) ^ 2 + _
               (mudtSheep(intIndex1).sngY - mudtSheep(intIndex2).sngY) ^ 2)
 
End Function

This handy little function returns the distance between any two sheep (identified by their index value within the array). With it, we can determine our closest neighbour (using loops, similar to those used in the randomization step) and check his speed. Remember, we need to keep every sheep's speed similar to that of the flock!

Const MAX_NOISE = 250
 
Dim sngXSum As Single
Dim sngYSum As Single
Dim sngXAvg As Single
Dim sngYAvg As Single
 
    For j = 0 To UBound(mudtSheep)
        sngXSum = sngXSum + mudtSheep(j).sngX
        sngYSum = sngYSum + mudtSheep(j).sngY
    Next j
 
    sngXAvg = (sngXSum / NUM_SHEEP) + (Rnd() * MAX_NOISE) - (MAX_NOISE / 2)
    sngYAvg = (sngYSum / NUM_SHEEP) + (Rnd() * MAX_NOISE) - (MAX_NOISE / 2)

This code will find the center of the flock by averaging the X and Y values of all of the sheep. It also adds some noise, so that the sheep appear to jostle around. The reason for the subtraction of (MAX_NOISE / 2) is so that the noise can be positive or negative. Essentially, we're adding a random value between -125 and 125.

All that remains is to move each sheep towards this "center" according to their X and Y speed values. Also, if a movement will cause a sheep to infringe on another's MIN_SEPERATION, then you should abort the movement. Have a look at this sample source code if you'd like to be a shepherd for a day.