Artificial intelligence and more

Developing AI for a PC game, and in general, requires more skills than to excel in the programming language of your choice. It's very much a prerequisite that you are capable of writing code that is well-structured and geared towards getting the best performance out of the machine you are developing for. But to be good at designing and implementing AI, you also need vision to design complex systems that perform like an organic entity that is governed by a grand overarching architecture.

Last year we started out with building the fundament of such an architecture by looking at sound methods to model the data structures and partition code smartly.

Today we are looking at the skills required to master the complexity that is typical of powerful AI. The functionality of an application and the means to control its functions smartly with AI are typically interwoven.

For many AI applications, especially grand strategy games, a lot of functionality deals with time and space, distances and the time needed to traverse these and perform actions. Technically this is addressed by the term topology and usually dealt with by a pathfinder. Its task is the highly performant computation of distances and paths, often to provide the AI with insight of what can happen on a map.

Before we move to practical examples let's get a better grasp of what matters.

Order

Possibly the most important concept for AI is order, because order permeates everything.

AI frequently needs to make comparisons and rank potential outcomes. For this data needs to be collected and processed. For example a high-performance pathfinder can process a hundred million distances per second and requests a huge volume of data. In practice there are a myriad of ways to go about this. But one thing never changes, the order in which you process, acquire and supply data has a huge impact on how your application performs.

AI typically makes choices what paths and variants to process next, and as a consequence effectively determines in which order processes in your application are run, what data has to be acquired next and so on. A fully fledged AI is the backbone of your application, because prioritizing all the data streams in your application correctly and processing what matters most can easily make a difference of a factor 1000 in performance.

Order has a dual sense here. Firstly in which order data is processed, or functionality invoked, by an application. This is a question of how your application is logically, internally structured. Secondly order matters in how the machine your application is running on supplies the bandwith and computing resources. You want to avoid bottlenecks, wait states and race conditions while making the most of your processor cache. As an AI programmer you need a firm grasp to understand both sides in order to implement an application that runs like a well oiled engine. AI requires you to see the big picture, how hundreds of millions of computations and comparisons in a second can be performed efficiently. If you can see how rearranging the different parts of an overarching architecture leads to different ways to process all the data, you have a very powerful tool. The order in which you process data is just as important as to decide what to process.

Let's have a look at some practical examples. The samples are meant for experienced C++ programmers who have an eye for efficiency and elegance in solving a challenge. In the light of the introduction above, these examples should bolster your tool chest and give you an idea how to go about finding a solid architecture for your application, both in terms of functionality and performance.

Contracts and negotiation

C++ offers you many options to partition your application, classes, interfaces, function definitions and all the bells and whistles that come with inheritance. For an AI programmer it is invaluable to choose such means that make most sense for implementing the architecture of your application.

Templates allow for the negotiation of contracts between different entities in a way that is more flexible than function prototypes and interfaces. If you know what you do, you can achieve significant performance gains.

Below you find an example that is part of a floor pathfinder that computes the distance from an origin to all tiles in range. If you make sure that the entire tile map is in the processor cache, performance is unmatched.

This type of distance computation is a versatile technique that is useful in many different circumstances.

/*----------------------------------------------------------------
    5 - Template based tile iteration
------------------------------------------------------------------*/

