Group Movement / Flocking Behavior

Here you can try it out. Left mouse button moves the group of red squares. Right button moves the blue ones. Here's the code.

In the pathfinding tutorial I mentioned that we'd have to have a separate algorithm for making characters pathfind around each other. I wanted to eventually be able to multithread the pathfinding which meant that you couldn't have have one square directly tell the other what to do. So for example when two of them collide the first one you did collision detection for couldn't tell the other "You go this way and I'll go that way".
The thought experiment that lead to this solution was how to avoid the collision of two squares moving directly towards each other:

fig 1
fig 1 The red and blue squares are perfectly aligned and moving towards each other. How should they decide on a direction to get out of each other's way?

Since they're mirror images of each other I thought introducing chirality, handedness or the concept of left and right, would be a good way to create some kind of asymmetry and therefore a way to make them distinguishable from each other so that they did not both perform the same movement. If they had a left and right you could tell them "always go left when colliding", which would allow them to avoid each other in the fig 1 example:

fig 2
fig 2 Both squares move to the left to solve the collision.

The question then becomes what does "move left" mean? If we have it to mean left of the current movement this would cause a problem if they bumped into each other from behind since then "left" for both squares would mean the same direction.

fig 3
fig 3 The blue square is bumping into the red one from behind. If they both move to the left of the direction they're going then that solves nothing since the red one will still be in the way of the blue one.

To solve this you could make them move to the left of the collision normal. The collision normal being a vector pointing straight back from the square we're colliding with.

fig 4
fig 4 The collision normal for the blue square is the red arrow pointing downward and for the red square it's the blue arrow pointing upwards. Now if they move to the left of their collision normals the red square would move out of the way of the blue one.

However there is a simple way to get the same result that's related to how we presented the walls of a square in the collision tutorial. In it the walls of a square can be seen as vectors moving clockwise around the square:

fig 5
fig 5

We can then just tell each square to follow the vector of the wall it's collided with:

fig 6
fig 6 Think of this as fig 1 but we've added a bit of space between the squares for clarity. The blue square will be colliding with the left wall of the red square. This wall is represented by the blue arrow which if followed would make the blue square move upwards. The red square will be colliding with the right wall of the blue square, represented by the red arrow making the red square move downwards.

The basic idea is then very simple:
1. Get the unit vector of the wall we're colliding with. We use the unit vector since the length of the wall shouldn't matter only it's direction.
2. Start accelerating our square in that direction.
We'll modify the get_walls() function to also return the unit vector for the wall in addition to the wall's regular vector. Then during collision detection we'll add a piece of code that sums all the units vectors for the walls we've collided with into a single vector which we then follow. The code for this is:
1. Check if we've collided.
2. If so add the unit vector of the wall we've collided with to a variable called avoidVector.
3. Since we might be adding a bunch of vectors into this avoidVector there's a chance of them cancelling each other out and avoidVector becoming zero. It's better that the character move in any direction when there's been a collision so he has a chance of solving it. We therefore check if avoidVector has become zero and if so re-initialize it with the current wall we've collided with.

1.	if( collision ) {
2.		avoidVector[ X_COORD ] += walls[ wallnbr ][ X_VEC_NORM ];
2.		avoidVector[ Y_COORD ] += walls[ wallnbr ][ Y_VEC_NORM ];

3.		if( fabs( avoidVector[ X_COORD ] ) < .001 && fabs( avoidVector[ Y_COORD ] ) < .001 ) {
3.			avoidVector[ X_COORD ] = walls[ wallnbr ][ X_VEC_NORM ];
3.			avoidVector[ Y_COORD ] = walls[ wallnbr ][ Y_VEC_NORM ];
		}
	}

avoidVector is the vector we'll be following to solve all collisions we've been involved in. What I mean by "following" is that we'll set the square's acceleration to equal avoidVector. walls[ wallnbr ] is the wall we've collided with and X_VEC_NORM and Y_VEC_NORM are the components of that wall's unit vector.

After we've added together a bunch of unit vectors from different walls that we've collided with we can no longer be sure of the length of avoidVector. We can be sure it points in the right direction but if we've collided with 10 walls it might have a greater magnitude than if we've collided with 5 walls. Since we're going to use it as our acceleration we need it to be uniform after every collision test and so we'll normalize it to make it into a unit vector of length 1. This means that after doing all the collision detection there's this line of code:

