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);
}
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
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>
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;
}
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;
}
}
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];
}
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;
}
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)
{
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;
}
}
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
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();
}
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
[...]
}
}
void CMonsterGroup2::seek(CVec2 mapPos, uint8_t type)
{
// transition to fight state ?
if (mapPos.manhattanDistance(player.pos) == 1)
{
enterFightState(mapPos);
}
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;
}
}
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...