template<class _T_FastMoveTileInfo> class tileIterator {

    struct FastMoveTileCache
        {
        FastMoveTile*           _ptr ;
        unsigned short          xOrigin ;
        unsigned short          yOrigin ;
        unsigned short          lineWidth ;
        unsigned short          lineCnt ;
        unsigned short          nFloorCnt ;
        bool                    bCopied ;
        };

    /*============== static const & variables ==============*/
private:
    static FastMoveTileCache*   cachePool ;

    /*============== member variables ==============*/

    _T_FastMoveTileInfo*        tileInfo ;
    long                        sizeOfTileInfo ;
    long                        mapTileCnt ;

    FastMoveTileCache           cache ;

    /*============== construction ==============*/
public:
    #define TILEITERATOR_NOCACHE    true

    tileIterator(
        unsigned short  x,
        unsigned short  y,
        unsigned short  xmax,
        unsigned short  ymax,
        bool            bIsUnderground,
        bool            bNoCache = false
        );

    ~tileIterator() ;

    /*============== tile formatting ==============*/
private:
        /* fetch tileInfo for border tiles and mark access limit */
    void markAccessLimit( _T_FastMoveTileInfo* _tileInfo )
        {
        _T_FastMoveTileInfo*    ti ;
         unsigned short         i ;

        for( i = 0, ti = _tileInfo ;
             i < cache.lineWidth ; i++, ti++ )
            ti->mapBorder |= north, ti->neighbors |= north ;

        for( i = 0, ti = _tileInfo + cache.lineWidth * (cache.lineCnt-1) ;
             i < cache.lineWidth ; i++, ti++ )
            ti->mapBorder |= south, ti->neighbors |= south ;

        for( i = 0, ti = _tileInfo ;
             i < cache.lineCnt ; i++, ti += cache.lineWidth )
            ti->mapBorder |= west, ti->neighbors |= west ;

        for( i = 0, ti = _tileInfo + cache.lineWidth - 1 ;
             i < cache.lineCnt ; i++, ti += cache.lineWidth )
            ti->mapBorder |= east, ti->neighbors |= east ;
        }

    /*============== public methods ==============*/
public:
        /* fetch tileInfo for border tiles and mark area limit */
    void markAreaLimit( _T_FastMoveTileInfo** mTiles, FastMoveTile** tiles, unsigned short nTileCnt )
        {
        unsigned short i ;

        for( i = 0 ; i < nTileCnt ; i++ )
            mTiles[i] = getTileInfoInitialized( tiles[i] );

        for( i = 0 ; i < nTileCnt ; i++ )
            {
            _T_FastMoveTileInfo* ti = mTiles[i] ;

            unsigned char neighbors = ti->neighbors ;

            for( unsigned char iNeighbor = N ; iNeighbor ; iNeighbor <<= 1 )
                if( neighbors & iNeighbor && ! getTileInfo( ti, iNeighbor )->bInitialized )
                    neighbors &= ~iNeighbor ;                   

            ti->neighbors = neighbors ;
            } // for( i = 0 ; i < nTileCnt ; i++ )
        }


    void reset() ;
    void reset( bool bIsUnderground );

    _T_FastMoveTileInfo* getTileInfoMap()       { return tileInfo ; }
    long                 getTileInfoMapLength() { return cache.lineWidth * cache.lineCnt ; }

    FastMoveTile* getTile( _T_FastMoveTileInfo* ti )
        {
        if( ti->bInitialized ) return ti->_ptr ;
        return ti->fetchTileInfo( cache._ptr + (ti - tileInfo) );
            // Note: ideal performance for sizeof(_T_FastMoveTileInfo) == sizeof(FastMoveTile) == 4, 8 or 16  
        }

    _T_FastMoveTileInfo* getTileInfo( FastMoveTile* tile ) const
        {
        return tileInfo + (tile - cache._ptr) ;
            // Note: ideal performance for sizeof(_T_FastMoveTileInfo) == sizeof(FastMoveTile) == 4, 8 or 16  
        }

    _T_FastMoveTileInfo* getTileInfoInitialized( FastMoveTile* tile ) const
        {
        _T_FastMoveTileInfo* ti = tileInfo + (tile - cache._ptr) ;
        if( ! ti->bInitialized ) ti->fetchTileInfo( tile );
        return ti ;
        }

    _T_FastMoveTileInfo* getTileInfoInitialized( long nTile ) const
        {
        _T_FastMoveTileInfo* ti = tileInfo + nTile ;
        if( ! ti->bInitialized ) ti->fetchTileInfo( cache._ptr + nTile );
        return ti ;
        }


    _T_FastMoveTileInfo* getN ( _T_FastMoveTileInfo* ti ) const { return ti - cache.lineWidth     ; }
    _T_FastMoveTileInfo* getNE( _T_FastMoveTileInfo* ti ) const { return ti - cache.lineWidth + 1 ; }
    _T_FastMoveTileInfo* getE ( _T_FastMoveTileInfo* ti ) const { return ti                   + 1 ; }
    _T_FastMoveTileInfo* getSE( _T_FastMoveTileInfo* ti ) const { return ti + cache.lineWidth + 1 ; }
    _T_FastMoveTileInfo* getS ( _T_FastMoveTileInfo* ti ) const { return ti + cache.lineWidth     ; }
    _T_FastMoveTileInfo* getSW( _T_FastMoveTileInfo* ti ) const { return ti + cache.lineWidth - 1 ; }
    _T_FastMoveTileInfo* getW ( _T_FastMoveTileInfo* ti ) const { return ti                   - 1 ; }
    _T_FastMoveTileInfo* getNW( _T_FastMoveTileInfo* ti ) const { return ti - cache.lineWidth - 1 ; }


    _T_FastMoveTileInfo* getTileInfo( _T_FastMoveTileInfo* ti, unsigned char neighbor ) const
        {
        _T_FastMoveTileInfo* tn = ti ;

        if( neighbor & north )
            tn -= cache.lineWidth ;
        else if( neighbor & south )
            tn += cache.lineWidth ;

        if( neighbor & east )
            tn += 1 ;
        else if( neighbor & west )
            tn -= 1 ;

        return tn ;
        }


    _T_FastMoveTileInfo* getTileInfoInitialized( _T_FastMoveTileInfo* ti, unsigned char neighbor ) const
        {
        _T_FastMoveTileInfo* tn = getTileInfo( ti, neighbor );

        if( ! tn->bInitialized ) tn->fetchTileInfo( cache._ptr + (tn - tileInfo) );

        return tn ;
        }


    bool ExistsInTileList( list<_T_FastMoveTileInfo*>& tileList, _T_FastMoveTileInfo* ti )
        {
        for( list<_T_FastMoveTileInfo*>::iterator jt = tileList->begin() ; jt != tileList->end() ; jt++ )
            if( ti == *jt ) return true ;

        return false ;
        }



/*________________________ iterators __________________________*/

    public:

        /*
            moveCostCalculator computes the move cost from a given seed
            to any accessible tile in a limited tile map area. Ordering
            of the spread is controlled by queueing newly added tiles.
        */
        class moveCostCalculator {

            const tileIterator&         TI ;

            list<_T_FastMoveTileInfo*> _q ;
            list<_T_FastMoveTileInfo*> _qr ;

            _T_FastMoveTileInfo*        origin ;

            /*============== construction ==============*/
        public:
            moveCostCalculator(
                const tileIterator&     _TI,
                _T_FastMoveTileInfo*    _origin
                )  
                : TI( _TI ), _q(), _qr(), origin( _origin )
                {
                if( debug.areaStateConstruction )
                        aiLogger() << "--- (moveCostCalculator) --- (" << origin->_ptr->x << ", " << origin->_ptr->y << ")" << endl ;
                }

            ~moveCostCalculator()
                {
                }

            /*============== public methods ==============*/

            _T_FastMoveTileInfo* first( _T_FastMoveTileInfo** mTiles, unsigned char* tileID_, unsigned short size )
                {
                _q.clear() ;
                _qr.clear() ;

                for( unsigned short i = 0 ; i < size ; i++ )
                    {
                    _T_FastMoveTileInfo* src = mTiles[ tileID_[i] ];
                    src->touched = true ;
                    src->accumulatedCost.clear() ;
                    _q.push_back( src );
                    }

                return next() ;
                }

            _T_FastMoveTileInfo* first()
                {
#ifdef STRATEGIC_AI_TRACK_MOVECOST_COMPUTATION
                if( debug.trackMoveCostComputation ) { aiLogger() << "first(), origin = " ; origin->_ptr->dumpTileInfo() ; }
#endif
                _q.clear() ;
                _qr.clear() ;
                origin->touched = true ;
                origin->origin  = 0 ;
                origin->active  = 0xff ;
                origin->accumulatedCost.clear() ;
                _q.push_back( origin );
                return next() ;
                }

            _T_FastMoveTileInfo* last()
                {
                _T_FastMoveTileInfo* ti ;
                _T_FastMoveTileInfo* tnext ;

                if( empty() || ! (ti = next()) )
                    ti = first() ;

                while( tnext = next() ) ti = tnext ;

                return ti ;
                }

            _T_FastMoveTileInfo* next()
                {
                _T_FastMoveTileInfo* ti ;

                if( ! _qr.empty() )
                    {
                    ti = _qr.front() ;
                    _qr.pop_front() ;
                    }
                else if( ! _q.empty() )
                    {
                    ti = _q.front() ;
                    _q.pop_front() ;
                    }
                else
                    return NULL ;

                pushNeighbors( ti );
                return ti ;
                }

            bool empty()
                {
                return _q.empty() && _qr.empty() ;
                }

            unsigned int queued()
                {
                return _qr.size() + _q.size() ;
                }

            void reset( _T_FastMoveTileInfo* _origin, _T_FastMoveTileInfo** pMoveCostInfo, unsigned short costInfoCnt )
                {
                if( pMoveCostInfo )
                    for( ; costInfoCnt > 0 ; costInfoCnt--, pMoveCostInfo++ ) (*pMoveCostInfo)->clear() ;

                origin = _origin ;
                _qr.clear() ;
                _q.clear() ;
                }

            /*============== tile queueing ==============*/
        private:
            void push( _T_FastMoveTileInfo* ti, _T_FastMoveTileInfo& accumulated, unsigned char iNeighbor )
                {
#ifdef STRATEGIC_AI_TRACK_MOVECOST_COMPUTATION
                if( debug.trackMoveCostComputation ) { aiLogger() << "To  : " ; ti->_ptr->dumpTileInfo() ; }
#endif
                bool bNewTouch = ! ti->touched ;

                if( ti->addMoveCost( accumulated, iNeighbor ) ) _qr.push_back( ti );

                if( bNewTouch && ti->accumulatedCost.noTriggersInPath ) _q.push_back( ti );
                }

            void pushNeighbors( _T_FastMoveTileInfo* ti )
                {
#ifdef STRATEGIC_AI_TRACK_MOVECOST_COMPUTATION
                if( debug.trackMoveCostComputation ) { aiLogger() << "From: " ; ti->_ptr->dumpTileInfo() ; }
#endif
                unsigned char           neighbors = ti->neighbors & ~ti->origin ;
                _T_FastMoveTileInfo*    tNeighbor ;

                if( neighbors & N )
                    {
                    tNeighbor = ti - TI.cache.lineWidth ;
                    push( tNeighbor, *ti, S );
                    }
                if( neighbors & NE )
                    {
                    tNeighbor = ti - TI.cache.lineWidth + 1 ;
                    push( tNeighbor, *ti, SW );
                    }
                if( neighbors & E )
                    {
                    tNeighbor = ti + 1 ;
                    push( tNeighbor, *ti, W );
                    }
                if( neighbors & SE )
                    {
                    tNeighbor = ti + TI.cache.lineWidth + 1 ;
                    push( tNeighbor, *ti, NW );
                    }
                if( neighbors & S )
                    {
                    tNeighbor = ti + TI.cache.lineWidth ;
                    push( tNeighbor, *ti, N );
                    }
                if( neighbors & SW )
                    {
                    tNeighbor = ti + TI.cache.lineWidth - 1 ;
                    push( tNeighbor, *ti, NE );
                    }
                if( neighbors & W )
                    {
                    tNeighbor = ti - 1 ;
                    push( tNeighbor, *ti, E );
                    }
                if( neighbors & NW )
                    {
                    tNeighbor = ti - TI.cache.lineWidth - 1 ;
                    push( tNeighbor, *ti, SE );
                    }

                ti->active = 0 ;
                }

            }; // class moveCostCalculator

/*________________________ end of iterators __________________________*/

        }; // class tileIterator

