C++ Coding Practice
Recently I had a few inquiries whether I could say more about how the AI is constructed in practical terms.
In principle it is a vast topic that has as its top the logical decision making, the sequencing of events or interactions that make up an entity's behaviour. But before this can happen many layers of information have to be processed and made accessible.
The Quantomas AI doesn't use neural networks, supercomputers or machine learning, instead we use maths and logic to build large networks of interconnected data which we evaluate with well defined algorithms.
Needless to say, any reasonably complex scenario, like the maps on which Heroes games play out, creates abundant amounts of data and processing it efficiently is of paramount importance.
A large part of this processing efficiency comes from the AI itself by smartly focusing on the most critical parts of the situation at hand. But there is no way around it, to arrive at this stage we have first to evaluate the data that describes the situation.
Most real-world scenarios, and anything that resembles it to some extent like a Heroes map, have to deal with spatial relations, i.e. the distance between objects, which requires means to measure all kinds of distances. Once you have to deal with hundreds or thousands of objects as in Heroes, it becomes a critical part of your application to do this as efficiently as possible.
For a game like Heroes this function is performed by a pathfinder. This task is more complicated than simply deducing the distance between objects by its coordinates on the map. It's like in the real world, there are obstacles that block your path, some of which you can remove and others you need to walk around, different types of terrain that can be traversed at different speeds and so on. With other words we need a solution that determines the time you need to travel between two objects on a case by case basis, i.e. each path is different.
Heroes III and Heroes V have already competent pathfinders, but when I began working on the AI for Heroes V I realized that for a fast and efficient AI we need a much faster pathfinder that can process the distances between any two objects on the map in nearly constant time.
What's covered here
In terms of the architecture of the entire AI the strategic decision making sits at the top, below it is the sequencing of events to figure out paths that serve the strategic goals, which in turn depends on the pathfinder to supply the information which objects are accessible and how long it takes to reach these, and at the bottom are a lot of basic but vital functions that retrieve, assemble and efficiently structure the data needed for all these tasks.
Today we start with an overview how the data structures necessary for a powerful pathfinder can be implemented. I will also explain how you can make good use of C++ to get this work done and give you an idea how you can structure your programs.
Once we have this firmly in place, we can move on to the next topic, how the pathfinder in Heroes III was implemented.
This first part covers efficient data structures. When I wrote this article and then reviewed it, I realized that the following code samples and my brief explanations aren't easily approachable for beginners. It's tough reading and you have to make yourself familiar with a lot of concepts in a very compact format. But you can learn a lot from this, techniques, design and coding practice, but most importantly it is a good preparation to building a professional pathfinder. If you are a pro or seasoned C++ programmer the concepts should be straightforward to grasp.
So bear with me if you like to know more about the internals of the pathfinder used in connection with the advanced AI.
Structured data
Ideally we want to write code in such a style that it is self-documenting and requires minimal auxiliary comment.
Let's start with a simple structure that defines the skills of a hero, how these are handled internally by the AI, in Heroes V.
/*----------------------------------------------------------------
struct HeroSkills
------------------------------------------------------------------*/
public:
struct HeroSkills
{
union
{
unsigned long flags ;
struct {
unsigned nativeTerrain : 8 ;
unsigned heroLevel : 8 ;
unsigned bIsPathfinder : 1 ;
unsigned bIsTracker : 1 ;
unsigned bHasSnatchSkill : 1 ;
unsigned bHasWayfarerBoots : 1 ;
unsigned bBattleBonusMove : 1 ;
unsigned bKnowsMysticism : 1 ;
unsigned bCanCastTownPortal : 1 ;
unsigned bCanCastTeleport : 1 ;
unsigned bCanSummonBoat : 1 ;
unsigned bCanCastAnySpells : 1 ;
unsigned maxSpellLevel : 3 ;
unsigned unused : 3 ;
};
};
unsigned short nDimensionDoorMoveCost ;
unsigned short nMovePointsMaxCurrent ;
long heroPowerBase ;
HeroSkills() : flags(0) {}
#ifndef STRATEGIC_AI_PROCESS
HeroSkills( IHero* hero ) { init( hero ); }
/*============== public methods ==============*/
void init( IHero* hero )
{
flags = 0 ;
if( ! IsValid( hero ) ) return ;
const SSpellInfo dimensionDoor( NDb::SPELL_DIMENSION_DOOR );
const SSpellInfo summonBoat( NDb::SPELL_SUMMON_BOAT );
const SSpellInfo townPortal( NDb::SPELL_TOWN_PORTAL );
nativeTerrain = 1 << MoveCost::getNativeTerrain( hero );
heroLevel = hero->GetLevel() ;
heroPowerBase = cHeroPowerBase + ( heroLevel - 1 ) * cHeroPowerIncPerLevel ;
bIsPathfinder = hero->GetSkillTrained( NDb::HERO_SKILL_PATHFINDING ) > NWorld::SKILL_MASTERY_NONE ;
bIsTracker = hero->HasSpecialization( NDb::HERO_SPEC_RASH );
bHasSnatchSkill = hero->GetSkillTrained( NDb::HERO_SKILL_SNATCH ) > NWorld::SKILL_MASTERY_NONE ;
bHasWayfarerBoots = hero->GetPutonArtifacts().Has( NDb::WAYFARER_BOOTS );
bBattleBonusMove = hero->GetSkillTrained( NDb::HERO_SKILL_PATH_OF_WAR ) > NWorld::SKILL_MASTERY_NONE ;
bKnowsMysticism = hero->GetSkillTrained( NDb::HERO_SKILL_MYSTICISM ) > NWorld::SKILL_MASTERY_NONE ;
bCanCastTeleport = hero->IsSpellKnown( dimensionDoor.eSpell ) && hero->CanCastSpell( dimensionDoor );
nDimensionDoorMoveCost = bCanCastTeleport ? hero->GetMovePointsMaxCurrent() / 2 : cMaxStateDistance ;
bCanSummonBoat = hero->IsSpellKnown( summonBoat.eSpell ) && hero->CanCastSpell( summonBoat );
bCanCastTownPortal = hero->IsSpellKnown( townPortal.eSpell );
bCanCastAnySpells = ! hero->GetSpells().empty() ;
nMovePointsMaxCurrent = hero->GetMovePointsMaxCurrent() ;
setMaxSpellLevel( hero );
}
void setMaxSpellLevel( IHero* hero )
{
maxSpellLevel = 2 ;
if( hero->GetSkillTrained( NDb::HERO_SKILL_WISDOM ) )
maxSpellLevel = 3 ;
updateMaxSpellLevel( hero, NDb::HERO_SKILL_DESTRUCTIVE_MAGIC );
updateMaxSpellLevel( hero, NDb::HERO_SKILL_DARK_MAGIC );
updateMaxSpellLevel( hero, NDb::HERO_SKILL_LIGHT_MAGIC );
updateMaxSpellLevel( hero, NDb::HERO_SKILL_SUMMONING_MAGIC );
if( maxSpellLevel < 3 && (NDb::TOWN_STRONGHOLD == hero->GetHeroTown()) )
maxSpellLevel = 1 ;
}
void updateMaxSpellLevel( IHero* hero, NDb::ESkillID eMagicSchool )
{
unsigned char nSchoolSpellLevel = 2 + hero->GetSkillTrained( eMagicSchool );
if( maxSpellLevel < nSchoolSpellLevel )
maxSpellLevel = nSchoolSpellLevel ;
}
#endif
}; // struct HeroSkills
This is a compact struct to maintain relevant data efficiently in a single place and make the code more reliable and readable. The preprocessor constant STRATEGIC_AI_PROCESS allows the same code to be used in two processes, of which only one provides the context for initialization while the second uses the data. Such a struct can be passed between processes.
It also demonstrates that in C++ you can store data with the efficiency of assembler while still maintaining well structured code.
If you are familiar with the game, you will note that the HeroSkills struct holds most of the information a pathfinder needs to calculate the movement costs for a hero to move across the map, amongst other things the nativeTerrain and bIsPathfinder flag.
The next example demonstrates techniques that you can use to process the movement cost on a tile based map. These are typical techniques to define the movement mechanics independently of the pathfinder itself.
/*----------------------------------------------------------------
struct TMoveCost
------------------------------------------------------------------*/
enum TerrainClass {
__plain = 1,
__dirt = 2,
__lava = 4,
__sand = 8,
__snow = 16,
__subterranean = 32,
__taiga = 64,
__road = 128
};
enum TerrainClassIndex {
__plain__ = 0,
__dirt__,
__lava__,
__sand__,
__snow__,
__subterranean__,
__taiga__,
__road__,
__terrainCnt__
};
static const unsigned short cTerrainMask = 0x00ff ;
enum Directions { N = 1, NE = 2, E = 4, SE = 8, S = 16, SW = 32, W = 64, NW = 128 };
static const unsigned int north = NW | N | NE ;
static const unsigned int east = NE | E | SE ;
static const unsigned int south = SE | S | SW ;
static const unsigned int west = SW | W | NW ;
static const unsigned long neighborBits = 0x000000ff ;
struct TMoveCost
{
unsigned short moveCost ;
/*============== construction ==============*/
TMoveCost()
{
}
TMoveCost( unsigned short _moveCost )
{
moveCost = _moveCost ;
}
/*============== public methods ==============*/
void clear()
{
moveCost = 0 ;
}
TMoveCost& operator+= ( const TMoveCost& _m )
{
moveCost += _m.moveCost ;
return *this ;
}
TMoveCost& operator= ( unsigned short _moveCost )
{
moveCost = _moveCost ;
return *this ;
}
TMoveCost operator+ ( const TMoveCost& _m )
{
TMoveCost tmp = _m ;
return tmp += *this ;
}
bool Improve( TMoveCost& improved )
{
if( improved.moveCost < moveCost )
{
moveCost = improved.moveCost ;
return true ;
}
return false ;
}
void adjustMinimumDistance()
{
if( ! moveCost ) moveCost = 32 ;
}
unsigned char moveCost64() const
{
return moveCost64( moveCost );
}
static unsigned char moveCost64( unsigned short c )
{
if( c & 0xc000 ) return 255 ;
else if( c & 0x2000 );
else c += 32 ;
return c >> 6 ;
}
static unsigned short fullMoveCost( unsigned char c )
{
return c << 6 ;
}
void dump() const
{
aiLogger() << (int)moveCost << endl ;
}
}; // struct TMoveCost
/*----------------------------------------------------------------
struct MoveCost
------------------------------------------------------------------*/
struct MoveCost
{
union
{
unsigned long flags ;
struct {
unsigned pathThroughNeighbor : 16 ;
unsigned nShortestPath : 8 ;
unsigned zeroThreatPath : 1 ;
unsigned noTriggersInPath : 1 ;
unsigned unused : 6 ;
};
};
TMoveCost m[ __terrainCnt__ ];
/*============== static const & variables ==============*/
static MoveCost nilMoveCost ;
/*============== construction ==============*/
MoveCost() {}
MoveCost( unsigned short c, unsigned long _flags = 0 ) { flags = _flags ; set( c ); }
/*============== static methods ==============*/
#ifndef STRATEGIC_AI_PROCESS
static TerrainClassIndex getNativeTerrain( IHero* hero )
{
if( ! IsValid( hero ) ) return __plain__ ;
TerrainClassIndex nativeTerrain ;
switch( hero->GetInfo().eTownType )
{
case NDb::TOWN_ACADEMY:
nativeTerrain = __sand__ ;
break;
case NDb::TOWN_DUNGEON:
nativeTerrain = __subterranean__ ;
break;
case NDb::TOWN_NECROMANCY:
nativeTerrain = __dirt__ ;
break;
case NDb::TOWN_INFERNO:
nativeTerrain = __lava__ ;
break;
case NDb::TOWN_FORTRESS:
nativeTerrain = __snow__ ;
break;
case NDb::TOWN_STRONGHOLD:
nativeTerrain = __taiga__ ;
break;
case NDb::TOWN_HEAVEN:
case NDb::TOWN_PRESERVE:
default:
nativeTerrain = __plain__ ;
} // switch( hero->GetInfo().eTownType )
return nativeTerrain ;
}
#endif
/*============== public methods ==============*/
void assign(
MoveCost& accumulated,
unsigned char terrain,
unsigned char iNeighbor
) {
bool bShortMove = iNeighbor & ( N | E | S | W ) ;
TMoveCost terrainMoveCost( bShortMove ? getMoveCost( terrain ) : getMoveCostDiag( terrain ) );
TMoveCost nativeMoveCost( bShortMove ? 100 : 141 );
m[__plain__] = accumulated.m[__plain__] + terrainMoveCost ;
m[__dirt__] = accumulated.m[__dirt__] + (terrain & __dirt ? nativeMoveCost : terrainMoveCost) ;
m[__lava__] = accumulated.m[__lava__] + (terrain & __lava ? nativeMoveCost : terrainMoveCost) ;
m[__sand__] = accumulated.m[__sand__] + (terrain & __sand ? nativeMoveCost : terrainMoveCost) ;
m[__snow__] = accumulated.m[__snow__] + (terrain & __snow ? nativeMoveCost : terrainMoveCost) ;
m[__subterranean__] = accumulated.m[__subterranean__] + (terrain & __subterranean ? nativeMoveCost : terrainMoveCost) ;
m[__taiga__] = accumulated.m[__taiga__] + (terrain & __taiga ? nativeMoveCost : terrainMoveCost) ;
m[__road__] = accumulated.m[__road__] + (terrain & ~__road ? nativeMoveCost : terrainMoveCost) ;
nShortestPath = accumulated.nShortestPath + 1 ;
}
unsigned char add(
MoveCost& accumulated,
unsigned char terrain,
unsigned char iNeighbor,
unsigned char active
) {
bool bShortMove = iNeighbor & ( N | E | S | W ) ;
TMoveCost terrainMoveCost( bShortMove ? getMoveCost( terrain ) : getMoveCostDiag( terrain ) );
TMoveCost nativeMoveCost( bShortMove ? 100 : 141 );
if( active & __plain
&& ! m[__plain__].Improve( accumulated.m[__plain__] + terrainMoveCost ) )
active &= ~__plain ;
if( active & __dirt
&& ! m[__dirt__].Improve( accumulated.m[__dirt__] + (terrain & __dirt ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__dirt ;
if( active & __lava
&& ! m[__lava__].Improve( accumulated.m[__lava__] + (terrain & __lava ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__lava ;
if( active & __sand
&& ! m[__sand__].Improve( accumulated.m[__sand__] + (terrain & __sand ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__sand ;
if( active & __snow
&& ! m[__snow__].Improve( accumulated.m[__snow__] + (terrain & __snow ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__snow ;
if( active & __subterranean
&& ! m[__subterranean__].Improve( accumulated.m[__subterranean__]
+ (terrain & __subterranean ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__subterranean ;
if( active & __taiga
&& ! m[__taiga__].Improve( accumulated.m[__taiga__] + (terrain & __taiga ? nativeMoveCost : terrainMoveCost) ) )
active &= ~__taiga ;
if( active & __road )
{
if( m[__road__].Improve( accumulated.m[__road__] + (terrain & ~__road ? nativeMoveCost : terrainMoveCost) ) )
nShortestPath = accumulated.nShortestPath + 1 ;
else
active &= ~__road ;
}
return active ;
}
void assign(
MoveCost& accumulated,
MoveCost& distance
) {
m[__plain__] = accumulated.m[__plain__] + distance.m[__plain__] ;
m[__dirt__] = accumulated.m[__dirt__] + distance.m[__dirt__] ;
m[__lava__] = accumulated.m[__lava__] + distance.m[__lava__] ;
m[__sand__] = accumulated.m[__sand__] + distance.m[__sand__] ;
m[__snow__] = accumulated.m[__snow__] + distance.m[__snow__] ;
m[__subterranean__] = accumulated.m[__subterranean__] + distance.m[__subterranean__] ;
m[__taiga__] = accumulated.m[__taiga__] + distance.m[__taiga__] ;
m[__road__] = accumulated.m[__road__] + distance.m[__road__] ;
nShortestPath = accumulated.nShortestPath + distance.nShortestPath ;
}
unsigned char add(
MoveCost& accumulated,
MoveCost& distance,
unsigned char active
) {
if( active & __plain
&& ! m[__plain__].Improve( accumulated.m[__plain__] + distance.m[__plain__] ) )
active &= ~__plain ;
if( active & __dirt
&& ! m[__dirt__].Improve( accumulated.m[__dirt__] + distance.m[__dirt__] ) )
active &= ~__dirt ;
if( active & __lava
&& ! m[__lava__].Improve( accumulated.m[__lava__] + distance.m[__lava__] ) )
active &= ~__lava ;
if( active & __sand
&& ! m[__sand__].Improve( accumulated.m[__sand__] + distance.m[__sand__] ) )
active &= ~__sand ;
if( active & __snow
&& ! m[__snow__].Improve( accumulated.m[__snow__] + distance.m[__snow__] ) )
active &= ~__snow ;
if( active & __subterranean
&& ! m[__subterranean__].Improve( accumulated.m[__subterranean__] + distance.m[__subterranean__] ) )
active &= ~__subterranean ;
if( active & __taiga
&& ! m[__taiga__].Improve( accumulated.m[__taiga__] + distance.m[__taiga__] ) )
active &= ~__taiga ;
if( active & __road )
{
if( m[__road__].Improve( accumulated.m[__road__] + distance.m[__road__] ) )
nShortestPath = accumulated.nShortestPath + distance.nShortestPath ;
else
active &= ~__road ;
}
#ifdef STRATEGIC_AI_DBG_MOVECOST
aiLogger() << " ~" << print8Bit( active ) << "~ ";
#endif
return active ;
}
void assignZeroThreat(
unsigned char _nShortestPath,
unsigned short distance,
TerrainClassIndex _terrain_
) {
m[_terrain_].moveCost = distance ;
zeroThreatPath = true ;
nShortestPath = _nShortestPath ;
}
bool addZeroThreat(
unsigned char _nShortestPath,
unsigned short distance,
TerrainClassIndex _terrain_
) {
if( distance < m[_terrain_].moveCost )
{
m[_terrain_].moveCost = distance ;
zeroThreatPath = true ;
nShortestPath = _nShortestPath ;
return true ;
}
return false ;
}
static unsigned short getHeroMoveCost( unsigned char terrain, bool bShortMove, HeroSkills heroSkills, int pathfinderSkill )
{
MoveCost c ;
if( terrain == __plain );
else if( terrain == __road );
else if( heroSkills.bHasWayfarerBoots || terrain == heroSkills.nativeTerrain ) terrain = __plain ;
else if( pathfinderSkill )
{
unsigned short nMoveCost = bShortMove ? 100 : 141 ;
unsigned short nExtraCost = terrain & (__sand | __snow ) ? (bShortMove ? 50 : 71) : (bShortMove ? 25 : 35 );
return nMoveCost + nExtraCost * ( 1.f - pathfinderSkill / 100.f ) ;
}
return bShortMove ? c.getMoveCost( terrain ) : c.getMoveCostDiag( terrain );
}
static unsigned short getMoveCost( unsigned char terrain )
{
if( terrain & __plain ) return 100 ;
if( terrain & __road ) return 75 ;
if( terrain & (__sand | __snow ) ) return 150 ;
return 125 ;
}
static unsigned short getMoveCostDiag( unsigned char terrain )
{
if( terrain & __plain ) return 141 ;
if( terrain & __road ) return 106 ;
if( terrain & (__sand | __snow ) ) return 212 ;
return 176 ;
}
unsigned short Min( MoveCost& c )
{
unsigned short changed = 0 ;
if( m[__plain__].Improve ( c.m[__plain__] ) ) changed |= __plain ;
if( m[__dirt__].Improve ( c.m[__dirt__] ) ) changed |= __dirt ;
if( m[__lava__].Improve ( c.m[__lava__] ) ) changed |= __lava ;
if( m[__sand__].Improve ( c.m[__sand__] ) ) changed |= __sand ;
if( m[__snow__].Improve ( c.m[__snow__] ) ) changed |= __snow ;
if( m[__subterranean__].Improve( c.m[__subterranean__] ) ) changed |= __subterranean ;
if( m[__taiga__].Improve ( c.m[__taiga__] ) ) changed |= __taiga ;
if( m[__road__].Improve ( c.m[__road__] ) ) changed |= __road ;
return changed ;
}
void adjustMinimumDistance()
{
for( unsigned short i = 0 ; i < __terrainCnt__ ; i++ ) m[ i ].adjustMinimumDistance() ;
}
void getZeroThreatMoveCostEstimate( unsigned char estimate[] ) const
{
*estimate++ = zeroThreatPath ? m[__plain__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__dirt__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__lava__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__sand__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__snow__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__subterranean__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__taiga__].moveCost64() : 0 ;
*estimate++ = zeroThreatPath ? m[__road__].moveCost64() : 0 ;
}
void set( unsigned short c )
{
m[__plain__] = c ;
m[__dirt__] = c ;
m[__lava__] = c ;
m[__sand__] = c ;
m[__snow__] = c ;
m[__subterranean__] = c ;
m[__taiga__] = c ;
m[__road__] = c ;
}
void clear()
{
m[__plain__] = 0 ;
m[__dirt__] = 0 ;
m[__lava__] = 0 ;
m[__sand__] = 0 ;
m[__snow__] = 0 ;
m[__subterranean__] = 0 ;
m[__taiga__] = 0 ;
m[__road__] = 0 ;
nShortestPath = 0 ;
}
void dumpMoveCost() const
{
aiLogger() << "plain : " ; m[__plain__].dump() ;
aiLogger() << "dirt : " ; m[__dirt__].dump() ;
aiLogger() << "lava : " ; m[__lava__].dump() ;
aiLogger() << "sand : " ; m[__sand__].dump() ;
aiLogger() << "snow : " ; m[__snow__].dump() ;
aiLogger() << "subterranean : " ; m[__subterranean__].dump() ;
aiLogger() << "snow : " ; m[__taiga__].dump() ;
aiLogger() << "unhindered : " ; m[__road__].dump() ;
aiLogger() << "nShortestPath : " << (int)nShortestPath << endl ;
aiLogger() << "zeroThreatPath : " << (int)zeroThreatPath << endl ;
aiLogger() << "noTriggersInPath: " << (int)noTriggersInPath << endl ;
}
}; // struct moveCost
/*----------------------------------------------------------------
struct MoveCostEstimate
------------------------------------------------------------------*/
struct MoveCostEstimate
{
unsigned char moveCost[ __terrainCnt__ ];
/*============== public methods ==============*/
MoveCostEstimate& operator+= ( const MoveCostEstimate& c )
{
for( unsigned short i = 0 ; i < __terrainCnt__ ; i++ ) moveCost[i] += c.moveCost[i] ;
return *this ;
}
MoveCostEstimate operator+ ( const MoveCostEstimate& c )
{
MoveCostEstimate tmp = *this ;
return tmp += c ;
}
bool operator<= ( unsigned short c )
{
return moveCost[__road__] <= c ;
}
unsigned short improve( MoveCost& distance, unsigned short terrain, bool bSetFlagIfEqual = false )
{
MoveCostEstimate tmp ;
unsigned char* p ;
unsigned char* t ;
unsigned short iTerrain ;
unsigned short update = 0 ;
if( distance.zeroThreatPath )
{
distance.getZeroThreatMoveCostEstimate( tmp.moveCost );
p = moveCost + __road__ ;
t = tmp.moveCost + __road__ ;
for( iTerrain = __road ; iTerrain ; iTerrain >>= 1, --p, --t )
{
if( terrain & iTerrain )
{
if( *t < *p )
{
*p = *t ;
update |= iTerrain ;
}
else if( bSetFlagIfEqual && *t == *p )
update |= iTerrain ;
}
}
}
return update ;
}
void set( unsigned char dist )
{
for( unsigned short i = 0 ; i < __terrainCnt__ ; i++ ) moveCost[i] = dist ;
}
void maximum()
{
set( 0xff );
}
void zero()
{
ZeroMemory( moveCost, __terrainCnt__ );
}
}; // struct MoveCostEstimate
Note that the MoveCost is optimized for the accurate calculation of large movement costs, whereas the MoveCostEstimate is more compact and optimized for quick estimates. The difference in practice can easily be a factor 2 to 10 in performance, depending on the size of tile maps, processor cache, and memory bus speed. Imagine that a high duty pathfinder has to process millions of distances a second.
In general good use of constants and a smart C++ class partition is required to implement a complex movement logic (terrain and hero skills affect movement cost) by lightweight, efficient and easy to maintain code.
The tile information itself, FastMoveTile, is stored also in a highly compact format:
struct FastMoveTile /* tile information customized for fast movement computation */
{
union
{
unsigned long flags ;
struct {
unsigned neighbors : 8 ;
unsigned threatLevel : 4 ;
unsigned bIsUnderground : 1 ;
unsigned bHasAnyWater : 1 ;
unsigned bDeepWater : 1 ;
unsigned bIsBlocked : 1 ;
unsigned bIsHeroHolder : 1 ;
unsigned bIsMonster : 1 ; // neutral creatures on the adventure map, or stationary hero
unsigned bIsTrigger : 1 ; // monster/borderguard trigger or interactive blocked
unsigned bHasCollectable : 1 ;
unsigned bInteractiveBlocked : 1 ;
unsigned bIsRoad : 1 ;
unsigned ttDirt : 1 ;
unsigned ttGrass : 1 ;
unsigned ttSand : 1 ;
unsigned ttSnow : 1 ;
unsigned ttLava : 1 ;
unsigned ttSubterranean : 1 ;
unsigned ttDwarvenMines : 1 ;
unsigned ttTaiga : 1 ;
unsigned ttWasteland : 1 ;
unsigned bFixedBorder : 1 ;
};
};
union
{
unsigned long extFlags ;
struct {
unsigned iBorderTile : 16 ; // TO DO: communicate 64K limit properly
unsigned ownerTileID : 8 ;
unsigned bIsBorderGuard : 1 ;
unsigned bIsAdvObjectMajor : 1 ;
unsigned bIsTeleporter : 1 ;
unsigned bIsDock : 1 ;
unsigned bIsLandWaterBorder : 1 ;
unsigned bStationaryHero : 1 ;
#ifdef STRATEGIC_AI_DBG
unsigned bIsBorder : 1 ;
#endif
unsigned bIsGarrison : 1 ;
};
};
unsigned short advEventID ;
unsigned short x ;
unsigned short y ;
unsigned short idAreaState ;
// threat range is a square
// monsters and heroes threaten adjacent cells
// garrison cell isn't threatened from neighboring cells
// garrison doesn't threaten neighboring cells
// ships don't threaten neighboring cells
/*============== construction ==============*/
FastMoveTile() ;
/*============== operators ==============*/
//FastMoveTile& operator= ( const STileGameInfo& t );
/*============== static functions ==============*/
static FastMoveTile* FindNoEventTile( unsigned char& tileID, FastMoveTile** tiles, unsigned short cnt );
static unsigned char GetNeighborReverse( unsigned char iNeighbor );
static unsigned char GetDirection( unsigned char iNeighbor );
/*============== public methods ==============*/
#ifndef STRATEGIC_AI_PROCESS
FastMoveTile& init( IWorld* pWorld, const STileGameInfo& t, bool _bIsUnderground );
#endif
SAdventureCell GetCellPosition() { return SAdventureCell( x, y, bIsUnderground ); }
bool IsAdvObjectMajor() ;
bool IsAdvObjectMajorExt() ;
bool IsAdvObjectMajorNoHolder() ;
bool IsTown() ;
bool IsGarrison() ;
bool IsTeleporter() ;
bool IsTrigger() ;
bool IsInteractiveBlockedTile() ;
bool IsShieldedFromThreat() ;
#ifndef STRATEGIC_AI_PROCESS
bool UpdateDock( IWorld* pWorld, unsigned short shipyardEventID );
bool UpdateTown( IWorld* pWorld, IAdvMapTown* town );
void AddTeleportExits( IWorld* pWorld );
bool UpdateMobileObject( IWorld* pWorld, IAdvMapObject* obj, bool bRegisterThreatObjects, bool bRegisterNoThreatObjects, bool bFlagEventCache );
bool ValidateMobileObject( IAdvMapObject* obj );
bool RemoveMobileObject() ;
void RemoveBorderGuard() ;
#endif
unsigned char GetGarrisonNeighborsAtSide( int nSide );
unsigned char GetGarrisonNeighborsAtSide( FastMoveTile* tn );
TerrainClassIndex getTerrainClassIndex() ;
TerrainClass getTerrainClass() ;
void UpdateThreatLevel( bool bRemoveBorderGuard = false );
unsigned char UpdateNeighborsMonsterTrigger( bool bSignalChange = false, bool bSignalChangeMajor = false );
bool IsBorderGuardKeyMaster( FastMoveTile* borderGuard );
bool IsMobile() ;
FastMoveTile* IsThreatOfNeighboringMonsterWithPrecedence( FastMoveTile* origin );
FastMoveTile* GetNeighboringBorderGuard() ;
FastMoveTile* GetNeighboringMonster( FastMoveTile* ignored = NULL );
FastMoveTile* GetNeighboringMobile( FastMoveTile* ignored = NULL );
unsigned char GetNeighborRelationUnblocked( FastMoveTile* tn );
unsigned char GetNeighborRelation( FastMoveTile* tn );
bool IsNeighbor( FastMoveTile* tn ) const ;
void GetNeighbors() ;
void GetAdjacentTargets( vector<SAdventureCell>* adjacentTargets );
unsigned short GetCollectables( FastMoveTile** collectables, unsigned short maxCollectables );
FastMoveTile* GetNeighbor( unsigned char iNeighbor );
FastMoveTile* getN () { return this - nXSize ; }
FastMoveTile* getNE() { return this - nXSize + 1 ; }
FastMoveTile* getE () { return this + 1 ; }
FastMoveTile* getSE() { return this + nXSize + 1 ; }
FastMoveTile* getS () { return this + nXSize ; }
FastMoveTile* getSW() { return this + nXSize - 1 ; }
FastMoveTile* getW () { return this - 1 ; }
FastMoveTile* getNW() { return this - nXSize - 1 ; }
void dumpTileInfo( bool bEndLine = true );
/*============== helpers ==============*/
private:
unsigned short GetAdjacentCollectables( unsigned short id, FastMoveTile** collectables, unsigned short maxCollectables );
}; // struct FastMoveTile
In the next snippet of code this information is put to use to check for threats on neighboring tiles.
aiAreaState::FastMoveTile* aiAreaState::FastMoveTile::GetNeighboringMonster( FastMoveTile* ignored )
{
FastMoveTile* monster = NULL ;
for( unsigned char iNeighbor = N ; iNeighbor ; iNeighbor <<= 1 )
if( neighbors & iNeighbor )
{
FastMoveTile* tn = GetNeighbor( iNeighbor );
if( tn->bIsMonster && tn->advEventID
&& ( ! monster || tn->threatLevel > monster->threatLevel ) && ( ! ignored || ignored != tn ) )
monster = tn ;
}
return monster ;
}
bool aiAreaState::FastMoveTile::IsNeighbor( FastMoveTile* tn )
{
if( tn->bIsUnderground != bIsUnderground ) return false ;
short dx = tn->x - x ;
short dy = tn->y - y ;
if( dx > 1 || dx < -1 ) return false ;
if( dy > 1 || dy < -1 ) return false ;
return true ;
}
void aiAreaState::FastMoveTile::GetNeighbors()
{
unsigned short neighbors = 0x00ff ;
if( y == 0 ) neighbors &= ~north ;
if( y == nYSize - 1 ) neighbors &= ~south ;
if( x == 0 ) neighbors &= ~west ;
if( x == nXSize - 1 ) neighbors &= ~east ;
if( neighbors & N )
{
if( (this - nYSize)->bIsBlocked ) neighbors &= ~N ;
}
if( neighbors & NE )
{
if( (this - nYSize + 1)->bIsBlocked ) neighbors &= ~NE ;
}
if( neighbors & E )
{
if( (this + 1)->bIsBlocked ) neighbors &= ~E ;
}
if( neighbors & SE )
{
if( (this + nYSize + 1)->bIsBlocked ) neighbors &= ~SE ;
}
if( neighbors & S )
{
if( (this + nYSize)->bIsBlocked ) neighbors &= ~S ;
}
if( neighbors & SW )
{
if( (this + nYSize - 1)->bIsBlocked ) neighbors &= ~SW ;
}
if( neighbors & W )
{
if( (this - 1)->bIsBlocked ) neighbors &= ~W ;
}
if( neighbors & NW )
{
if( (this - nYSize - 1)->bIsBlocked ) neighbors &= ~NW ;
}
FastMoveTile::neighbors = neighbors ;
}
aiAreaState::FastMoveTile* aiAreaState::FastMoveTile::GetNeighbor( unsigned char iNeighbor )
{
FastMoveTile* tn = this ;
if( iNeighbor & north )
tn -= nYSize ;
else if( iNeighbor & south )
tn += nYSize ;
if( iNeighbor & east )
tn += 1 ;
else if( iNeighbor & west )
tn -= 1 ;
return tn ;
}
void aiAreaState::FastMoveTile::UpdateThreatLevel( bool bRemoveBorderGuard )
{
if( bRemoveBorderGuard )
bIsBorderGuard = false ;
if( bIsBorderGuard )
threatLevel = cMaxThreatLevel ;
else
{
FastMoveTile* nmonster = GetNeighboringMonster() ;
threatLevel = nmonster ? nmonster->threatLevel : 0 ;
}
bIsTrigger = IsTrigger() ;
}
unsigned char aiAreaState::FastMoveTile::UpdateNeighborsMonsterTrigger( bool bSignalChange )
{
unsigned char affectedNeighbors = 0x00 ;
for( unsigned char iNeighbor = N ; iNeighbor ; iNeighbor <<= 1 )
{
if( neighbors & iNeighbor )
{
FastMoveTile* tn = GetNeighbor( iNeighbor );
if( tn->bIsMonster || tn->bIsBorderGuard ) continue ;
unsigned char nneighbors = tn->neighbors ;
unsigned char newThreatLevel = 0 ;
for( unsigned char iiNeighbor = N ; iiNeighbor ; iiNeighbor <<= 1 )
if( nneighbors & iiNeighbor )
{
FastMoveTile* tnn = tn->GetNeighbor( iiNeighbor );
if( tnn->bIsMonster )
{
if( tnn->threatLevel > newThreatLevel ) newThreatLevel = tnn->threatLevel ;
}
}
if( bSignalChange && tn->threatLevel != newThreatLevel && tn->bFixedBorder )
affectedNeighbors |= iNeighbor ;
tn->threatLevel = newThreatLevel ;
tn->bIsTrigger = tn->IsTrigger() ;
} // if( neighbors & iNeighbor )
} // for( unsigned char iNeighbor = N ; iNeighbor ; iNeighbor <<= 1 )
return affectedNeighbors ;
}
void aiAreaState::FastMoveTile::GetAdjacentTargets( vector<SAdventureCell>* adjacentTargets )
{
for( unsigned char iNeighbor = N ; iNeighbor ; iNeighbor <<= 1 )
if( neighbors & iNeighbor )
{
FastMoveTile* tn = GetNeighbor( iNeighbor );
if( tn->bHasCollectable )
{
adjacentTargets->push_back( SAdventureCell( tn->x, tn->y, tn->bIsUnderground ) );
}
}
}It is a functional example how adventure map logic benefits from sound logical partition and how small methods complement each other to perform more complex detection and evaluation, while at the same time resulting in code easy to read and maintain. The adventure map consists of a contiguous two-dimensional array of lightweight FastMoveTile objects. The array can hold two floors (surface and underground) and the map has a size of nXSize * nYSize.
The next code sample gives you an idea how the tile data and the movement cost are connected with evaluating the significance of a path.
/*----------------------------------------------------------------
struct ShortPath
------------------------------------------------------------------*/
struct ShortPath
{
/* ... */
long value ;
long kamikazee ;
unsigned short movePoints ;
unsigned short mana ;
unsigned short manaMax ;
bool bCriticalPosition ;
bool bMaintainStrategicPresence ;
bool bPositionFinal ;
bool bProcessed ;
bool bSimulated ;
unsigned char allies ;
BIT__KEY keys ;
HeroArmyStack army ;
HeroSkills heroSkills ;
SMoney available ;
SMoney income ;
/*============== public methods ==============*/
/* ... */
bool hasBetterTravelValue( ShortPath& from, long eventValue, unsigned short travelCost, unsigned short minValuePerTravel,
long eventKamikazee ) const
{
#ifdef STRATEGIC_AI_DETAILEDDBGEVENTTRACE
if( debug.eventQueue ) aiLogger() << "bProcessed = " << (int)bProcessed << endl ;
#endif
if( ! bProcessed ) return true ;
if( eventKamikazee )
return kamikazee && eventKamikazee > kamikazee ;
else if( kamikazee )
return true ;
short newRemainingMovePoints = TMoveCost::moveCost64( from.movePoints - travelCost );
short currentRemainingMovePoints = TMoveCost::moveCost64( movePoints );
long gain = from.value + eventValue - value ;
long ceiling = ( minValuePerTravel << 2 ) * (currentRemainingMovePoints - newRemainingMovePoints) ;
#ifdef STRATEGIC_AI_DETAILEDDBGEVENTTRACE
if( debug.eventQueue )
{
aiLogger() << "from.value = " << (int)from.value << ", eventValue = " << (int)eventValue << ", value = "
<< (int)value << endl ;
aiLogger() << "currentRemainingMovePoints = " << (int)currentRemainingMovePoints << ", newRemainingMovePoints = "
<< (int)newRemainingMovePoints << endl ;
aiLogger() << "gain = " << (int)gain << ", ceiling = " << (int)ceiling << ", improved = " << (int)(gain > ceiling)
<< endl ;
}
#endif
bool bResult = gain > ceiling ;
#ifdef STRATEGIC_AI_DETAILEDDBGEVENTTRACE
if( debug.eventQueue ) aiLogger() << "bResult = " << (int)bResult << endl ;
#endif
return bResult ;
}
bool hasHigherTravelValue( ShortPath& from, long eventValue, unsigned short travelCost ) const
{
if( ! bProcessed ) return true ;
return from.value + eventValue > value
|| from.value + eventValue == value && from.movePoints - travelCost > movePoints ;
}
bool improve( ShortPath& alternatePath ) const
{
if( debug.eventQueue )
{
aiLogger() << "ShortPath::improve(), present = " << (bProcessed ? value : cLowestStrategicValue)
<< ", alternatePath.value = " << (int)alternatePath.value
<< ", alternatePath.movePoints = " << alternatePath.movePoints ;
}
if( alternatePath.kamikazee )
return ! bProcessed || kamikazee && alternatePath.kamikazee > kamikazee ;
if( ! bProcessed
|| alternatePath.value > value
|| alternatePath.value == value && alternatePath.movePoints > movePoints
|| kamikazee )
{
if( debug.eventQueue ) aiLogger() << " improved" << endl ;
return true ;
}
if( debug.eventQueue ) aiLogger() << " skipped" << endl ;
return false ;
}
}; // struct ShortPath
/*----------------------------------------------------------------
class AdvObjectBase
------------------------------------------------------------------*/
enum AdvMapEventType
{
AdvMapEvent_None = 0x00000000,
AdvMapEvent_Town = 0x00000001,
AdvMapEvent_Garrison = 0x00000002,
AdvMapEvent_Sanctuary = 0x00000004,
AdvMapEvent_Teleporter = 0x00000008,
AdvMapEvent_Exit = 0x00000010,
AdvMapEvent_Stables = 0x00000020,
AdvMapEvent_RallyFlag = 0x00000040,
AdvMapEvent_FountainOfYouth = 0x00000080,
AdvMapEvent_Oasis = 0x00000100,
AdvMapEvent_Shipyard = 0x00000200,
AdvMapEvent_Lighthouse = 0x00000400,
AdvMapEvent_MagicWell = 0x00000800,
AdvMapEvent_MagicSpring = 0x00001000,
AdvMapEvent_HillFort = 0x00002000,
AdvMapEvent_WarMachineFactory = 0x00004000,
AdvMapEvent_TradingPost = 0x00008000,
AdvMapEvent_Dock = 0x00010000,
AdvMapEvent_BorderGuard = 0x01000000,
AdvMapEvent_Monster = 0x20000000,
AdvMapEvent_Artifact = 0x40000000,
AdvMapEvent_Treasure = 0x80000000
};
static const unsigned long AdvMapEvent_Removable = AdvMapEvent_Monster | AdvMapEvent_Artifact | AdvMapEvent_Treasure
| AdvMapEvent_BorderGuard ;
static const unsigned long AdvMapEvent_PreBattle = AdvMapEvent_RallyFlag | AdvMapEvent_FountainOfYouth | AdvMapEvent_Oasis ;
static const unsigned long isAdvObjectMajor = AdvMapEvent_Town | AdvMapEvent_Garrison | AdvMapEvent_Sanctuary
| AdvMapEvent_Teleporter | AdvMapEvent_Exit | AdvMapEvent_Dock ;
static const unsigned long isAdvObjectHolder = AdvMapEvent_Exit | AdvMapEvent_Dock ;
static const unsigned long isMoveBoost = AdvMapEvent_Stables | AdvMapEvent_RallyFlag | AdvMapEvent_FountainOfYouth
| AdvMapEvent_Oasis ;
static const unsigned long isMagicBoost = AdvMapEvent_MagicWell | AdvMapEvent_MagicSpring ;
class AdvObjectBase : public PooledAdvInfo /* represents an interactive object on the adventure map */
{
public:
/*============== static const & variables ==============*/
static const unsigned long isPreBattleBoost = 0x000001ff ;
static const unsigned long builtZoneFlags = 0x00000600 ;
static const unsigned long mobileZoneFlags = 0x00670000 ;
static const unsigned long worldChanged = 0x0000ffff ;
/*============== member variables ==============*/
public:
union
{
unsigned long flags ;
struct {
/* objects with their own one tile area state */
unsigned bIsTown : 1 ;
unsigned bIsGarrison : 1 ;
unsigned bIsSanctuary : 1 ;
unsigned bIsTeleporter : 1 ; // teleporter/monolith/subterranean gate
unsigned bIsExit : 1 ;
/* buildings */
unsigned stables : 1 ;
unsigned rallyFlag : 1 ;
unsigned fountainOfYouth : 1 ;
unsigned oasis : 1 ;
unsigned shipyard : 1 ;
unsigned lighthouse : 1 ;
unsigned magicWell : 1 ;
unsigned magicSpring : 1 ;
unsigned hillFort : 1 ;
unsigned warMachineFactory : 1 ;
unsigned tradingPost : 1 ;
unsigned dock : 1 ;
unsigned tavern : 1 ;
unsigned denOfThieves : 1 ;
unsigned redwoodObservatory : 1 ;
unsigned hutOfTheMagi : 1 ;
unsigned seerHut : 1 ;
unsigned cartographer : 1 ;
unsigned keymaster : 1 ;
unsigned borderGuard : 1 ;
unsigned dwelling : 1 ; // creature generator
unsigned mine : 1 ;
unsigned treasureVault : 1 ; // guarded building with treasure stash
unsigned otherInteractive : 1 ; // other interactive map object
/* mobile objects */
unsigned monster : 1 ;
unsigned artifact : 1 ;
unsigned treasure : 1 ;
};
};
/*-------------- extended flags --------------*/
union
{
unsigned long zoneFlags ;
struct {
/* prebattle boosts */
unsigned fountainOfFortune : 1 ;
unsigned mermaids : 1 ;
unsigned faerieRings : 1 ;
unsigned temple : 1 ;
unsigned lakeOfScarletSwan : 1 ;
unsigned idolOfFortune : 1 ;
unsigned buoy : 1 ;
unsigned nomadsShaman : 1 ;
unsigned fortuitousSanctuary : 1 ;
unsigned bMultiTileArea : 1 ;
unsigned bIsAreaState : 1 ;
unsigned library : 1 ;
unsigned bHeroVisitsOnce : 1 ;
unsigned bWeeklySupplies : 1 ;
unsigned bMerchant : 1 ;
unsigned bGuarded : 1 ;
unsigned bFriendlyHero : 1 ;
unsigned bAlliedHero : 1 ;
unsigned bHostileHero : 1 ;
unsigned bHeroToSupply : 1 ;
unsigned bDockBlocked : 1 ;
unsigned bShip : 1 ;
unsigned bCaravan : 1 ;
unsigned bEvaluated : 1 ;
unsigned bHeroSensitive : 1 ; // change of hero
unsigned bArmySensitive : 1 ; // change of army
unsigned bResourceSensitive : 1 ; // change of available resources
unsigned bValidate : 1 ;
unsigned bRemoved : 1 ; // takes precedence over bValidate
unsigned relay : 1 ;
unsigned queued : 1 ;
unsigned visited : 1 ;
};
};
union
{
unsigned long worldFlags ;
struct {
/* world state change (modifications need to be reflected in worldChanged) */
unsigned affectedNeighbors : 8 ;
unsigned bModified : 1 ;
unsigned bChangeMinor : 1 ;
unsigned bChangeMajor : 1 ;
unsigned bChangeMajorBorder : 1 ;
unsigned reservedModified : 4 ;
/* world state */
unsigned bValidAdvMapEvent : 1 ;
unsigned bShrine : 1 ;
unsigned bPrison : 1 ;
unsigned bFlagged : 1 ;
unsigned bSpecialDwelling : 1 ;
unsigned bCampFire : 1 ;
unsigned bPlayerVisitsOnce : 1 ;
unsigned bResetAndModify : 1 ;
unsigned bTouched : 1 ;
unsigned bMainRoute : 1 ;
unsigned bStrategicGoal : 1 ;
unsigned reservedWorldState : 5 ;
};
};
unsigned short advEventID ;
SAdventureCell position ;
/*-------------- object IDs --------------*/
cacheID mID ; // mobile or object ID
NDb::EBuildingType buildingType ;
unsigned short visitedOnceID ; // index into advVisitedOnce
/*-------------- paired events --------------*/
SAdventureCell shipyardPosition ;
unsigned short shipyardEvent ;
unsigned short shipyardDockEvent ;
/*-------------- world properties for AI processing --------------*/
long value ;
long baseValue ;
long passValue ;
SMoney income ;
FastMoney resourceType ;
BIT__PLAYER owner ;
BIT__PLAYER visitedBy ;
/*-------------- guards & creature dwellings --------------*/
long guardPower ;
long guardExpValue ;
long dwellingRecruits ;
HeroArmyStack dwellingCreatures ;
HeroArmyStack dwellingWeeklyCreatures ;
NDb::ETownType dwellingNativeTown ;
/* ... */
/*============== construction ==============*/
public:
AdvObjectBase( AdvObjectBase* copy = 0 )
: advEventID(0), flags(0), zoneFlags(0), worldFlags(0), position(INVALID_ADVENTURE_CELL), __tile(NULL),
buildingType((NDb::EBuildingType)0), visitedOnceID(0), value(0), baseValue(0),
owner(0), visitedBy(0), guardPower(0), guardExpValue(0) // nilAdvMapEvent
{
if( copy )
*this = *copy ;
}
~AdvObjectBase()
{
}
/*============== public methods ==============*/
public:
bool IsAdvObjectMajor() const { return flags & isAdvObjectMajor ; }
bool IsPreBattleBoost() const { return flags & AdvMapEvent_PreBattle || zoneFlags & isPreBattleBoost ; }
bool IsBorderGuardKeyMaster( FastMoveTile* tiBorderGuard );
bool IsOpenBorderGuard( BIT__KEY keys )
{
return borderGuard && mID.object < advMapGuards.cnt && advMapGuards[ mID.object ].keyColor & keys ;
}
void setGuards( long _guardPower, long _guardExpValue )
{
if( guardPower != _guardPower ) bModified = true ;
guardPower = _guardPower ;
guardExpValue = _guardExpValue ;
}
wchar_t* GetName() const ;
wchar_t* GetInternalName() const ;
void dump( unsigned short idAreaState = 0 ) const ;
}; // class AdvObjectBase
/*----------------------------------------------------------------
class AdvMapEvent
------------------------------------------------------------------*/
class AdvMapEvent : public AdvObjectBase /* represents an interactive object on the adventure map */
{
/* ... */
/*============== construction ==============*/
public:
AdvMapEvent( AdvObjectBase* copy = 0 ); /* usually initialized from cached AdvObjectBase object */
AdvMapEvent( unsigned short id, FastMoveTile* pTile = NULL )
: AdvObjectBase(id), tile(pTile),
idAreaState(0), tileID(0), nLinkedEventCnt(0), shipyardTile(0),
path(), initialEventSequence(), mobileReinforcements(id) {}
~AdvMapEvent()
{
}
/*============== operators ==============*/
AdvMapEvent& operator= ( const AdvObjectCache& obj )
{
AdvObjectBase::operator=( obj );
if( __tile )
tile = GetFastMoveTileSafe( position );
if( shipyard )
shipyardTile = GetFastMoveTileSafe( shipyardPosition );
return *this ;
}
/*============== public methods ==============*/
public:
/* ... */
bool evaluate( AdvMapEvent& from, unsigned short travelCost, unsigned char distance, unsigned short minValuePerTravel,
unsigned char nTurn, unsigned char nPlayer )
{
if( &from == this ) return false ;
bTouched = true ;
bool bWillEndTurn =
bMultiTileArea || bIsSanctuary || ( bShip && ! owner || dock && ! IsDockBlocked( from.path.visited, nTurn ) )
&& ! from.path.heroSkills.bHasSnatchSkill ;
if( dock || bShip )
AdvMapEvent::bEvaluated = false ; // TO DO: optimize, reprocess only some cases
bool bImprove = false ;
bool bEvaluated = AdvMapEvent::bEvaluated ;
if( debug.eventQueue )
{
aiLogger() << " to : " ; dump() ;
aiLogger() << " from: " ; from.dump() ;
aiLogger() << " hero: " << from.path.hero->GetName() << endl ;
#ifdef STRATEGIC_AI_DBG_WORLDSTATE
aiLogger() << " keys: " << print8Bit( from.path.keys>>1 ) << endl ;
#endif
}
passValue = 0 ;
kamikazee = 0 ;
if( travelCost <= from.path.movePoints )
{
if( bWillEndTurn )
{
if( bShip || dock || bIsSanctuary ) travelCost = from.path.movePoints, bEvaluated = true ;
bImprove = path.hasHigherTravelValue( from.path, 0, travelCost );
}
else if( bEvaluated )
bImprove = value >= minValuePerTravel * distance
&& path.hasBetterTravelValue( from.path, value, travelCost, minValuePerTravel, kamikazee );
if( bImprove || ! bEvaluated )
{
long eventValue = getEventValue( &from.path, travelCost, nTurn, nPlayer );
#ifdef STRATEGIC_AI_DETAILEDDBGEVENTTRACE
aiLogger() << "eventValue = " << (int)eventValue << ", minValuePerTravel = " << (int)minValuePerTravel
<< ", distance = " << (int)distance << ", kamikazee = " << (int)kamikazee << endl ;
#endif
if( ! bEvaluated )
bImprove = (passValue && eventValue > 0 || eventValue >= minValuePerTravel * distance)
&& path.hasBetterTravelValue( from.path, eventValue, travelCost, minValuePerTravel, kamikazee );
if( dock && ! eventValue ) bImprove = false ;
if( bImprove )
{
value = eventValue -= passValue ;
path = from.path ;
path.value += eventValue ;
path.movePoints -= travelCost ;
path.previousEvent = from.advEventID ;
path.bBattleSite = bGuarded || monster || bHostileHero ;
path.bAcquisition = mine || treasure || treasureVault ;
path.bDwellingRecruits = dwelling ;
path.kamikazee = kamikazee ;
path.lastNonHeroEvent = bFriendlyHero ? from.path.lastNonHeroEvent : advEventID ;
if( bIsTown )
{
if( kamikazee );
else if( path.strategicAssets.get( mID.strategicAsset ) )
{
approveEstimatedRecruits() ;
}
else
{
SGameTime gameTime( worldParameters.worldTime );
getAdjustedGameTime( gameTime, nTurn, nPlayer );
unsigned char adjustedTurn = gameTime.nDay - worldParameters.worldTime.nDay ;
if( 1 == gameTime.GetDayOfWeek() && (1 << nPlayer) < owner )
path.nTownAcquisition = adjustedTurn ;
if( guardPower ) path.bBattleSite = true ;
}
}
else if( hillFort )
{
value = path.army.UpgradeForces( &path.available );
}
else if( keymaster )
{
path.keys |= advMapKeys[ mID.object ].keyColor ;
}
if( bIsExit && guardPower )
{
FastMoveTile* monster = tile ;
if( monster && ! monster->bIsMonster ) monster = monster->GetNeighboringMonster() ;
bool bNeighboringMonster = monster && monster != tile ;
if( ! path.visited.get( advEventID )
|| bNeighboringMonster && ! path.visited.get( monster->advEventID ) )
{
path.bBattleSite = true ;
if( bNeighboringMonster )
path.visited.set( monster->advEventID );
}
}
if( shipyard )
{
SMoney cost( 10, 0, 0, 0, 0, 0, 1000 );
path.available -= cost ;
path.value -= 2000 ;
path.visited.clear( shipyardDockEvent );
if( ! path.bIsCommander && path.available.nWood < 10 ) path.value -= 5000 ;
}
bool bTownShipyardDock = false ;
if( dock && ! IsDockBlocked( from.path.visited, nTurn ) || bShip && ! owner )
{
if( dock && getAdvMapEvent( shipyardEvent ).bIsTown )
{
SMoney cost( 10, 0, 0, 0, 0, 0, 1000 ); // reserve some wood
path.available -= cost ;
path.bBuildShip = true ;
bTownShipyardDock = true ;
}
if( ! path.heroSkills.bHasSnatchSkill )
path.movePoints = 0 ;
}
if( fountainOfYouth ) path.movePoints += 400 ;
if( oasis ) path.movePoints += 800 ;
if( rallyFlag ) path.movePoints += 400 ;
if( stables && ! path.bVisitedStables ) path.movePoints += 600 ;
if( path.bBattleSite && path.heroSkills.bBattleBonusMove ) path.movePoints += 350 ;
if( magicWell && path.mana < path.manaMax )
path.mana = path.manaMax ;
if( magicSpring && path.mana < path.manaMax * 2 )
path.mana = path.manaMax * 2 ;
if( ! bMultiTileArea && ! IsAdvObjectMajor() || dock && ! bTownShipyardDock || bIsExit )
path.visited.set( advEventID );
}
}
if( debug.eventQueue )
{
aiLogger() << distance << (bImprove ? ": (+" : ": (") << (int)value << ") " ; dump() ; aiLogger() << endl ;
}
}
else
{
if( debug.eventQueue )
{
aiLogger() << "Travel cost exceeds remaining movement points by " << travelCost – from.path.movePoints
<< "! " ; dump() ; aiLogger() << endl ;
}
}
currentTravelCost = travelCost ;
return bImprove ;
}
}; // class AdvMapEvent
It is a more complex example how a logical partition into separate C++ classes yields well developed evaluation services on a higher logical level. ShortPath is used for adventure map path probing, AdvMapEvent encapsulates adventure map object properties. Only shortened samples are provided. The debug code is left in to demonstrate a typical debugging strategy, due to the complexity of the AI variable debug dumping has proved invaluable. It allows also for the incremental validation of functionality and detailed bug tracking during betas. Together the various classes allow for code that appears nearly organic in nature to express high level functionality.
Putting all together
With this short practical guide you have an overview what type of data is typically needed for pathfinding and AI. Please note that the data structures for the game itself are usually much more complex, the data structures presented here are highly optimized for an AI that needs to process millions of variants in a short period of time.
You may also ask why there are data structures for the adventure map events if the aim is to develop a pathfinder. Pathfinder and AI logic is often intertwined, which is highly evident in the design of Heroes III, essentially adventure map objects affect movement. There is a more clear distinction in the advanced AI I developed, but even here time constraints and requirements for optimization make both interdependent.
This concludes today's coding practice. If there is enough interest, the next topic will be how to build a working pathfinder and AI similar to the one Heroes III uses. Let me know if you are interested in this.