Flanking / Retreating

This tutorial is reliant on the vector fields we implemented previously, so you'll need to have read that to get anything out of it.

Having AI opponents either just standing still and shooting at the player or rushing him gets boring quickly. They should at least be able to circle around and fall back when attacked so as to provide some variety and that's what we'll try and implement in this tutorial.

Here's a small demo program. The blue square represents a character that's either trying to flank or retreat from, the red square.
Red arrows represents the path it would take if moving directly towards the red square. As it would first move into the red square's convex set that's where the arrows are pointing and the set itself is shown as empty red squares.
Green arrows show the path taken if it tried to flank the red square. A convex set is shown with empty green squares and this is an intermediate set used to create an indirect path as explained below.
Orange arrows is the path when retreating from the red square.
Left mouse key places the blue square where the mouse cursor is and right mouse places the red square.
Several possible paths exists both for flanking and retreating and these can be cycled through using the A key.
Code can be found here.

Cost of travel

In order to make a decision on which path to take we have to be able to measure the distance of different paths, however doing so can be an expensive operation. Instead we'll append a second value to our vector field that shows how far away from the convex set a tile is. Every time we do another iteration to add vectors pointing back at the convex set we'll increment an integer that represents how far we've had to travel to get to those tiles.
Looking at figure 1 through 14 in the pathfinding tutorial we can see how this would work. In fig 5 we'll add the number 1 to all green tile as we're on the first iteration and these tiles are then the closest ones to the tile marked O where the vectors are pointing to.
In fig 10 we'll add the number 2 to the green tiles of the second iteration. In fig 11 we'll add 3, fig 12 add 5, fig 13 add 6 and for the last tile add 7. Now we'll end up with a field of increasing numbers that looks like this:

1

fig 1. A field of increasing numbers representing how far away a tile is from the origin tile marked O. Contrast with fig 14 in the pathfinding tutorial.

This number roughly indicates the number of tiles a character would have to traverse in order to get into the convex set. Had it for example stood on the bottom tile with the number 6 in it we can follow the arrows and see that it passes through six tiles before reaching the tile labeled O.
This doesn't always accurately represent the distance between two point. Diagonal movement will take longer than cardinal and the use of convex sets also complicates matters. Consider for example the case below where the points B and C are in the same convex set.

2

fig 2. Points B and C are both in the same convex set as represented by the empty tiles at the bottom. If point A wanted to reach any of them it would first follow a vector field to get into this convex set. The path for getting into this convex set would be the same regardless of which point it wanted to get to, it would just travel straight down. Point A would see the same cost of 6 for both points. Obviously this is because we only calculate cost per convex set and not per tile.

The path taken by two points trying to reach each other can also vary widely. As in this example:

3

fig 3. Point B when navigating to point A will first move into the convex set that point A is in, here represented as the top row of empty tiles. The path taken into this convex set is shown by the tiles with arrows and is not the optimal way to get to A but such are the pitfalls of using convex sets. The cost seen by B in order to reach A would be 3 for the three arrows it uses to get into the convex set. It would then have to traverse seven tiles inside the convex set to get to A but it wouldn't know about those as we only calculate distance between sets.

4

fig 4. From the perspective of point A trying to reach B it would look very different with A having a cost of 7 to reach the convex set of B. Once those seven tiles had been traversed it would be inside the same tile as B.

So B would see a shorter distance for reaching A than A would for reaching B. B however would have to travel farther to reach A than A to reach B. These are problems that crop up when using convex sets. We can't see the real distance between points and it could be different depending on which frame of reference we pick.

For this reason I've called it a cost field instead of a distance field. Though it is kinda similar to the Manhattan distance only we allow diagonal movement.
I won't go into how to code the cost fields. It's a fairly simple procedure, for every vector field an additional cost field is created which like the vector field is just an array. As the vector field gets populated so does the cost field and for each new batch of vectors being placed you increment the cost by one.

Basics

We have two characters on a game level and one of them is trying to maneuver in relation to the other. Either retreating from him or trying to flank him. Real levels however can present complex geometry that's difficult to reason about when trying to decide how to move a character around it. Instead we'll see if we can solve the problem in the abstract and then try to apply that solution to the "real" world. This means that we'll think about this as if our two guys are two dots on a featureless plane and the only measurement known to us is the distance between them.
Instead of convex sets we'll think about places where we can move as points on this plane.

5

fig 5. Blue and red dots are two characters in game. The blue dot represents a character I'll call the "player" from now on and the red dot another character called the "target" that the player wants to maneuver around. The only known measurement known to us is the distance between them, here labeled "c".

In actuality we won't know the exact distance between the characters, instead what we'll have to work with are the tiles the characters are standing on and what convex sets those tiles belong to. From this we'll be able to query the cost of moving from one character's tile into the other character's convex set and though this does not accurately represent the distance it will work well enough though to allow us to model paths.

