Citizen phil » Flocking. » methods

An Investigation Into Computational Flocking Techniques.Dissertation for final year project for BSc.(Hons) in Applied Computing.

Methods.

skip intro

There is no overall control of the flock. This is a popular misconception about flocking, as is the idea of a leader bird that the others follow. Each tadpoid must be developed so that it behaves autonomously.

Each tadpoid has a set of properties about themselves and reactive behaviours that determine its movement dependent on its environment. The tadpoids are social creatures so seek company when they are unable to see others. The self-determining behaviour of each tadpoid was created such that when a group of tadpoids interact with each other and their environment, a flock emerges. There is no definitive definition of what a flock is. We understand a flock when we see one in action, by watching the movement of the creatures. It is as if the collection of animals being together in motion together with the mesmerising fluidity of interactions and unpredictability makes the whole a 'flock' or 'hive'. As (Kelly, 1994) states,

"A bird on the fly has no overarching concept of the shape of its flock. "Flockness" emerges from creatures completely oblivious of their collective shape, size or alignment. A flocking bird is blind to the grace and cohesiveness of a flock in flight".

Each tadpoids various behaviours are independent, so they can be developed separately, as the tadpoids movement is an effect of all the behaviours operating in parallel. An example of this is a tadpoid heading back to the flock, while avoiding collisions. This allows an incremental path from very simple systems to complex autonomous intelligent systems (Brooks, 1991). At each step of the way it is only necessary to build a small additional behaviour and interface it to an existing, working, complete intelligence.

As the behaviour of the flock emerges from a collection of creatures with no overall control, the task of developing the flock of tadpoids can now be thought of as developing a single tadpoid, then let a collection of them loose and see what happens. Each tadpoid has behaviours added incrementally in the following stages:

  • tadpoid movement - ability to 'wander'
  • actual physical collision
  • avoiding a collision with another tadpoid
  • 'in-flock' behaviour
  • 'out-of-flock' behaviour
  • avoiding a boundary perimeter
  • fleeing from predator

Tadpoid movement

back to intro
skip topic

Each tadpoid determines its own actions. Each tadpoid has a direction it is moving in (an angle theta 0-359 degrees) and a velocity or speed that it is traveling at. In order to simulate the tadpoids on screen and to check on their position, a screen co-ordinate (X, Y) is stored for each tadpoid. Each iteration through the program code allows each tadpoid to self-determine their behaviour and to reposition each tadpoid depending on their new speed and direction. Each tadpoids speed and direction may have been modified dependent on a collision with another tadpoid, avoiding another tadpoid, evading the predator, avoiding the barrier or returning to the flock.

Using trigonometry the new position of the tadpoid can be calculated using the following formula:

Each tadpoid can 'wander' freely while they are not avoiding, evading or returning to the flock. The change in direction is randomly generated first to decide whether to turn right or left and then to decide how much to turn. A maximum range-of-turn is defined that represents the physical ability to turn for each tadpoid. By changing the value of the 'range-of-turn' different types of movement can be observed.

The speed of each tadpoid has a maximum limit and the change of speed is randomly generated, as is the decision on whether to speed up or slow down. Each tadpoid has a store of its last eight screen co-ordinates that is continually updated. These co-ordinates are connected to form a line that represents a trail of where the tadpoid has been. I initially did this as a visual clue to help follow the tadpoid on screen, making it seem a bit more like a living entity. While observing the tadpoids in motion I noticed that the 'tail' stretched the faster the tadpoid travelled and shrunk the slower the tadpoid travelled. This makes sense as the faster each tadpoid travels the greater the distance between each co-ordinate and vice-versa. Quite by accident I had a visual representation of each tadpoid accelerating and decelerating without having to display actual values.

Each tadpoid has a vector that can be displayed to show the direction it is traveling or pointing in. When testing the simulation this proved useful to check the desired direction of the tadpoid against the actual direction.

Tadpoids actual physical collision

back to Tadpoid movement
skip topic

Although each tadpoid is able to detect when a collision with another moving tadpoid is imminent and so will take evasive action. Each tadpoid reacts to the real-world situation it finds itself in.

Therefore there will be times when a collision with another moving tadpoid is unavoidable due to the situation it is in and the reactive abilities of the tadpoid.

Consider the following situations:

  • Two people walking along a corridor towards each other. Normally they would avoid bumping into one another, but on the odd occasion they find themselves doing a 'no after you-shuffle'.
  • You are driving along happily in your car when someone swerves in front of you. Due to the speed traveling at and reaction time a crash is unavoidable.

In the real world collisions do occur. Each tadpoid is modelled as a physically solid object and so an overlap of tadpoids is forbidden.

Although the avoidance works well to a point there are times when the tadpoids actually overlap. The desire to model each tadpoid as if a solid real world object meant an algorithm had to be developed to stop an actual physical overlap.

