Part 47: Monsters Part 7: seeking

Downloads

Source code
Executable for the map editor - exactly the same as in part 40 (Windows 32bits)
Executable for the game (Windows 32bits)

Before you try to compile the code go to the "Projects" tab on the left menu, select the "Run" settings for your kit,
and set the "Working directory" to the path of "editor\data" for the editor or "game\data" for the game.

Cone of vision

In this part we will talk about the seeking behavior when a group of monsters sees the party and walks towards it.
So first let's look how the group "sees" the party.
In the original game it was done in 3 stages.
At the beginning we will look if the party is in our "cone of vision" that looks like that for a monster looking
towards the right:


To test if the party is in the cone we will define 2 distances distA and distB between the group and the party.
distA is the distance along the line of sight of the monster and distB is the perpendicular direction.


When the party is inside the cone, distA must be positive and distB must be smaller that distA in absolute value.
That's what we check in the isTargetInConeOfVision() function:

		bool CMonsterGroup2::isTargetInConeOfVision(CVec2 pos, CVec2 target, EMonsterDir dir)
		{
			int distA, distB;

			if (dir == eMonsterDirUp)
			{
				distA = pos.y - target.y;
				distB = ABS(pos.x - target.x);
			}
			else if (dir == eMonsterDirDown)
			{
				distA = target.y - pos.y;
				distB = ABS(pos.x - target.x);
			}
			else if (dir == eMonsterDirLeft)
			{
				distA = pos.x - target.x;
				distB = ABS(pos.y - target.y);
			}
			else
			{
				distA = target.x - pos.x;
				distB = ABS(pos.y - target.y);
			}

			return (distA > 0 && distB <= distA);
		}
				
As the monsters in the group can have different orientations, we will check this cone for each of them until we
find one that can see the party.
But some monsters like the screamer can see the towards all directions. I added a parameter "sideAttack" in the
monsters database for this purpose.