In principle similar results can be achieved with different techniques, for example class and interface definitions. But templates allow for more specific contracts and the efficient separation of functionality.

Order and sorting

While implementing AI the ordering and sorting of data is often critical. Efficient sorting algorithms are invaluable.

Here is an example that uses priority queues to perform partial ordering of input values. In practice it is useful for smart variant selection (similar to MCTS). Priority queues and heapsort (the algorithm used) have many other uses as well, especially if you only need to know what are the top values of an input sample.

The first class optimized_queue gives you an idea how far optimization can go. It is nearly identic to the version in the STL but has a few improvements and much better readability.

The second class heap_queue demonstrates how you can make the interface more adaptable. This algorithm also addresses memory management and references to the source data.

/*----------------------------------------------------------------
    6 - Powerful sorting strategies
------------------------------------------------------------------*/

template <class _Tp, class _Sequence = vector<_Tp>, class _Compare = less() >
class optimized_queue
    {
    /*============== types ==============*/
public:
    typedef          _Tp                        value_type;
    typedef          _Sequence                  container_type;

    typedef typename _Sequence::reference       reference;
    typedef typename _Sequence::const_reference const_reference;

    /*============== member variables ==============*/
protected:
    _Sequence           c ;
    _Compare            comp ;

    /*============== construction ==============*/
public:
    optimized_queue()
        {
        }

    /*============== private methods ==============*/
private:
    inline void heap_assign( int pos, _Tp& assignee )
        {
        c[pos] = assignee ;
        }

    void pullBinarySort( int posHole, _Tp& newValue )
        {
        int cntEntries = c.size() ;
        int iSecond ;

        while( (iSecond = (posHole + 1) * 2) < cntEntries )
            {
            int iSecond2 = iSecond-- ;

            if( comp( c[iSecond], c[iSecond2] ) )
                iSecond = iSecond2 ;

            if( ! comp( newValue, c[iSecond] ) ) break ;

            heap_assign( posHole, c[iSecond] );
            posHole = iSecond ;
            }

        if( iSecond == cntEntries )
            {
            iSecond-- ;

            if( comp( newValue, c[iSecond] ) )
                {
                heap_assign( posHole, c[iSecond] );
                posHole = iSecond ;
                }
            }

        heap_assign( posHole, newValue );
        }

    void pushBinarySort( int posHole, _Tp& newValue )
        {
        while( posHole )
            {
            int posParent = (posHole - 1) / 2 ;

            if( comp( c[posParent], newValue ) )
                {
                heap_assign( posHole, c[posParent] );
                posHole = posParent ;
                }
            else
                break ;
            }

        heap_assign( posHole, newValue );
        }

    /*============== public methods ==============*/
public:
    void push( value_type& __x ) 
        {
        int posHole = c.size() ;

        c.push_back( __x ); 

        pushBinarySort( posHole, __x );
        }

    void pop() 
        {
        int size = c.size() ;

        if( ! size ) return ;

        value_type val = c[--size] ;

        c.pop_back() ;

        if( size )
            pullBinarySort( 0, val );
        }

    const_reference top() const { return c.front() ; }

    void clear()
        {
        c.resize( 0 );
        }

    bool empty() const { return c.empty() ; }
    int  size()  const { return c.size() ; }

    vector<_Tp>& getElements()  { return c ; }

    _Tp* nextQueued( _Tp& queued )
        {
        if( empty() ) return 0 ;

        queued = top() ;

        pop() ;

        return &queued ;
        }

    }; // class optimized_queue