At first I considered implementing the principle of conservation of momentum. This principle is best demonstrated using snooker balls. A stationary ball is struck by another ball and the momentum is transferred from the moving ball to the stationary one. Although the tadpoids are modelled as physical objects, they are soft animals and so on collision they would dissipate most of the energy. Implementing this algorithm therefore proved inappropriate.

An alternative algorithm is that were two tadpoids to overlap they would be 'pulled' apart from each other, along the shortest distance between them so they no longer overlap.

Each tadpoids displacement being dependent on tadpoids speed, direction and relative position at the moment of impact means that although computationally simple, the algorithm produced very realistic collision interactions.

The diagram below shows two overlapping tadpoids:

The overlapping distance (shown in red) is calculated by doubling the radius and subtracting the distance between the tadpoids along the shortest path. The distance that each tadpoid has to travel is half of this distance. The direction each tadpoid has to travel that distance along is shown in green. That is, the sum of the Y-distances is divided by the sum of the X-distances and the inverse tan of the result of this division is the angle used for the offset.

The formula for forbidding a physical overlap between tadpoids is shown below:

(X1, Y1) represents tadpoidA co-ordinate
and (X2, Y2) represents tadpoidB co-ordinate

distance between tadpoids (x-axis), dX = X1 - X2
distance between tadpoids (y-axis), dY = Y1 - Y2

distance between tadpoids, D = sqrt ((dX2) + (dY2))

distance each tadpoid must move, Dt = 2R - D

angle theta = tan-1 (dY/dX)

The relative positions of the tadpoids are used to 'pull' the tadpoids apart at opposite angles.

if X1 > X2, theta1 = theta
theta2 = theta + 180
else
theta1 = theta + 180
theta2 = theta

To run through an actual example, two tadpoids are overlapping as shown below:

dX = 30 dY = 17 R = 21

D = sqrt ((302) + (172)) = sqrt (1189) = 34.48

distance each tadpoid must move, Dt = (2 * 21) - D = 42 - 34.48 = 7.52

angle theta = tan-1 dY/dX = 17/30 = 0.56 => tan-1 = 29.83 degrees

The relative positions of the tadpoids are used to 'pull' the tadpoids apart at opposite angles.
As X2 > X1 theta1 = 29.83 + 180 = 209.83
theta2 = 29.83

The expected result of this algorithm is that the tadpoids will not overlap. This was proved to be correct, but an unexpected ability was observed.

A fast moving tadpoid collides into a group of tadpoids from behind, and because they do not overlap, the fast moving tadpoid appears to try to 'shove' its way through. The tadpoid appears to be slowed down as it tries to barge its way through. It is quite a realistic effect and can be explained by the 'pulling apart' of the overlapping tadpoids. If the two overlapping tadpoids are traveling in the same direction, they will be 'pulled apart' along the same direction they are traveling in, one forward and one backward. The fast moving tadpoid is pulled backwards and this gives it the appearance of slowing down, in a very physical way. It is not unreasonable to expect a faster moving creature to overtake a slower one, even if it means barging the slower one out of the way first.

Tadpoid collision detection and avoidance strategy

back to Tadpoids actual physical collision
skip topic

The method each tadpoid has for detecting when a collision is imminent was initially implemented in a basic way and then developed for better accuracy and greater realism.

The two main behavioural layers required to avoid collisions are to:

  • detect when a collision is imminent
  • take evasive action to avoid colliding

To detect when a collision is imminent for a tadpoid, it would have to predict if and when a collision is going to happen, based on the current speed and direction of itself and any tadpoids it can see. However, two tadpoids may be heading towards each other but be quite a distance apart, so it is not really necessary to take evasive action unless they were closer. Rather than use a predictive method to test for a collision being imminent, a method could be introduced where a tadpoid is only concerned with those tadpoids within a certain area of itself.

The simplest form of collision detection is to put two boxes around the subject. One box is used to detect when a collision is imminent, and another box (that is the same size as the tadpoid) is used to detect when an actual physical collision has occurred.

The algorithm for checking if two boxes are overlapping is as follows:

if ((tadpoidA.i_x1 + Box width) >= testB.x1) and
if ((tadpoidA.y1 + Box height) >= testB.y1) and
if (tadpoidA.x1 <= (tadpoidB.x1 + Box width)) and
if (tadpoidA.y1 <= (tadpoidB.y1 + Box height)) then
the boxes overlap
else
the boxes do not overlap

Boxes are sufficient for very basic collision detection but it is not a very accurate or realistic method. The distance between two tadpoids when their collision detection areas overlap is not equal for all cases. This means that the movement after detection will not be smooth. It is also unrealistic in that it does not take into account any visual capability from the tadpoid. A 'softer' method of detection is preferred but this simplified method is satisfactory initially. A more accurate method would be to use circles for collision detection. At least in this way the distances between collisions would remain equal. The method to test if two circles are overlapping is two calculate the distance between both tadpoids and if it is less than the sum of both circle radii then they are overlapping each other.

