Advanced C++ Skills
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_queueThere 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__] ; // denotes the tile from which an event is accessed
// which can vary for heroes with different native terrain
// e.g. grass, sand, snow impact which is the best path for each hero
/*============== 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 ; // events checked during the current search
BITMAPHANDLE* hdlVisited ; // events already visited in the game
TerrainClassIndex _terrain_ ; // specs of the hero moving
unsigned char nPlayer ;
bool bInBoat ;
/*============== construction ==============*/
RelayQueue( BITMAPHANDLE& relayFilter, BITMAPHANDLE blockedTiles[], unsigned short mapTileCnt )
: 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() ; // ensures that this tile is initialized
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 RelayQueueThe 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.