Flanking

When flanking we still want to move towards the target but in a circuitous way and not straight on. To accomplish this we'll use an intermediate convex set that our player moves into before starting to move towards the target. The problem then becomes how to select this intermediate set so that when we reach it and start moving towards our target proper we'll approach it from the side or back and not the front. Let's look at some scenarios:

6

fig 6. The player moves to point "p" before moving towards the target. An ideal example of how flanking should work.

7

fig 7. The path now skews towards the target but would still be OK.

8

fig 8. Here the player would pass the target before turning back towards it. Not a good path.

What we can gauge is that we want to pick points that are in between the player and target and to their sides. How can we then determine if a point is in between the player and target to begin with? Fortunately there's a computationally simple shape that allows us to do just that called a hyperbola.

9

fig 9. A Hyperbola drawn using the two dots from fig. 5 as focal points for it.

A quick explanation on how hyperbolas work: There's two focal points and when you pick a point on the hyperbola and measure the distance from it to both focal points then the absolute value of the difference between these distances will always give the same result.

10

fig 10. Taking the absolute difference of the distances to each focal point on any part of the hyperbola will yield the same number. So | B1 - R1 | = | B2 - R2 | = | B3 - R3 |

So the lines in fig 9. are drawn using the equation | R - B | = x where R and B are the distances from the red and blue dots respectively and x is an arbitrary constant that for fig. 9 has been set to half the distance between the dots, that is half the c value in fig. 5. Increasing the x value will increase the eccentricity or how "curvy" the hyperbola is. Selecting all points inside the hyperbola's line can easily be done by modifying the equation to | R - B | < x.
Hyperbolas allows for a good initial selection of point as the farther to the side that those points lie the more biased they can be towards either the player or target which is what we want from fig 6 through 8. Allowing for a greater selection of points.

11

fig 11. Changing = to < means all points in between the two green lines in fig. 9 now are solutions to the equation and therefore fills in the hyperbola.

Now we have a pretty decent selection of points to choose from but flanking means not moving directly towards the target so we want to exclude points that lead to a too direct path. To do so we'll use an ellipse which functions similar to a hyperbola in that you start with two focal points but then you pick all points around those focal points where the sum of the distances from each focal are equal to some constant. So R + B = x.

12

fig 12. Drawing an ellipse around the two focal points using the formula R + B = x. With a value of x set to twice the c value in fig. 5.

As with the hyperbola if we switch out the equal sign so that the equation reads R + B < x we can select all points inside the ellipse. Those we then remove from the selection, creating a hole in the hyperbola:

13

fig 13. Removing all points within the ellipse from fig. 12.

Last step is to limit the range so we don't end up moving too far across the map when trying to flank someone. To do this we'll again use an ellipse but this time larger than the one in the middle. A value of 8 * c allows for a decent surrounding area.

14

fig 14. Drawing another larger ellipse around the foci. Seen only partially as the red lines to the sides.

15

fig 15. This time it's points outside the ellipse that we remove in order to limit how far our character can move when flanking.

If we first move to any point inside the green area and then towards the target we'll consider that a flanking maneuver. The same concept as for selecting the green area will be applied to selecting convex sets and if we're lucky the theory will match reality.

Code

To begin with we'll have to setup some initial values, namely finding the c value from fig. 5 and calculating the constants for our hyperbola and ellipses.

1. For starters the only thing known to use are the tiles that the player and target characters are standing on. This would be the position of our blue and red dots in fig. 5. What we'll be returning is the number of an intermediate convex set we should move into before approaching the target.
2. Get which convex sets the player and target tile belong to.
3. If both are standing in the same convex set then flanking will not be possible as the cost for moving will be zero and the equations won't work. When this happens we'll just return the current set the player is standing in and as he's already in that set he'll immediately start moving towards the target. So it works as a fail over.
4. Get the cost for the player moving into the target's convex set and what the cost would be for the target to move into the player's.
5. As these two costs might vary considerably we'll just average them out. averageCost is then equivalent to the c value in fig. 5.
6. Calculate a constant for describing the hyperbola in fig. 11.
7. Calculate a constant for describing the ellipse in fig. 12.
8. Calculate a constant for describing the ellipse in fig. 14.
9. Now we can go looking for a convex set that fits our criteria. Starting with the first set in the map and going through all of them.
10. If no suitable set has been found then the search function will have returned NONE which is magic number set to UINT_MAX that's used to indicate "nothing" for a bunch of stuff and we'll fail over again and return the player's own convex set. If the returned convex set number is not NONE we'll return it instead.