By Pythagorus theorem:

distance (D) = sqrt ((Xdiff * Xdiff) + (Ydiff * Ydiff))

Each tadpoid has a screen co-ordinate (x, y) that represents its centre. The difference in both x-axis and y-axis can be calculated by subtracting one from the other. As they are being squared in the calculation, the order in which they are subtracted does not affect the result.

The test for an overlap:

if (distance < 2 * radius) then
the circles overlap
else
the circles do not overlap

The value of using circles for collision detection is that the distance between the detection of imminent collisions of tadpoids remains equal, unlike using squares.

A strategy to enable each tadpoid to avoid colliding with another tadpoid needs to be explored.

At first I reconsidered the two people in a corridor situation. When you notice that there is someone coming towards you in the distance it is easy to take evasive action. If you only notice when they are quite close there is a kind of etiquette that follows the 'left-hand-drive' rule of motorists, so that if you both move to the left you will avoid each other. This is also incorporated at sea for boats to avoid colliding with each other, but uses the right-hand drive rule. You don't really want boats tacking left-right waiting to see if the other boat is going to change direction again. I tried incorporating this 'turn left to avoid' rule and although the tadpoids did not actually collide with each other that often, the movement was unnatural. Animals do not follow any such rules, and the motion of the tadpoids was too circular as they always turned left to avoid. The ones on the outside of the group would come towards the group and immediately turn off on detecting a collision. I did not want any 'hard-coded' behaviour either and so this method was not incorporated.

The method for avoiding a collision with another tadpoid has to take into account the direction that the tadpoids are traveling in. In (Brooks, 1989) he describes how the robot 'Allen' avoids both static and dynamic obstacles by using sonar distance sensors. Every sonar return represented a repulsive force with an inverse square drop off in strength. The vector sum of the repulsive forces, suitably thresholded, told the robot in which direction it should move to avoid an obstacle.

I used this notion of repulsive forces as inspiration in the development of the tadpoids avoidance strategy.

Each tadpoid has a vector that represents its speed and direction. If this is used to represent a repulsive force upon another tadpoid, itself exerting a repulsive force, these vectors could be used to avoid a collision. I decided to evaluate this further as it is a reactive method that takes into account the speed and direction both the tadpoid when avoiding, and the tadpoid it is trying to avoid.

Two tadpoids heading towards each other at the moment a collision is detected have the sum of their vectors calculated. This vector sum value is then used as the axis about which each tadpoids own current direction is mirrored, so that the tadpoids do not follow the same path, but are repelled. See below:

In this way when two tadpoids are about to collide, they 'swoop' away from each other in a natural way. There is no hard-coded method, it is dependent on each tadpoids speed and direction at the point of imminent collision detected and so is different for all situations.

Consider a fast moving tadpoid heading north and a slow moving tadpoid heading west on a collision path. You would expect the fast moving tadpoid heading north to take little evasive action but the slow tadpoid heading west would pull up and turn at an acute angle to avoid the collision with the fast moving tadpoid. Using the vector sum approach takes this situation into account.

To run through an actual example, two tadpoids are traveling towards each other as shown below:

x = Speed * cosine (theta)
y = Speed * sine (theta)

x1 = 42 * cosine (45) = 29.69
y1 = 42 * sine (45) = 29.69

x2 = 38 * cosine (157) = -34.97
y2 = 38 * sine (157) = 14.84

xsum = x1 + x2 = 29.69 -34.97 = -5.28
ysum = y1 + y2 = 29.69 + 14.84 = 44.53

new vector sum angle = tan-1 (ysum / xsum)

= 44.53 / -5.28 = -8.43 => tan-1 = -83 degrees

This new vector sum angle is used to calculate the new direction for each tadpoid as shown below:
tadpoid A new = (2 * 83) - 45 = 121 degrees

tadpoid B new = (2 * 83) - 157 = 9 degrees

The new tadpoid directions are shown below:

Initially the tadpoids angle was set directly to the new vector sum angle the first time an avoidance collision was detected, just to test out the theory. The tadpoids jerked into the new direction but the theory of using the vector sum appears the correct method to use.

The reason the tadpoids jerked was because the new angle could have been quite a bit of a jump to turn in a single iteration. In order to remove this jerkiness the maximum amount the tadpoid can turn each time was used. This means that the tadpoid turns toward the new angle. However, the vector sum is re-calculated if an imminent collision is still detected.

Turning towards the new angle improves the behaviour of each tadpoid trying to avoid another moving tadpoid, but there remains a fundamental problem by using a circle that surrounds each tadpoid to detect an imminent collision. Consider two tadpoids that are heading towards each other, an imminent collision is detected (1) and each tadpoid start to turn to avoid a collision (2, 3).

At the point that each tadpoid turns so that they are no longer heading for an imminent collision, because their collision detection circles are still overlapping the newly calculated vector sum starts pointing them back towards each other.