normalize_vec( &avoidVector[ X_COORD ], &avoidVector[ Y_COORD ] );

Margins when moving around

I've made one slight alteration to help with flocking. The geometry of the level is made up of tiles of a certain size, right now 30 x 30 pixels. The squares making up the characters in a level used to be half the size of these geometry tiles so 15 x 15 pixels. This however meant that they could get wedged in between geometry quite easily. Imagine there's two empty tiles flanked by two solid tiles, the space in between the two solid tiles is then 60 pixels. In those 60 pixels you could exactly fit four characters 15 pixels wide each. That would then leave no room to maneuver left and right. By making the character squares one pixel smaller this loosened things up and made navigation a lot easier.

fig 7
fig 7 If the red character squares are half the size of the geometry tiles you could fit exactly four of them in between these two solid tiles that have two empty tiles in between them but they would have no space to move sideways.

fig 8
fig 8 If we shrank them by just a little this would give a bit of wiggle room which when it comes to collision avoidance made it a lot easier for squares to slip through gaps

Stopping

Let's say we have a bunch of squares all moving towards the same destination on a map. After the group has reached the destination they should of course all stop but what does it mean for them to have reached the destination?
For the first square that gets there it's simple, it just checks if it's standing on the desired coordinates but how do all the other squares know that the destination is now occupied and they need to stop outside it? You could create some sort of larger area surrounding the destination who's size depends on how many characters wants to move there but it's difficult to guarantee that characters will stack up efficiently enough to fit into this area and the level geometry might not allow it.
Instead we can use time as the limiting factor. If a square keeps colliding with other squares when it tries to move to the destination it should eventually get exhausted and give up, stopping completely.

So how much time should we give it before making the square stop? Well as an estimate we could use the time it would take the square to reach it's target if it moved in a straight line. For example if the square is 200 pixels away from it's target and moving at 5 pixels per second then the total time it would take for it to reach it's target if it could move in a straight line would be 200 / 5 = 40 seconds.
So if the square was stuck 200 pixels away from it's destination, colliding with other squares, then after 40 seconds of doing that we could tell it to stop. This is not entirely scientific, there's nothing saying the square would not have been able to get to it's destination if it had had a bit more time and a destination that's close by in a straight line might be far away when taking the level geometry into consideration. So it's certainly not a prefect system by we're making an estimate.

However calculating the distance from the square to it's destination is an expensive operation requiring a square root and since honestly the time it should wait before stopping is arbitrary I've decided to use the X distance + the Y distance to the target instead. Which is a close enough approximation and guarantees a none zero value.

As for the timer, when we're colliding with another square which is stopped it will be counting up in seconds and constantly comparing that timer value to a maximum allowed time based on the distance from the target as stated above. When we're colliding with a square which is moving or not colliding with any square, and the timer is above zero it should be counting down so as to slowly reset the timer when there aren't any collisions.
The reason for differentiating between collisions with stopped and moving squares is so that we won't get caught in a traffic jam, colliding with many moving squares and making us stop when really those squares would have moved out of our way eventually.
One problem with this that I noticed was that acceleration will cause squares to swing out into empty space when avoiding a collision and the amount of time spent not colliding would reset the stop timer sufficiently so that the square would never stop moving.

fig 9
fig 9 The red square wants to move to a position occupied by the blue square, represented by the X. Starting off at position 1 it will move along the border of the blue square but because it doesn't have instantaneous acceleration it will swing out away from the blue square ending up at position 2 before being able to change it's velocity and head back towards the blue square. Once it's back and colliding with the blue square at position 3 it will once again move along it's side then swing out into empty space again represented by position 4.
The stop timer will be counting up when it's colliding with the blue square but conversely will also be counting down whenever it's away from the blue square. Because the acceleration isn't instantaneous it will spend more time away from the blue square, near positions 2, 4, 6 and 8, than colliding with it at positions 1, 3, 5 and 7, so the stop timer will never reach a high enough value to actually stop the red square.