1.	unsigned int ai_flank_get_convex_set( const unsigned int myTile, const unsigned int targetTile )
	{
2.		const unsigned int myConvexSet = level_get_convex_set( myTile );
2.		const unsigned int targetConvexSet = level_get_convex_set( targetTile );

3.		switch( myConvexSet == targetConvexSet ) { case true: return myConvexSet; }

4.		const unsigned int myCost = level_get_cost( myTile, targetConvexSet );
4.		const unsigned int targetCost = level_get_cost( targetTile, myConvexSet ) ;

5.		const unsigned int averageCost = ( myCost + targetCost ) / 2;
6.		const unsigned int hyperbola = averageCost / 2;
7.		const unsigned int smallEllipse = averageCost * 2;
8.		const unsigned int largeEllipse = averageCost * 8;

9		const unsigned int convexSet = ai_flank_convex_set_search( myTile, targetTile, hyperbola, smallEllipse, largeEllipse, 0, level_get_nbr_convex_sets() );

10.		return convexSet == NONE ? myConvexSet : convexSet;
	}

When searching for convex sets we'll likely find multiple ones that fit our search criteria, just as in fig. 15 there's still technically an infinite number of points left inside the green area. What we'll do is save a bunch of the ones we find in a buffer and when the search is complete we'll pick one at random. This will have the benefit of making the character's decisions less predictable. Here's the search function:

1. A buffer capable of holding 256 integers, each representing the index number of a convex set we've found.
2. A buffer index, indicating how many sets are in the buffer.
3. Get the cost for the player and target to move into the selected convex set.
4. Subtract the two costs from each other for to compare against the hyperbola constant. As we're using unsigned ints we need to check which value is largest before doing the subtraction and this ends up being an absolute value as it's always positive.
5. Add the two costs together for to compare against the two ellipses.
6. Test if our convex set satisfies the criteria and if so set a variable to true:
6.1 The set is outside the hyperbola from fig. 11 set the variable to false.
6.2. The set is inside the ellipse from fig. 12 set the variable to false.
6.3. The set is outside the ellipse from fig. 14 set the variable to false.
6.4. Else the set has passed all the tests and we set the variable to true.
7. If the test in step 6 was successful we add the set's number to the buffer and increment the buffer index.
8. Move on to and test the next convex set in the map.
9. If we've searched through all convex sets on the map or if our buffer is full then we need to return.
9.1. If the buffer is empty that means our search has failed and we have no sets to return so again we'll fail over and return NONE.
9.2. If the buffer is not empty we:
9.2.1. Pick an index in the buffer at random.
9.2.2. Reset the buffer index so next time the function is run it will overwrite what's in the buffer.
9.2.3. Return the set number that's at our random index.

		unsigned int ai_flank_convex_set_search( const unsigned int myTile, const unsigned int targetTile, const unsigned int hyperbola, const unsigned int smallEllipse, const unsigned int largeEllipse, const unsigned int convexSet, const unsigned int convexSetsRemaining )
	{
1.		static unsigned int buffer[ 256 ] = { 0 };
2.		static unsigned char bufferIndex = 0;

9.		const bool endSearch = convexSetsRemaining == 0 || bufferIndex == 255;
9.1.		const bool bufferEmpty = bufferIndex == 0;
9.		switch( endSearch + bufferEmpty * 2 ) {
9.1.		case true + true * 2: return NONE;
9.2.		case true + false * 2:
			{
9.2.1			const unsigned char randomIndex = rand() % bufferIndex;
9.2.2			bufferIndex = 0;
9.2.3			return buffer[ randomIndex ];
			}
		}

3.		const unsigned int myCost = level_get_cost( myTile, convexSet );
3.		const unsigned int targetCost = level_get_cost( targetTile, convexSet );

4.		const unsigned int costSub = myCost > targetCost ? myCost - targetCost : targetCost - myCost;
5.		const unsigned int costAdd = myCost + targetCost;

6.		const bool addCS =
6.1.		costSub > hyperbola ? false :
6.2.		costAdd < smallEllipse ? false :
6.3.		costAdd > largeEllipse ? false :
6.4.		true;

7.		switch( addCS ) {
7.			case true: buffer[ bufferIndex++ ] = convexSet;
		}

8.		return ai_flank_convex_set_search( myTile, targetTile, hyperbola, smallEllipse, largeEllipse, convexSet + 1, convexSetsRemaining - 1 );
	}

Retreating

When retreating we'll only want to look at points that are directly behind the player. To that end we can modify our equation to only include points that are above the hyperbola. First we'll change the < from fig. 11 to >, which will invert the colors in fig. 11 making the top and bottom parts of the image that are outside the hyperbola green.
Next we'll only look at points where the distance to the player is closer than that to the target. That'll eliminate all points in the lower half of the screen leaving us with the following picture:

16

fig 16. Limiting the points where the player is able to retreat to.