The tadpoids end up switching directions between heading towards each other then away and so on until their collision detection circles are no longer overlapping.

Another problem with using surrounding circles for detecting that a collision is imminent is that it does not take into account a tadpoid having any visual capabilities. The direction the tadpoid is traveling in is not taken into account when detecting that a collision is imminent. Two tadpoids may not be heading for a collision but if their collision areas are overlapping then each tadpoid will start to take evasive action regardless. The diagrams below illustrates this:

The method of collision detection needs to incorporate the direction that the tadpoid is traveling in. Some sort of visual representation for each tadpoid is needed.

I decided to keep the circles method of detecting an overlap between two areas, but use three circles lined up and offset on the tadpoids direction vector to create an arc of vision, much like a cars headlight beam at night. In this way each tadpoid will only react to avoid another tadpoid if their 'beams' overlap.

In this method each tadpoid is only interested in taking evasive action if it is either heading towards another tadpoid, or another tadpoid is heading towards it.

The larger circle is named 'collisionMax' and the smaller circle is named 'collisionMin'. The circle that is the same size as the tadpoid is named 'collisionAct'.

The same method is used for testing for overlapping circles but now we have to test for all cases of circles that make up the cone.

There is likely to be more than one type of overlap between two tadpoids so all possible cases of detection between Max, Min and Actual collision detection areas are tested for in order of priority, depending on the urgency of the situation.

For instance, a collision between a maximum and a maximum collision area has a lesser priority than an actual and an actual collision area because the distance between the tadpoids is greater in the maximum-maximum scenario. Therefore the test for an actual-actual will be executed before the maximum-maximum.

At the top of the priority list must be the actual-actual test, as there is no more urgent situation than if two tadpoids have actually bumped into each other.

Using the principle of distance between tadpoids, as well as each tadpoids direction traveling in, it follows that the next urgent scenario is the actual-minimum test and the minimum-actual test. The possible positions of the tadpoids in this situation (N.B. there cannot have been an actual-actual overlap as this is higher in the priority list and so action would be taken on that situation if it were also overlapping) are shown below:

Therefore the full order of priority for collision avoidance is:

tadpoidA__tadpoidB__Speed change
actual----actual
actual----minimum___speed up tadpoid A
minimum---actual____slow down tadpoid A
minimum---maximum___speed up tadpoid A
maximum---minimum___slow down tadpoid A
maximum---actual____slow down tadpoid A
actual----maximum___speed up tadpoid A
minimum---minimum
maximum---maximum

However, using 'cones' that are linked to the direction the tadpoid is traveling in also allows for modifications to the speed for each tadpoid in the collision. For instance in the case of 'maximum - actual', there must have been no collisions between the higher priority cases, so it must be approaching from behind. In this case we would want tadpoid A to slow down as well as changing direction. This helps to make the behaviour more realistic and natural. This slow down / speed up addition to the avoidance behaviour is similar to cars in slow moving traffic. You cannot speed up until the car in front of you has increased its speed to create a gap to accelerate into.

Observing the tadpoids movement I noticed that when two tadpoids are traveling in the same direction and their cones overlap, they stay together for a little while. This following behaviour is actually desired, as the tadpoids should not be scattered away from each other totally, as if afraid of each other. A certain amount of 'togetherness' without constantly physically colliding and while maintaining their individual random movement is the ideal situation, in fact. What causes this following behaviour to happen is a result of the vector sum algorithm. Two tadpoids heading towards each other will start to turn away from each other until the point that they are heading in the same direction, or are parallel to each other. The next time the vector sum is calculated they start turning towards each other, and so on. Each iteration through the program code the vector sum is recalculated if an imminent collision is detected.

The vector sum method of avoiding an imminent collision keeps the birds moving in a really smooth way to avoid each other. It is especially effective when a lone tadpoid heads at a perpendicular angle towards a large group. The individual tadpoid just swoops right along with the group.

An unforeseen advantage of recalculating the vector sum each time is that because of the cone shape used for evading a collision, the tadpoids tend to remain in parallel, which is fine as they are not going to collide anyway while parallel. This 'following' behaviour emerges when the tadpoids are together and enhances the flocking effect.

To form a group or flock of tadpoids requires another layer of behaviour to be added for each tadpoid. The methods to exhibit a 'flocking instinct' are described next.

Flocking

back to Tadpoid collision detection and avoidance strategy
skip topic

Craig Reynolds uses three main steering rules (Kelly, 1994) for his BOIDS software:

  • Separation- steer to avoid crowding local flockmates.
  • Alignment-- steer towards the average heading of local flockmates.
  • Cohesion--- steer to move toward the average position of local flockmates.

When is a tadpoid 'in-flock' and when is it 'out-of-flock'? If there are only two tadpoids left to roam around does this constitute a flock?

I would consider that if two tadpoids are within a perceived distance of each other that they could be considered a flock. The distance they can be apart from each other and still be a flock depends on the type of flocking deemed appropriate for the animal trying to be modelled.

