Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Bitmaps in Bomb
        
(Message started by: fotland on Feb 11^th, 2007, 5:37pm)

Title: Bitmaps in Bomb
Post by fotland on Feb 11^th, 2007, 5:37pm

I'm going to start some topics on the internals of Bomb. There are no big new ideas in Bomb, but there might be some things others haven't seen before.

Bomb is written in C++, but I minimize use of "new" and don't inheritance, to keep the performance high. This gives me the performance of C, but the compiler catches more of my coding errors.

Bomb uses bitmaps to represent the board. The bitmap class has inline implementations to avoid function calls to the bitmap functions. Each bitmap is represented in two 32-bit ints. I have all the simple functions like and, or, set bit, etc. I also have functions to iterate (find and clear the next bit), count number of bits set, and expand the bitmap by setting all bits adjacent to bits already set.

Here is some sample code:

#define ML 0xfefefefe
#define MR 0x7f7f7f7f
#define MD 0x00ffffff
#define MU 0xffffff00

class bmap
{
public:
__forceinline bmap(){
bm0 = bm1 = 0;
}

inline void bmnot(){
bm0 = ~bm0;
bm1 = ~bm1;
}
inline void bmand(bmap &m){
bm0 &= m.bm0;
bm1 &= m.bm1;
}
inline void expand(){ // set all bits adjacent to any set bit
int t0 = (bm0>>1)&MR | (bm0<<1)&ML | (bm0<<8) | (bm0>>8) | (bm1>>24);
int t1 = (bm1>>1)&MR | (bm1<<1)&ML | (bm1<<8) | (bm1>>8) | (bm0<<24);
bm0 |= t0;
bm1 |= t1;
}