Author: Steffan Westcott
Date: 15:52:05 09/09/02
Go up one level in this thread
Hi Gerd,
You could use a "flood fill" algorithm, like the one below, starting at the
"from" square and stopping if the fill hits the "to" square or the fill can't
make any more progress. The fill progresses in all directions at once, so should
return an answer within a few iterations. Each iteration is pretty fast too, as
it just a bunch of shifting and logic operations. And no lookup tables either :)
Please note the warning about making BitBoard unsigned...
Cheers,
Steffan
----- CUT HERE -----
// NB MUST BE UNSIGNED (for >> to work ok)
typedef unsigned __int64 BitBoard;
BitBoard ShiftRight(BitBoard b)
{
return (b<<1) & 0xfefefefefefefefe;
}
BitBoard ShiftLeft(BitBoard b)
{
return (b>>1) & 0x7f7f7f7f7f7f7f7f;
}
BitBoard ShiftUp(BitBoard b)
{
return b<<8;
}
BitBoard ShiftDown(BitBoard b)
{
return b>>8;
}
/////////////////////////////////////////////////////////////////////////
//
// Returns true if a path of set bits in 'path' exists that 8-way connect
// any set bit in sq1 to any set bit of sq2
bool SquaresAreConnected(BitBoard sq1, BitBoard sq2, BitBoard path)
{
// With bitboard sq1, do an 8-way flood fill, masking off bits not in
// path at every step. Stop when fill reaches any set bit in sq2, or
// fill cannot progress any further
if (!(sq1 &= path) || !(sq2 &= path)) return false;
// Drop bits not in path
// Early exit if sq1 or sq2 not on any path
while(1)
{
if (sq1 & sq2) return true; // Found a good path
BitBoard temp = sq1;
sq1 |= ShiftLeft(sq1) | ShiftRight(sq1); // Set all 8 neighbours
sq1 |= ShiftDown(sq1) | ShiftUp(sq1);
sq1 &= path; // Drop bits not in path
if (sq1 == temp) return false; // Fill has stopped
}
}
----- CUT HERE -----
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.