template <class _Tp, class _Sequence = vector<_Tp>, class _Compare = less() >
class heap_queue
    {
    /*============== types ==============*/
public:
    typedef          _Tp                        value_type;
    typedef          _Sequence                  container_type;

    typedef typename _Sequence::reference       reference;
    typedef typename _Sequence::const_reference const_reference;

    /*============== member variables ==============*/
protected:
    _Sequence           c ;
    _Compare            comp ;

    vector<int>         vPosition ;
    int                 szPosition ;
    int                 szGarbage ;

    /*============== construction ==============*/
public:
    heap_queue( )
        : vPosition(1020)
        , szPosition(0)
        , szGarbage(0)
        {
        }

    /*============== private methods ==============*/
private:
    void expand_positions()
        {
        int size = vPosition.size() ;

        vPosition.resize( size * 2 );

        CopyMemory( vPosition.end() - szGarbage, vPosition.begin() + size - szGarbage, sizeof(int) * szGarbage );
        }

    void add_garbage( const value_type& assignee )
        {
        if( szPosition + szGarbage >= vPosition.size() )
            expand_positions() ;

        *(vPosition.end() - ++szGarbage) = assignee.uid ;
        }

    HUID add_position( value_type& assignee )
        {
        if( szGarbage )
            {
            assignee.uid = *(vPosition.end() - szGarbage--) ;
            }
        else
            {
            assignee.uid = szPosition++ ;

            if( assignee.uid >= vPosition.size() - szGarbage )
                expand_positions() ;
            }

        return assignee.uid ;
        }

    inline void heap_assign( int pos, _Tp& assignee )
        {
        c[pos] = assignee ;

        vPosition[assignee.uid] = pos ;
        }

    void pullBinarySort( int posHole, _Tp& newValue, int posValue )
        {
        int cntEntries = c.size() ;
        int iSecond ;

        while( (iSecond = (posHole + 1) * 2) < cntEntries )
            {
            int iSecond2 = iSecond-- ;

            if( comp( c[iSecond], c[iSecond2] ) )
                iSecond = iSecond2 ;

            if( ! comp( newValue, c[iSecond] ) ) break ;

            heap_assign( posHole, c[iSecond] );
            posHole = iSecond ;
            }

        if( iSecond == cntEntries )
            {
            iSecond-- ;

            if( comp( newValue, c[iSecond] ) )
                {
                heap_assign( posHole, c[iSecond] );
                posHole = iSecond ;
                }
            }

        if( posHole != posValue )
            heap_assign( posHole, newValue );
        }

    void pushBinarySort( int posHole, _Tp newValue )
        {
        while( posHole )
            {
            int posParent = (posHole - 1) / 2 ;

            if( comp( c[posParent], newValue ) )
                {
                heap_assign( posHole, c[posParent] );
                posHole = posParent ;
                }
            else
                break ;
            }

        heap_assign( posHole, newValue );
        }

    /*============== public methods ==============*/
public:
    HUID push( value_type& __x ) 
        {
        int posHole = c.size() ;

        add_position( __x );
        c.push_back( __x ); 

        pushBinarySort( posHole, __x );
        return __x.uid ;
        }

    void pop() 
        {
        int size = c.size() ;

        if( ! size ) return ;

        add_garbage( *c.begin() );

        value_type val = c[--size] ;

        c.pop_back() ;

        if( size )
            pullBinarySort( 0, val, size );
        }

    const_reference top() const { return c.front() ; }
    reference       top()       { return c.front() ; }

    void clear()
        {
        c.resize( 0 );
        szPosition = 0 ;
        szGarbage  = 0 ;
        }

    bool empty() const { return c.empty() ; }
    int  size()  const { return c.size() ; }

    void update( value_type& newValue )
        {
        int posHole = vPosition[ newValue.uid ];

        value_type& oldValue = c[posHole] ;

        if( comp( oldValue, newValue ) )
            {
            pushBinarySort( posHole, newValue );
            }
        else
            {
            pullBinarySort( posHole, newValue, c.size() );
            }
        }

    void remove( HUID uid )
        {
        int size = c.size() ;

        if( ! size || uid >= szPosition ) return ;

        int posHole = vPosition[ uid ];

        if( posHole >= size ) return ;

        add_garbage( c[posHole] );

        value_type newValue = c[--size] ;
        value_type oldValue = c[posHole] ;

        c.pop_back() ;

        if( size == posHole ) return ;

        if( comp( oldValue, newValue ) )
            {
            pushBinarySort( posHole, newValue );
            }
        else
            {
            pullBinarySort( posHole, newValue, size );
            }
        }

    vector<int>& getPositions() { return vPosition ; }
    vector<_Tp>& getElements()  { return c ; }

    _Tp* nextQueued( _Tp& queued )
        {
        if( empty() ) return 0 ;

        queued = top() ;
        queued.uid = huidVoid ;

        pop() ;

        return &queued ;
        }

    }; // class heap_queue

