Artificial intelligence and more

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.

You’ve successfully subscribed to Quantomas AI
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.