Part 47: Monsters Part 7: seeking

Downloads

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

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 wefind 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

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 itimplies 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

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

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, wereturn 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, thenit 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 edgebetween 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

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:

- primary direction
- secondary direction
- opposite of secondary direction
- opposite of primary direction

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

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...