There are of course many more sorting algorithms and strategies. Though heapsort, as featured above, is a very efficient and powerful tool to do partial sorting only in order to find the most critical variants.

Ultrafast distance computation

A pathfinder is typically a tool to examine possible paths, from tile to tile or node to node, depending on the topology, and then select those that offer the best value, depending on the criteria.

In the context of AI design a pathfinder usually does more and associates values with the events an actor would perform/encounter while traversing a path. Thus a pathfinder performs two functions. Firstly it strings path segments together which connect one event with another, i.e. the actor travels from one event to the next. Which tiles the actor travels along doesn't matter, it is the job of the pathfinder to figure out which route can be travelled most efficiently.

The second task of the pathfinder is more complex. It associates a value with each event and tracks the total value accumulated along a path. What makes this more complex is that the events typically are context-sensitive, that is their outcome and value depends on the state of the actor and what events the actor visited beforehand.

In order to maximize the value of the movepoints (or other equivalent) that an actor spends, the pathfinder has to examine all kinds of possible paths, even paths that zigzag from event to event or loop back. Or it could even mean visit event A, then event B, then A again. Plus individual events could have multiple different outcomes.

In order to accomplish this the pathfinder has to track what events have already been visited for each path that is under consideration, and how this changes the events that can happen afterwards.