Although I am not modelling any definitive animal as such I do want quite a close huddle, adhering to the 'safety in numbers' principle. When you see gazelles being pursued by a leopard, they are as groups but are constantly changing direction to evade capture in a life or death situation. Flocks of sheep stick together based on a fear of the sheep dog, and tend to stay close to each other making it possible to steer them into a pen. This is the type of movement I am looking for in the tadpoids.

There is no overall control of the flock. The flock emerges from the individual tadpoids desire to be near other tadpoids.

A tadpoid is considered to be 'out-of-flock' if it is a certain distance from another tadpoid. By having a specified area around the tadpoid a test can made to check if there is an overlap with another tadpoids area. If there is an overlap, then both tadpoids can be said to be 'in-flock'.

Initially I started with a circular area centred on each tadpoid. This is shown below. Both tadpoid A and tadpoid B are 'in-flock':

If a tadpoid is 'out-of-flock' it has to have a reactive behaviour that will send it back to an 'in-flock' state. The method used by Craig Reynolds is to direct the object to the centre of the flock. The centre of the flock is the average position of the sum of the tadpoids. This method works well with Reynolds flocking algorithms as the creatures also have a directional goal to head for. In the situation I have with an enclosed area that the tadpoids are free to roam, the implementation of this method proved unsatisfactory.

The main criticism is that it is an unnatural method of keeping the creatures together. When an animal wanders away from a group and wants to return to that group it does not have the capacity to calculate the average position of the other animals. It is a more realistic assumption that it will head for the most densely populated area that it can see. A problem with the centring method is that the average position of the group could be where there are no tadpoids.

This is demonstrated below, the red X indicates the average position of the flock:

I implemented the centring method to test the effectiveness with the tadpoids. Although the method keeps the flock together the movement of the tadpoids looks unnatural. When a tadpoid is 'out-of-flock' it starts heading for a definite spot, usually where there are no tadpoids. If there are a few tadpoids out-of-flock the effect is accentuated. Also with this method if the group is split, as soon as one tadpoid is out of flock it heads straight back to the centre-point of the group. This method is also unappealing for herding the flock by means of a predator as the method that keeps the flock together is an unnatural one. If a predator heads for the middle of a flock you would expect the flock to be split into two or three other smaller groups, not stay together regardless, as if tethered by an invisible rope.

I needed to find an alternative method to the centring method whereby each tadpoid, if it is 'out-of-flock', heads to the most densely populated group it can see.

When I observed the flock I could perceive certain groups of tadpoids. I did this instinctively, but required the implementation of a method that the tadpoids could use to recognise different sized groups. This would allow the tadpoid to make a decision on which group to head towards based on the size and proximity of the groups. This value is the 'pull' of the group. The pull decreases in value the further away it is, and increases with the size of the group. This is similar in theory to Brooks' avoiding obstacle behaviour described earlier, where 'every sonar return represents a repulsive force with an inverse square drop off in strength'. If I could find a way for each tadpoid to recognise a group then I could calculate the distance from the tadpoid to the group and use the inverse square rule to calculate the 'pull' of that particular group. Each tadpoid that is out-of-flock can check for the group with the greatest 'pull' relevant to itself and head in that direction.

In this way a flock should be able to split up and reform when the situation demands. Consider a flock of sheep heading for a stationary obstacle. Rather than the whole flock follows the same path to circumvent the obstacle, you would expect the flock to split with the sheep to the left of the obstacle turning left as an evasive action and the sheep to the right of the obstacle turning right. The diagram below shows this flock movement:

The main benefit of using the 'pull' of a group is that it is a realistic method for the tadpoids to use to return to the flock as each tadpoid then has a choice. The flock it returns to may not be the largest group, as the distance to the group is also taken into consideration. By trying out various function curves generated I was able to make a decision on the one that worked best.

To calculate the 'pull' of a group the following formula is used:

pull = C + size of group/distance2, where C is a constant.

The value of C is such there is has to be a certain amount of tadpoids in a group to give a positive 'pull.'

A graph with varying values of constant C and a range of different sized groups at different distance away was plotted to observe the varying effects.
The graph is shown below, where the value of C = -0.9

The value of the constant is set to this value so that when there are two tadpoids left they will head towards each other.

It is assumed that a tadpoid is capable of counting. It can distinguish whether one group has more tadpoids in it than another group. In order that a tadpoid may count a group of tadpoids, a grid was overlaid on the screen area. This allows a tadpoid to recognise the size of group and judge the distance it would have to travel to reach them.

Each area of the grid calculates the amount of tadpoids within the area and stores as a value. The grid is made up from 13 x 25 squares.

On observing the flock in motion a tadpoid appears to intuitively head to the appropriate group. This enabled a more cohesive naturally moving flock. However, if a group of tadpoids move across a square in, for example, a group of 5, as they cross the border of the square the group changes to a group of 4 in one square and a single tadpoid in the other. Then, it is a group of 3 and 2, 2 and 3, 1 and 4 and finally back to a group of 5 in the other square.