A bit of that green however is towards the target and we don't want to move towards it, so those points have to go. To get rid of them we'll draw a circle with a diameter of twice the distance between the player and target and who's center is the target. All points inside this circle get removed.

17

fig 17. Getting rid of points that are too close to the target.

As a last step we again need to limit how far away the player can run to stop him from retreating all the way across the map. We'll draw another circle of diameter 2 * c but now with it's center on the player. All points outside this circle get excluded.

18

fig 18. Setting a max limit on how far the player is allowed to retreat.

Code

Setup is exactly the same as when flanking but but instead of calculating the constants of two ellipses we just calculate a single diameter that will be used by both our circles.

1. Circle diameter of 2 * c that the circles in fig. 17 and 18 both use.

	unsigned int ai_retreat_get_convex_set( const unsigned int myTile, const unsigned int targetTile )
	{
		const unsigned int myConvexSet = level_get_convex_set( myTile );
		const unsigned int targetConvexSet = level_get_convex_set( targetTile );

		switch( myConvexSet == targetConvexSet ) { case true: return myConvexSet; }

		const unsigned int targetCost = level_get_cost( targetTile, myConvexSet );
		const unsigned int myCost = level_get_cost( myTile, targetConvexSet );

		const unsigned int averageCost = ( myCost + targetCost ) / 2;
		const unsigned int hyperbola = averageCost / 2;
1.		const unsigned int circle = averageCost * 2;

		const unsigned int convexSet = ai_retreat_convex_set_search( myTile, targetTile, hyperbola, circle, 0, level_get_nbr_convex_sets() );

		return convexSet == NONE ? myConvexSet : convexSet;
	}

Search function is likewise very similar to when flanking, only using the criteria from fig. 16, 17 and 18 instead.

1. Check if the cost for moving into the set is lower for the player than for the target. I.e. the player has to be closer to the set as in fig. 16.
2. Subtract the player's cost from the target's cost and compare that value to the hyperbola constant to see if it's outside the hyperbola. Note that we're able to safely subtract the player's cost from the target's since in the previous step we've concluded that the target's cost is greater than that for the player. Otherwise subtracting unsigned ints like this would be unsafe.
3. Make sure that the target's cost is greater than the diameter of our circle. Conforming to fig. 17.
4. Make sure the the player's cost is lower than the diameter of our circle. Conforming to fig. 18.
5. If all previous tests are passed then add the set to the buffer.

	unsigned int ai_retreat_convex_set_search( const unsigned int myTile, const unsigned int targetTile, const unsigned int hyperbola, const unsigned int circle, const unsigned int convexSet, const unsigned int convexSetsRemaining )
	{
		static unsigned int buffer[ 256 ] = { 0 };
		static unsigned char bufferIndex = 0;

		const bool endSearch = convexSetsRemaining == 0 || bufferIndex == 255;
		const bool bufferEmpty = bufferIndex == 0;
		switch( endSearch + bufferEmpty * 2 ) {
			case true + true * 2: return NONE;
			case true + false * 2:
				{
				const unsigned char randomIndex = rand() % bufferIndex;
				bufferIndex = 0;
				return buffer[ randomIndex ];
				}
		}

		const unsigned int myCost = level_get_cost( myTile, convexSet );
		const unsigned int targetCost = level_get_cost( targetTile, convexSet );

		const bool addCS =
1.			myCost > targetCost ? false :
2.			( targetCost - myCost ) < hyperbola ? false :
3.			targetCost < circle ? false :
4.			myCost > circle ? false :
5.			true;

5.		switch( addCS ) {
5.			case true: buffer[ bufferIndex++ ] = convexSet;
		}

		return ai_retreat_convex_set_search( myTile, targetTile, hyperbola, circle, convexSet + 1, convexSetsRemaining - 1 );
	}

Conclusions

It works surprisingly well but sometimes a character will end up backtracking or running past the target. This is exacerbated if the characters are boxed in and there's a limit number of paths available to them. That's why the test map at the top is very open plan. Some of that could possibly be mitigated by tweaking the sizes of the different geometrical elements. Such as enlarging the ellipse in fig. 12 would cut down on paths that are too direct but would also limit the paths available to use, which might be OK though on larger maps.
Sizes for the different elements were chosen here primarily because they could fit in the limited image sizes and still look decent on screen and perhaps should be adjusted in a full size game level.
Characters picking the wrong path is somewhat ameliorated by the randomness. If a character starts from the same position the path should not be bone headed every time and with multiple characters most would appear intelligent, I hope.

Searching through all convex sets could also be taxing on performance in a real game with large levels that has lots of convex sets in them. The obvious thing would be to start searching at the set number that the character is currently standing in but adjacent numbers aren't really good indicators for sets that are adjacent spatially. Setting a max number of searches per frame and splitting the search between multiple frames seems like the simplest solution.