A natural and efficient solution for this is to precompute the distances, i.e. the movepoints required, and to store these in a table that lists the distances between events. However, this isn't feasible on large maps with a high density of events.

What is possible instead is to create tables that list the distances from each event to all events within a limited range. The distance to events beyond the limited range can then be approximated by using the events within range as relays. This is a proven method that is – with a few tweaks – astonishingly efficient.

Technically, it requires some compact and well designed data structures plus a mechanism that is called a relay queue that is optimized to an extent to support millions of distance computations in a second.

Below you find an implementation that demonstrates this technique. Note the special requirements for events that have already been visited and checked during the present computation. The caller calls init() and next() to iterate over the events in order of distance.

This approach is ultrafast if implemented well and an integral part of a high-performance pathfinder.

/*----------------------------------------------------------------
    7 - Ultrafast distance computation
------------------------------------------------------------------*/

struct TileNavigation
    {
    union
        {
        unsigned long       flags ;
        struct {
            unsigned        terrain             : 8 ;
            unsigned        tileID              : 8 ;
            unsigned        bSingleTileState    : 1 ; // set by LinkAreaEvents()
            unsigned        bIsTeleporter       : 1 ;
            unsigned        bInteractiveBlocked : 1 ;
            unsigned        bDeepWater          : 1 ;
            unsigned        bIsLandWaterBorder  : 1 ;
            unsigned        bIsAreaTile         : 1 ;
            unsigned        bHasEventsToLink    : 1 ;
            unsigned        bNoConnectedEvents  : 1 ;
            unsigned        unused              : 8 ;
            };
        };

    TmpEventDistance*       eventsToLink ;
    LinkedEvents            linkedEvents ;
    TileRelays*             relayed ;

    unsigned short          idAreaState ;
    unsigned short          advEventID ;

    /*============== public methods ==============*/

    void clear() { ZeroMemory( this, sizeof(TileNavigation) ); }

    /* ... */

    }; // struct TileNavigation