To solve this I first tried using the dot product. As stated in previous tutorials the dot product of two vectors will be negative if the angle between the vectors is more than 90°. We could take the dot product between the acceleration and velocity vector and when the red square is moving away from the blue square it's velocity will be pointing away from it but the acceleration will be pointing towards it because it's trying to change it's course and head back. Thus the angle between acceleration and velocity will be greater than 90° and the dot product negative. When the dot product was negative it would not decrement the stop timer. This would mean that the stop timer would only be counting down when a square was more or less moving in the direction it desired, when the acceleration and velocity corresponds to within 90°. This would slow down the decrementation of the timer and it would reach it's cutoff value faster and stop the moving square.

fig 10
fig 10 Again the red square is trying to move to position X that is occupied by the blue square. It starts at position 1 and then swings out into empty space as before. The yellow arrows represents it's acceleration which is constant and always points towards the X it wants to move to. The green arrows are the velocity that decreases as the acceleration slowly manages to reverse the direction of movement.
In positions 2, 3 and 4 the angle between the acceleration vector and the velocity is greater than 90° meaning we won't decrement the stop timer while the red square is traveling this distance. At positions 5, 6 and 7 the angle is less than 90° and so here the stop timer would be counting down. This effectively slows down the speed at which the timer decrements.

This worked but really just amounted to counting down using the frame time divided by two. So one second would decrement the timer half a second on average. There were then additional problems concerning if a square was stuck between many other squares it would rapidly change it's acceleration and since it was so close to other squares it's speed was close to zero so the dot product calculation would give random results. In the end just decrementing the stop timer by half the real time solved both problems and was the simpler solution.

This is the code I ended up with for the timer to stop a moving square:
1. Check if we've collided with another square that has already stopped.
1.1 If so increment the stop timer with the frame time.
1.2 Calculate an approximate value for how long it would take us to move to our target in a straight line.
1.3 Check if the stop timer is larger than the value from 1.2 and if so return true to indicate that we should stop.
2. If we did not collide with a stopped square then we check if our stop timer is above zero seconds and if so decrement it using half the frame time. Half because we want to slow the decrementation down as stated above.
3. Return false to indicate that we shouldn't stop.

		bool ai_stop_timer_moving( double *stopTimer, const bool collision, const bool collisionWithStopped, 
				const double xMe, const double yMe, const double xTarget, const double yTarget, const double topSpeed )
		{
1.			if( collisionWithStopped ) {
1.1				*stopTimer += g_frametime;
1.2				const double xDist = fabs( xMe - xTarget );
1.2				const double yDist = fabs( yMe - yTarget );
1.2				const double maxTime = ( xDist + yDist ) / topSpeed;
				
1.3				if( *stopTimer > maxTime ) return true;
			}
2.			else if( *stopTimer > 0 ) *stopTimer -= g_frametime / 2;

3.			return false;
		}

Moving out of the way when stopped then stopping again

There's another scenario that we need to take into account: If a square is stopped and another one is trying to move through it it should get out of the way.
To get a still square moving again is not a problem, the collision algorithm detects the collision and sets it accelerating in the direction of the wall that it's colliding with, same as above. The problem is that we can't just wait for still standing squares to stop colliding before stopping them again. The reason is that you get what might be called self resonance in the system.
If you had a group of still standing squares bunched together and one moving square bumped into one of them that square would start bumping into other still squares and even when the original moving one had disappeared they would continue to bump into and setting each other in motion again and it would take a long time for the system to settle down.

To solve this we will again use time as the limiting factor but now the timer will count down to zero instead of up towards some cut off value. When a still standing square gets bumped into by a moving one it will set it's stop timer value to 5 seconds, giving it 5 seconds to move out of the way. If it's still bumping into the moving square after those five seconds the timer will again reset to five, giving it an additional five seconds and so on. So as long as the stopped square is colliding with a moving one it will try to move out of the way.
If this stopped square bumps into another stopped square then that one will copy the timer value of the square it bumped into. So if there's two seconds left on the timer when our stopped square bumps into stopped square #2 then #2 will set it's own timer to two seconds and then start counting down. They will only keep moving for as long as their timers are above zero. This will mean that even if a group of squares keep bumping into each other and copy each other's timers the over all movement time left in the system will always be decreasing as long as there's not a moving square bumping into the group somewhere.