So the beginning of our main function to check visibility is like this:

		int CMonsterGroup2::getVisibleDistance(CVec2 pos, CVec2 target, uint8_t type)
		{
			CMonsters::SMonsterData&    data = monsters.monstersDatas[type];

			for (int i = 0; i < 4; ++i)
			{
				if (mMonsters[i].pos != eMonsterPosNone)
				{
					if (data.sideAttack == true ||
					    isTargetInConeOfVision(pos, target, mMonsters[i].dir) == true)
					{
				

Distance

Now that we know that the party is inside the cone of vision of the group, we will check it's distance.
Every monster type has a maximum viewing distance that I put along with the "sideAttack" in monsters.xml:

		<!-- 07 Screamer -->
		<monster name = "MONSTER07">
			[...]
			<side_attack/>
			<sight_range>1</sight_range>
			[...]
		</monster>
				
Computing the distance between the group and the party using the classic Pythagoras formula is expensive as it
implies a square root that is a slow operation.
Instead the original game used the much simpler Mahattan distance that is simply the sum of the absolute values
of the distances along x and y.



		CVec2 CVec2::abs(const CVec2& vec)
		{
			return CVec2(ABS(vec.x),
			             ABS(vec.y));
		}

		uint32_t CVec2::manhattanDistance(const CVec2& dest)
		{
			CVec2 dist = CVec2::abs(dest - *this);
			return dist.x + dist.y;
		}
				
The view distance of the monsters varies with the light. The darker the dungeon, the shorter this max distance is.
So our main test function becomes that:

		int CMonsterGroup2::getVisibleDistance(CVec2 pos, CVec2 target, uint8_t type)
		{
			CMonsters::SMonsterData&    data = monsters.monstersDatas[type];

			for (int i = 0; i < 4; ++i)
			{
				if (mMonsters[i].pos != eMonsterPosNone)
				{
					if (data.sideAttack == true ||
					    isTargetInConeOfVision(pos, target, mMonsters[i].dir) == true)
					{
						int range = data.sightRange;
						int light = game.getLightPower();
						range -= (256 - light) / 102;

						if (range < 1)
							range = 1;

						int dist = pos.manhattanDistance(target);

						if (dist > range)
							return 0;
						else
							return distanceWithWalls(pos, target);
					}
				}
			}
			return 0;
		}
				

Walls blocking the sight

The distanceWithWalls function now is the 3rd stage of our vision tests.
Now that the party position is bounded by the cone and the distance, we will actually draw the line of sight
between it and the group.
And we will follow it tile by tile to test if we encounter walls on the way.


To draw this line we will use the Bresenham algorithm.
We need 2 "increment" variables one for each the axes.
For the line on this image we will go along every pixel on the X axis so the increment is 1.
Along the Y axis the increment will be the slope of the line.


It is easy to understand that this works only for lines that are more horizontal than vertical.
For more vertical lines we will use an increment of 1 along the Y axis and compute the X axis increment accordingly
to fit the slope of the line.
Also note that for symmetry reasons we start at the center of the tile so we add 0.5 to the coordinates of the
ends of the line.
So here is the code that follows the line:

		//---------------------------------------------------------------------------------------------
		// returns the distance between source and dest if there are no walls in between, or returns 0 if there are walls
		int CMonsterGroup2::distanceWithWalls(CVec2 source, CVec2 dest)
		{
			CVec2   delta = dest - source;
			CVec2   absDist = CVec2::abs(delta);

			// if we are right next to the destination, don't take the walls into account.
			if (absDist.x + absDist.y <= 1)
				return 1;

			// is the line more horizontal or more vertical ?
			bool    isXSmallerThanY = (absDist.x <  absDist.y);

			// compute the steps for advancing one tile at a time along the largest axis
			float   stepX, stepY;

			if (isXSmallerThanY == true)
			{
				stepY = SGN(delta.y);
				stepX = stepY * (float)delta.x / (float)delta.y;
			}
			else
			{
				stepX = SGN(delta.x);
				stepY = stepX * (float)delta.y / (float)delta.x;
			}

			// for symetry reasons, start at the center of the tile
			float   posX = (float)source.x + 0.5;
			float   posY = (float)source.y + 0.5;

			while (true)
			{
				// advance
				float nextX = posX + stepX;
				float nextY = posY + stepY;

				// test walls
				CVec2   srcTile((int)posX, (int)posY);
				CVec2   nextTile((int)nextX, (int)nextY);

				if (isWallBetweenPos(srcTile, nextTile) == true)
					return 0;

				// are we at the end ?
				if (nextTile.manhattanDistance(dest) <= 1)
					return absDist.x + absDist.y;

				// update position and loop back
				posX = nextX;
				posY = nextY;
			}
		}
				
The isWallBetweenPos() function will check if there is a wall between 2 tiles.
If the tiles touch each other horizontally or vertically, we only check one wall, but if they touch
diagonally, we check 1 wall on the X axis and one on the Y axis.
This function also checks for stairs and closed doors.

		bool CMonsterGroup2::isWallBetweenPos(CVec2 source, CVec2 dest)
		{
			CTile*  srcTile = map.getTile(source);
			CTile*  dstTile = map.getTile(dest);

			// check walls
			if (dest.x > source.x)
			{
				if (srcTile->mWalls[eWallSideRight].getType() != 0)
					return true;
			}
			else if (dest.x < source.x)
			{
				if (srcTile->mWalls[eWallSideLeft].getType() != 0)
					return true;
			}

			if (dest.y > source.y)
			{
				if (srcTile->mWalls[eWallSideDown].getType() != 0)
					return true;
			}
			else if (dest.y < source.y)
			{
				if (srcTile->mWalls[eWallSideUp].getType() != 0)
					return true;
			}

			// check stairs
			if (dstTile->getType() == eTileStairs)
				return true;

			// check doors
			if (dstTile->getType() == eTileDoor && dstTile->getBoolParam("isOpened") == false)
			{
				// we can't see through a closed door unless it's a porticullis
				if (dstTile->getIntParam("Type") != 0)
					return true;
			}

			return false;
		}
				

Getting the direction to the party

We will now write a function to get the direction of the group towards the party nearly the same way it was done in
the original game.
This function will return a primary direction that will always be towards the party and a secondary direction that
will be 90° to the left of to the right.
This secondary direction will be used in case we can't move to the tile of the primary one.

First, we will need 3 small functions that given a direction returns the one 90° to the left, the one 90° to the
right and the opposite one.

		//---------------------------------------------------------------------------------------------
		EMonsterDir CMonsterGroup2::nextDir(EMonsterDir dir)
		{
			static const EMonsterDir nextDirs[4] =
			{
				eMonsterDirRight,   // up
				eMonsterDirLeft,    // down
				eMonsterDirUp,      // left
				eMonsterDirDown     // right
			};

			return nextDirs[dir];
		}

		//---------------------------------------------------------------------------------------------
		EMonsterDir CMonsterGroup2::prevDir(EMonsterDir dir)
		{
			static const EMonsterDir prevDirs[4] =
			{
				eMonsterDirLeft,    // up
				eMonsterDirRight,   // down
				eMonsterDirDown,    // left
				eMonsterDirUp       // right
			};

			return prevDirs[dir];
		}

		//---------------------------------------------------------------------------------------------
		EMonsterDir CMonsterGroup2::oppositeDir(EMonsterDir dir)
		{
			static const EMonsterDir oppositeDirs[4] =
			{
				eMonsterDirDown,    // up
				eMonsterDirUp,      // down
				eMonsterDirRight,   // left
				eMonsterDirLeft     // right
			};

			return oppositeDirs[dir];
		}
				
Now, to get the direction the first cases are simple: if the group is aligned with the party along x or y, we
return the direction of the party. The secondary direction is randomly chosen between the direction perpendicular
to the primary one.

		EMonsterDir CMonsterGroup2::getDirectionToTarget(CVec2 pos, CVec2 target, EMonsterDir& secondaryDir)
		{
			// group aligned with target
			if (pos.x == target.x)
			{
				secondaryDir = (RANDOM(2) ? eMonsterDirLeft: eMonsterDirRight);

				if (target.y < pos.y)
					return eMonsterDirUp;
				else
					return eMonsterDirDown;
			}

			if (pos.y == target.y)
			{
				secondaryDir = (RANDOM(2) ? eMonsterDirUp: eMonsterDirDown);

				if (target.x < pos.x)
					return eMonsterDirLeft;
				else
					return eMonsterDirRight;
			}
				
Now here is the interesting part.
We know that the party is not on the same line/column as the group.
We will try all directions until we find one where the party is in the cone of vision.
This will be our primary direction.

			// group is not aligned with target: we find in which direction we need to turn to face it
			EMonsterDir primaryDir = eMonsterDirUp;

			while (true)
			{
				if (isTargetInConeOfVision(pos, target, primaryDir) == true)
				{
				
Then we check the directions 90° to the left and right. If we can't see the party in one of those directions, then
it is "in front" of us. That's the case we already saw in the images:


In this case, as for the case we discussed before, the secondary direction is randomly chosen between the ones that
are perpendicular to the direction we are looking to.

					// found a direction where we can see the target
					secondaryDir = nextDir(primaryDir);

					if (isTargetInConeOfVision(pos, target, secondaryDir) == false)
					{
						secondaryDir = prevDir(primaryDir);

						if (isTargetInConeOfVision(pos, target, secondaryDir) == false)
						{
							// target can neither be seen when we turn right nor when we turn left, so we are in the "middle" of the cone
							if (RANDOM(2))
								secondaryDir = oppositeDir(secondaryDir);

							return primaryDir;
						}
					}
				
If the party is also visible in one of the 2 perpendicular directions we tested, that means that it is on the edge
between 2 cones of visions. So it is on a diagonal relatively to the group.


In this case, we randomly choose one of the directions as the primary one, and the other will be the secondary.

					// we can see the target both in the primary and secondary direction, it is on the edge of the cone
					if (RANDOM(2))
					{
						EMonsterDir temp = primaryDir;
						primaryDir = secondaryDir;
						secondaryDir = temp;
					}

					return primaryDir;
				}

				primaryDir = (EMonsterDir)(primaryDir + 1);
			}
		}
				

The seek state

Here we will put together all the functions we talked about to define the "seek" behavior.
So let's begin with this picture that show where this behavior will take place inside the state machine.


Then let's take a look at our differents states.
The easiest one is the fight state that doesn't change very much - Remember that most of this behavior takes place
at the Monster level. The MonsterGroup2 only handles the transition.

		void CMonsterGroup2::fight(CVec2 mapPos, uint8_t type)
		{
			// transition to seek state ?
			if (mapPos.manhattanDistance(player.pos) != 1)
				enterSeekState();
		}
				
Notice that I wrote "enter" functions for each state just to initialize the variables needed.

Now the wander state does not change much either.
We only use our getVisibleDistance() function to test if the group can see the player.

		void CMonsterGroup2::wander(CVec2 mapPos, uint8_t type)
		{
			// transition to seek state ?
			int dist = getVisibleDistance(mapPos, player.pos, type);

			if (dist > 0)
			{
				enterSeekState();
			}
			else
			{
				// wander
				[...]
			}
		}
				
Finally the in the seek state, we first check the transition to the fight state.

		void CMonsterGroup2::seek(CVec2 mapPos, uint8_t type)
		{
			// transition to fight state ?
			if (mapPos.manhattanDistance(player.pos) == 1)
			{
				enterFightState(mapPos);
			}
				
Now remember that I said at the beginning that the group does not always go towards the party.
When it sees the party it goes towards it, but if the party gets out of sight, the groups continues to walk
towards the last position he saw it.
If the group reach this position and the party is still not visible, then it goes back to wandering mode.

So in our function we will use the getVisibleDistance to check if we see the party. If it's the case, we store its
position to a lastPlayerPos variable, that will be the target of the group.
And if we reached this target, we enter the "wander" state.

			else
			{
				// seek
				int dist = getVisibleDistance(mapPos, player.pos, type);

				if (dist > 0)
				{
					lastPlayerPos = player.pos;
				}
				else
				{
					// We can't see the player. If we arrived at the destination, go back to wander
					if (mapPos == lastPlayerPos)
					{
						enterWanderState();
						return;
					}
				}
				
Now we will walk towards lastPlayerPos.
We call the getDirectionToTarget() function to get the primary and secondary directions.
Then we will test in each direction in this order:
If we can get to the neighbor tile in one of theses directions, we boldly go to it.
But if every neighboring tile is blocked, we are stuck, so we go back to the wander state.

				if (moveTimer.update() == true)
				{
					initMoveTimer(type);

					// choose direction
					EMonsterDir primaryDir;
					EMonsterDir secondaryDir;
					primaryDir = getDirectionToTarget(mapPos, lastPlayerPos, secondaryDir);

					if (canMove(mapPos, (EWallSide)primaryDir) == true)
					{

					}
					else if (canMove(mapPos, (EWallSide)secondaryDir) == true)
					{
						primaryDir = secondaryDir;
					}
					else if (canMove(mapPos, (EWallSide)oppositeDir(secondaryDir)) == true)
					{
						primaryDir = oppositeDir(secondaryDir);
					}
					else if (canMove(mapPos, (EWallSide)oppositeDir(primaryDir)) == true)
					{
						primaryDir = oppositeDir(primaryDir);
					}
					else
					{
						primaryDir = (EMonsterDir)4;
						enterWanderState();
					}

					// move
					if (primaryDir != 4)
					{
						dir = primaryDir;
						move(mapPos, type);

						for (int i = 0; i < 4; ++i)
							mMonsters[i].dir = primaryDir;
					}
				}
			}
		}
				

Conclusion

I had to tweak a few parameters like the moments we check for the move timer to make the fights more dynamic and a
bit more random.
Anyways there is still some small refinements to include in the monsters behavior to catch the feeling of the
original game.

The original game had some more features that I did not include by lack of time. I.e. while the monsters see the
party, they run towards it instead of walking.
Monsters could also "smell" the champions when they are near.
Either way, the combat system is no completely finished yet, and it will be improved later.

While I was testing this part I saw some strange behaviors. So there are probably some small bugs in the code of
this part. I need to investigate it further...