struct LinkedEvents
    {
    EventDistance*      ptr ;
    unsigned short      cnt ;
    };

struct EventPosition
    {
    TileNavigation*     tile ;
    MPTS                mp ;
    MPTS                mpReimbursed ;
    };

struct EventDistance
    {
    union
        {
        unsigned long       flags ;
        struct {
            unsigned        idEventTarget       : 16 ;
            unsigned        bRelaying           :  1 ;
            unsigned        bIsRelay            :  1 ;
            unsigned        bIsMonster          :  1 ;
            unsigned        bIsAreaState        :  1 ;
            unsigned        bIsTreasure         :  1 ;
            };
        };

    EventPosition           pos[__terrainCnt__] ;

    /*============== public methods ==============*/

    void clear() { ZeroMemory( this, sizeof(EventDistance) ); }

    TileNavigation* getTile( TerrainClassIndex _terrain_ ) { return pos[_terrain_].tile ; }

    }; // struct EventDistance


struct RelayQueue
    {
    static const unsigned short cRelayQueueSize = 510 ;

    struct EventDistanceQueue
        {
        EventDistanceQueue* relayer ;
        EventDistance*      relayingEvent ;
        TileNavigation*	    relayTile ;
        EventDistance*      firstEvent ;
        EventDistance*      currentEvent ;
        EventDistance*      endOfEvents ;
        MPTS                baseDistance ;
        bool                bProcessed ;
        }; // struct EventDistanceQueue


    EventDistanceQueue  relayQueue[ cRelayQueueSize ];
    vector<MPTS>        relayed ;
    BITMAPHANDLE&       relays ;
    BITMAPHANDLE*       blocked ;

    unsigned short      nRelayQueueSize ;

    MPTS                maxDistance ;
    BITMAPHANDLE*       hdlChecked ;
    BITMAPHANDLE*       hdlVisited ;

    TerrainClassIndex  _terrain_ ;
    unsigned char       nPlayer ;
    bool                bInBoat ;

    /*============== construction ==============*/

    RelayQueue( BITMAPHANDLE& relayFilter, BITMAPHANDLE blockedTiles[], unsigned short nEventCnt )
        : relayed(mapTileCnt), relays( relayFilter ), blocked( blockedTiles ), nPlayer( 0 )
        {
        }

    ~RelayQueue()
        {
        }

    /*============== public methods ==============*/

    void clear() { nRelayQueueSize = 0 ; relays.zero() ; }

    void add( MPTS baseDistance, TileNavigation& relayTile, EventDistanceQueue* relayedFrom = 0 )
        {
        relayTile.init() ;

        if( relayTile.bDeepWater != bInBoat && ! relayTile.bIsTeleporter ) return ;

        int nTilePosition = getTilePosition( &relayTile );

        if( relays.get(nTilePosition) && relayed[nTilePosition] <= baseDistance ) return ;

        if( nRelayQueueSize >= cRelayQueueSize )
            {
            if( debug.eventQueue )
                aiLogger() << "WARNING: RelayQueue overflow! Skipping additional events." << endl ;
            return ;
            }

        if( nPlayer < cMaxPlayers && blocked[nPlayer].get( nTilePosition ) ) 
            return ;

        if( ! relayTile.linkedEvents.ptr || ! relayTile.linkedEvents.cnt )
            {
            computeTileDistances( relayTile );

            if( ! relayTile.linkedEvents.ptr || ! relayTile.linkedEvents.cnt )
                {
                if( debug.eventQueue ) { aiLogger() << "WARNING: relayTile without linked events! " ; relayTile.dump() ; }
                return ;
                }
            }

        relayQueue[ nRelayQueueSize ].relayer          = relayedFrom ;
        relayQueue[ nRelayQueueSize ].relayingEvent    = relayedFrom ? relayedFrom->currentEvent : 0 ;
        relayQueue[ nRelayQueueSize ].baseDistance     = baseDistance ;
        relayQueue[ nRelayQueueSize ].relayTile        = &relayTile ;
        relayQueue[ nRelayQueueSize ].firstEvent       = relayTile.linkedEvents.ptr ;
        relayQueue[ nRelayQueueSize ].currentEvent     = relayTile.linkedEvents.ptr ;
        relayQueue[ nRelayQueueSize ].endOfEvents      = relayTile.linkedEvents.ptr + relayTile.linkedEvents.cnt ;
        relayQueue[ nRelayQueueSize ].bProcessed       = false ;
        relayed[nTilePosition] = baseDistance ;
        relays.set( nTilePosition );
        if( debug.eventQueue )
            {
            aiLogger() << "     RelayQueue[" << nRelayQueueSize << "] added, baseDistance = " << (int)baseDistance << "  " ; relayTile.dump() ;
            }
        nRelayQueueSize++ ;
        }

    void init( TileNavigation& navigation, BITMAPHANDLE& checked, BITMAPHANDLE& visited, TerrainClassIndex iTerrain, MPTS mpMaxDistance, unsigned char nPlayerCheckedForRegionsBlocked )
        {
        clear() ;

        hdlChecked  = &checked ;
        hdlVisited  = &visited ;

        _terrain_   = iTerrain ;
        maxDistance = mpMaxDistance ;
        nPlayer     = nPlayerCheckedForRegionsBlocked ;
        bInBoat     = navigation.bDeepWater ;

        add( 0, navigation );

        for( unsigned short i = 0 ; i < nRelayQueueSize ; i++ )
            {
            relayQueue[ i ].currentEvent = relayQueue[ i ].firstEvent ;
            relayQueue[ i ].bProcessed   = false ;
            }
        }

    MPTS next( EventDistance** targetEvent )
        {
        BITMAPHANDLE&   checked       = *hdlChecked ;
        BITMAPHANDLE&   visited       = *hdlVisited ;
        EventDistance*  nearestEvent  = NULL ;
        MPTS            bestDistance  = cStateDistanceVoid ;
        unsigned short  bestQueue     = 0 ;

        for( unsigned short nQueue = 0 ; nQueue < nRelayQueueSize ; nQueue++ )
            {
            EventDistanceQueue& rq = relayQueue[ nQueue ];

            if( rq.bProcessed ) continue ;

            while( true )
                {
                EventPosition* position = rq.currentEvent->pos + _terrain_ ;
                MPTS           distance = rq.baseDistance + position->mp ;

                if( distance > maxDistance )
                    {
                    rq.bProcessed = true ;
                    break ;
                    }

                if( checked.get( rq.currentEvent->idEventTarget ) )
                    {
                    if( rq.currentEvent->bRelaying )
                        {
                        if( visited.get( rq.currentEvent->idEventTarget ) )
                            {
                            if( rq.currentEvent->bIsRelay )
                                {
                                TileNavigation* navigation = position->tile ;

                                add( distance - position->mpReimbursed, *navigation, &rq );
                                }
                            } // if( visited.get( rq.currentEvent->idEventTarget ) )
                        } // if( rq.currentEvent->bRelaying )
                    } // if( checked.get( rq.currentEvent->idEventTarget ) )
                else
                    {
                    if( distance < bestDistance )
                        {
                        bestDistance  = distance ;
                        nearestEvent  = rq.currentEvent ;
                        bestQueue     = nQueue ;
                        }
                    break ;
                    }

                if( ++rq.currentEvent >= rq.endOfEvents )
                       {
                       rq.bProcessed = true ;
                       break ;
                       }
                } // while( rq.currentEvent < rq.endOfEvents )
            } // for( unsigned short nQueue = 0 ; nQueue < nRelayQueueSize ; nQueue++ )

        if( bestDistance < cStateDistanceVoid )
            {
            if( ++relayQueue[ bestQueue ].currentEvent >= relayQueue[ bestQueue ].endOfEvents )
                relayQueue[ bestQueue ].bProcessed = true ;
            }

        if( debug.eventQueue )
            {
            aiLogger() << "     RelayQueue[" << bestQueue << "].next(), bestDistance = " << (int)bestDistance << endl ;
            }

        *targetEvent = nearestEvent ;
        return bestDistance ;
        }

    }; // struct RelayQueue

The processing the relay queues do can be performed nearly exclusively in the processor cache.

Putting all together

I hope this short practical guide gives you an idea what type of tools are typically needed to build complex AI. It will help you if you develop a firm grasp of high-level concepts like these that are useful in application and AI development.

If you are smart you can already build a powerful pathfinder from this lesson and the last. 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.