The code for stopping a square which is already stopped is:
1. If we're colliding with a moving square then set our stop timer to five seconds regardless of it's current value and return false in step 4. farther down to indicate that we shouldn't stop.
2. If we're not colliding with a moving square and our stop timer is above zero do the following tests:
2.1 If there hasn't been a collision at all then we ignore whatever value the timer has and we just stop since we're supposed to be stopped anyway and were just moving till we got out of someone's way.
2.2 Else we decrement the stop timer and then check if it's below zero. If it is then we return true to indicate that we should stop.
3. If there's been a collision we can now be certain that it's been with another stopped square because we already check for moving squares in step 1.
If our own stop timer is below zero but the timer of the square we've collided with isn't then we copy the time of this other square into our own timer. - If we've collided with multiple stopped squares we would have chosen the timer with the largest remaining value, this is done elsewhere in the code. - This is to indicate that we should start moving. We subtract the frame time from the other square's stopped timer to ensure that they won't simply copy back the exact same time in the next frame if their own timer had reached zero and potentially getting into a situation where the system never settles down.
4. Return false to indicate the we should not stop moving.

	bool ai_stop_timer_stopped( double *stopTimer, const bool collision, const bool collisionWithMoving, const double otherStopTimer )
	{
1.		if( collisionWithMoving ) *stopTimer = 5;
2.		else if( *stopTimer > 0 ) {
2.1			if( !collision ) return true;

2.2			*stopTimer -= g_frametime;
2.2			if( *stopTimer < 0 ) return true; 
		}
3.		else if( collision && otherStopTimer > 0 ) *stopTimer = otherStopTimer - g_frametime;

4.		return false;
	}

Detecting a collision with a square in a different state

If you've noticed the timer code for a moving square involves the boolean "collisionWithStopped" and the timer code for stopped squares involves another boolean "collisionWithMoving".
These are in fact the same boolean and it's created during collision detection. When testing for collisions there's this code:

if( collision ) {
	if( !*collidedWithOpposite ) *collidedWithOpposite = me->moving != other->moving;
}

Here we have a variable "collidedWithOpposite" that represents if we've collided with square that's in the opposite state to us, e.g. if we're moving and the square we've collided with is stopped. "moving" are boolean member variables of our square struct and gets set to true if it's moving towards some destination on the map.
"collidedWithOpposite" gets initialized to false and if we're moving and colliding with a square that is stopped or if we're stopped and the other square is moving it gets set to true and stays true even if there are other collisions that don't fulfill the criterion.
This variable then gets passed up through the logic and used by the different timer functions. In the timer function used by stopped squares it will then represent if we've collided with a moving square and in the timer for moving squares it will represent a collision with a stopped square.

Setting the acceleration

Now that we've had a look at how the timer works we can look at how we use the "avoidVector" from the beginning of the tutorial. First there has to have been a collision, second we either have to be moving or if we're stopped then our stop timer has to be above zero so as to allow us to use the avoidVector to move out of the way.

void ai_acceleration_collision( double *xAcc, double *yAcc, const bool collision, const bool moving, 
		const double stopTimer, const double avoidVector[2] )
{
	if( collision && ( moving || stopTimer > 0 ) ) {
		*xAcc = avoidVector[ X_COORD ];
		*yAcc = avoidVector[ Y_COORD ];
	}
}

Conclusion

It wont give the most efficient avoidance path but it should allow characters to collide with each other without getting stuck and to clump up on the target coordinates. If one group is blocking another group at a choke point you might have to move them out of the way manually, otherwise it could take a long time for the two groups to sort things out themselves.
Despite this I think it works OK, I like complex behavior that arise from simple rules and the base algorithm is just a couple of lines of code. Of course the code to stop moving is a lot more complex and I'm not completely happy with how it turned out. I was trying to simulate a system were a moving square colliding with stopped squares would impart energy to the system that would then gradually dissipate. Sort of like how a passing air plane kicks up turbulence which slowly settles down. The idea for using time as the limiting factor came from James Hague's use of timers in his posts about functional game programming.