This is shown below:

This problem can be countered by having another grid placed over the existing grid at an offset. It is not a perfect solution to the problem but with the extra grid the amount of time that the group is 'split' is so short and the effect is negligible.

The final grid layout for detecting a group of tadpoids is shown below:

Initially once the square with the greatest 'pull' has been identified, the tadpoid that was 'out-of-flock' headed toward the centre of that square. Rather than make the tadpoid head towards a square, it would be more realistic for the tadpoid to head for another tadpoid.

This is achieved by selecting the nearest tadpoid from within the square with the greatest 'pull', and heading towards it.

The result of using this flocking technique is a particularly fluid, natural-looking movement. The tadpoids group together and move as a flock, but depending on the situation can break away into splinter groups.

The way in which the tadpoids detect whether they are 'in-flock' needs improving to take into account the visual capacity of a tadpoid. This is achieved by still using a circle for detection of another tadpoid but offsetting it on its own directional vector. Also a test is made not for an overlap with another tadpoids circle but whether another tadpoid itself is within the range of the circle, thereby simulating the tadpoid being able to see another tadpoid. This is demonstrated below where tadpoid A is able to 'see' tadpoid B, and so is 'in-flock', but tadpoid B cannot see tadpoid A so it is 'out-of-flock':

This method is a more realistic approach to testing if a tadpoid is 'in-flock', in that this is only true when a tadpoid can actually 'see' that another tadpoid is close enough for safety. When the flock was observed, there was a tendency for the lead tadpoid to peel off from the front of the flock and rejoin it after turning back into the flock. It was doing this as it was at the front and could not see another tadpoid, so turned back towards the group again.

To counter this problem a second circle is used that is positioned central to the tadpoid. This creates an effective elliptical 'in-flock' detection area. This is shown below where both tadpoid A and tadpoid B are both 'in-flock':

By changing the radii of the 'search' circles that are used for testing if a tadpoid is in or out of flock, the type of flocking movement varies. A large radius allows greater spacing between the tadpoids, while still remaining 'in-flock'.

When a large radius is used the tadpoids spend more time freely wandering and tend to be in flocks of twos and threes. When the radius is small, the tadpoids tend to bunch up and spend more time avoiding collisions. They tend to exhibit more cohesiveness as a flock, and have greater numbers in the groups. This is only a general observation and all scenarios are free to exist within all flock circle ranges. This is emergent flock behaviour being observed.

If a tadpoid is 'in-flock' then it is free to wander in its own way unless avoiding a collision. Each tadpoid wanders autonomously as the wandering behaviour is randomly generated for each tadpoid.

Tadpoid boundary avoidance

back to Flocking
skip topic

Initially each tadpoid had the freedom to move off-screen. This meant that if they were moving west and they went off-screen they would reappear, still heading west, from the right-hand side of the screen. This scenario was satisfactory while the initial development of the tadpoids' technique for avoiding another tadpoid was being implemented, but for the purposes of herding a flock of tadpoids, some boundary detection and reactive behaviour is required otherwise the scenario is unrealistic. This is the case for herding creatures on the ground. I chose this method, as the implications for herding air-born creatures would complicate matters unnecessarily.

Ideally the tadpoids should be able to detect the boundary before they actually contact the boundary so that they may take the necessary action to avoid hitting the boundary. However, in the same way that the tadpoids avoid colliding with each other, a tadpoid is only interested in avoiding the wall when it is heading towards the wall and is a certain distance from it. This allows the tadpoid to move parallel to the wall.

When two tadpoids are trying to avoid colliding with each other, a collision is sometimes unavoidable. When a tadpoid is trying to avoid collision with a wall, it will not always succeed. This may be due to the speed of the tadpoid and the vicinity of it with regard to the wall, and its current interaction with the surrounding tadpoids. If a group is heading towards a boundary, although the tadpoids at the front of the flock may take evasive action, the momentum of the group may still drive the front ones into a collision with the wall.

This 'trickle-down' effect is apparent if you consider a crowd of people moving forward, the front ones notice something and try to stop. The people behind the front runners try to stop slightly later, and this reaction trickles through the crowd until eventually they have all stopped. From the time the people at the front first attempt to stop, to the point that they finally stop is much longer than they could have stopped on their own. As the crowd behind them reacts slower, they were bustled along until everyone had stopped.

To allow the tadpoid to detect when a wall is approaching, a vector is projected in the direction the tadpoid is moving. When the end of the vector is over a boundary some action needs to be taken to avoid hitting the wall.

The initial approach I implemented forced the tadpoids to always turn clockwise (right) when a wall was detected. This approach worked in as much as the tadpoids avoided the wall quite well, but this also led to wall following behaviour. To always turn in a direction whatever the situation is also an unnatural reaction. The direction the tadpoid is moving in towards the wall when the wall is first detected relates to the direction that you would expect it to turn in to avoid the wall.

To demonstrate this, the diagram below on the left, the tadpoid is moving towards the wall in a north-westerly direction, detects the wall and turns clockwise (looking from above) to avoid collision with the wall. This is the desired direction to turn in.

In the diagram above on the right, the tadpoid is moving towards the wall in a south-westerly direction, detects the wall and turns anti-clockwise to avoid a collision with the wall. This is not the desired direction to turn in. The desired direction would result in a more likely and realistic avoidance strategy.

To implement the desired boundary detection and avoidance, a co-ordinate (x, y) of the end of a vector is stored that is offset a fixed length in the direction the tadpoid is moving in. If this point overlaps a boundary area then depending on what wall and the tadpoids direction is, the tadpoid will turn right or left to avoid the wall.

The direction for the tadpoid to turn in for all cases of boundary detection is shown bellow.

To identify the wall to check the tadpoid against, four X-axis and four Y-axis are named and positioned as shown below.

If (x, y) is the co-ordinate of the end point of the detection vector, the following table shows the conditions required to satisfy the identification of the wall it is currently overlapping.

The reactive behaviour of each tadpoid as it approached a boundary led it to turn in the desired direction for the walls of ID 5, 6, 7 and 8 (top, bottom, left and right). However, for the walls of ID 1, 2, 3 and 4 (the corners), the tadpoids were diverted into the wall, along the axis on which direction to turn is decided.

This is shown in the diagram below, for the top-left corner:

Tadpoid (position 1) approaches the wall, on a collision course, at an angle of 220 degrees. On detecting the wall, the tadpoid (position 2) begins turning right, as its direction is greater than 180 degrees (see look-up table for the turning decision). The tadpoid (position 3) remains turning right until its angle is now greater than the decision axis (yellow line). The tadpoid (position 4) turns left until its angle is less than the decision axis, before turning right again (position 5). The forward motion of the tadpoid is maintained while turning, and the tadpoid is driven along the decision axis.

Although the boundary avoidance was a reactive behaviour it did not take into account the current behaviour or urge of the tadpoid, i.e. "I am turning right", but only the momentary direction.

A method was introduced for the corners, whereby the current behaviour and momentum was considered. In this way if a tadpoid heads into a corner it will continue to follow the direction it is turning in. The introduction of this additional decision process produced a more natural and fluid movement for the tadpoids boundary avoidance and eliminated the problem of tadpoids being driven into a corner.

If the tadpoid is physically overlapping the boundary then the same method that is described for overlapping tadpoids is used. This forces the tadpoids to never overlap the boundary, which is the case for physical properties.

Tadpoid Pen avoidance

back to Tadpoid boundary avoidance
skip topic

To give the predator a purpose, that is to herd the tadpoids into a pen, an area needs defining. I decided that the pen should have an opening that acts as an entrance to it. As the pen is to be modelled as a physical object, the tadpoids will have to take evasive action to avoid colliding with the pen. The pen is a solid stationary object, and so a tadpoid should react to detecting the pen using the same method as if a wall had been detected. That is, the tadpoids direction it is traveling in is taken into account when deciding what direction it needs to turn in, to avoid hitting the wall of the pen.

To identify the wall of a pen to check the tadpoid against, six X-axis and four Y-axis are named and positioned as shown below. The wall ID's shown in the pen use the same condition to determine it as shown in the table for the wall boundary ID's.

The direction to turn is dependent on the angle of the tadpoids direction it is heading in and the ID of the pen wall. The same table as the wall boundary table is used.

Fleeing from predator

back to Tadpoid boundary avoidance
skip topic

In the animal kingdom the hunted have evolved a variety of strategies to evade capture from the hunters. If your straight-line speed is slower than your predator but you have greater mobility, you have a chance to evade capture by zigzagging away. The 'safety-in-numbers' approach is an alternative method. By grouping together, each animal is at less of a risk of being 'picked off'. Cattle and sheep adopt this approach.

The method of obstacle avoidance used by Brooks, where 'every sonar return represents a repulsive force with an inverse square drop off in strength', can be implemented as a method of herding the tadpoids. The predator can be represented as a repulsive force on each tadpoid. I have called this force the 'influence' of the predator.

The closer the predator is to each tadpoid the greater the influence it exerts on each tadpoid. By implementing the influence alone, the tadpoids are dispersed at the angle that they are to the predator, see the diagram below:

This dispersion of the tadpoids is only part of the solution as the direction the predator is traveling in needs to be taken into consideration. This is because a predator traveling away from a tadpoid should have little or no influence, whereas a predator moving closely towards a tadpoid should have a relatively high influence.

A stationary predator is of less concern to a tadpoid than a fast moving one. Therefore, the area used for detecting whether a tadpoid is subject to the predators influence was made proportional to the speed the predator was traveling at, and offset along the predators direction of travel vector. A smaller circular area is used as a minimum area that exerts a greater influence on each tadpoid as a more extreme measure, and is positioned central to the tadpoid. The diagrams below show the predators two herding areas and an example of a fast and slow moving tadpoid:

To avoid the predator's influence overriding all other tadpoids behaviours, the vector that the influence represents needs to be summed with the tadpoids own 'pre-influence' direction vector. This is applied whether or not the tadpoid is 'in-flock', so that a tadpoid will still try to return to the flock for safety, if the pull is great enough.

For example, in the diagram below the tadpoid has a direction that it wants to head in to return to the flock. There is a predator separating it from the flock. The desired direction for the tadpoid would be to detour around the predator.

The algorithm each tadpoid uses to calculate its new direction due to the predators influence is shown below, where a predator is shown intercepting a tadpoid:

where,

Vi is the influence vector upon the tadpoid
Vt is the tadpoids vector pre-influence
Vnew is the tadpoids vector post-influence

Vi is calculated using the tadpoid's distance from and angle to the predator.
Distance to predator, Dp = sqrt ((Xp+Xt)2 + (Yp+Yt)2 )

theta1 = tan-1 (dy / dx)

influence upon tadpoid, Vt = 1600 / Dp2 at an angle theta1

Vnew = Vi + Vt

Vt = Speed at angle Theta2

Vt = Xvt + Yvt Xvt = Speed * cosine (theta2)
Yvt = Speed * sine (theta2)

Xvi = Influence * cosine (theta1)
Yvi = Influence * sine (theta1)

Vnew = sqrt ( ((Xvt + Xvi) 2 ) + ((Yvt + Yvi) 2 )

Theta new = tan-1 (Ysum / Xsum) = tan-1 (Yvt + Yvi / Xvt + Xvi)

The method described was implemented and the tadpoids took evasive action from the predator.

Below is the graph showing the predators influence for the minimum herding area:

Rate of Turn

back to Fleeing from predator
skip topic

Initially, when a tadpoid was either turning away from a predator or turning towards a flock of tadpoids, the amount the tadpoid turns in one program iteration was fixed. The amount, or rate-of-turn is set to the maximum range-or-turn. Having a fixed rate-of-turn means that the turning circle of a tadpoid is fixed, and therefore unnatural. Depending on the situation a tadpoid is in it may be desired or maybe even necessary for a tadpoid to turn suddenly. For instance, a tadpoid may have to turn suddenly to evade a fast moving predator.

A new algorithm was developed whereby the amount to turn is calculated, dependent on the amount to turn in total in order to be heading in the desired direction.

Through experimentation a minimum and maximum rate-of-change were decided. Initial values for the range of degrees possible to turn per iteration were set from 2 to 16 degrees. A function line was plotted for a total possible amount of required to deviate from its current heading, between 2 and 180 degrees (the minimum and maximum amount a tadpoid would possibly need to turn).

Following the formula for a straight line function, with the above conditions:

Y = m X + c
Therefore,
(i) 2 = m 2 + c
(ii) 16 = m180 + c
To calculate m,
(i)* 8 gives
16 = m 16 + 8c
so,
16m + 8c = 180 m + c
8c - c = 180m - 16m
7c = 164m
c = (164 / 7) m

2m - 2 = 180 m - 16
14 = 178 m

Therefore,
m = 14 / 178 = 0.078

we know that c = (164/7) m

Therefore,
c = ( 164 / 7 ) * 0.078 = 1.843

Finally,

rate-of-turn = 0.078 * degrees + 1.843

where degrees is the desire amount of degrees required to turn in total.

When this ability to turn as sharply as necessary was implemented, the change in the tadpoids movement was observed to be more natural than previously. This is due to the differing turning circles that are now implemented. The situation is like trying to turn to avoid something while not slowing down.

The tadpoids reaction to the predator had a greater degree of urgency and the overall effect was a more realistic fleeing behaviour.

The graph for the rate-of-turn with a range between 2 and 16 is shown below:

Change of Speed

intro
back to Rate of Turn

Initially the speed a tadpoid travelled at when freely wandering was randomly generated to decide whether to speed up or slow down.

If a tadpoid were 'out-of-flock' it would accelerate until its maximum speed was reached and then maintain this speed until 'in-flock'. This fixed speed led to the 'out-of-flock' tadpoids moving at the same maximum speed, and gave them a uniform behaviour. A tadpoid returning to a flock would also speed into the group rather ungracefully. To give the tadpoids a more realistic change of speed, an element of probability was introduced.

The distance a returning tadpoid is to the flock it is heading toward is used to give the probability of accelerating or decelerating. The table used is shown below:

The result of implementing this algorithm is that a fast approaching tadpoid has an increased probability of decelerating as it gets closer to the flock, enabling the tadpoid to swoop in and join the flock in a natural, elegant way. It also removed the uniformity of speed among returning tadpoids.

top

Results