Author: Gerd Isenberg
Date: 16:10:27 09/09/02
Go up one level in this thread
On September 09, 2002 at 18:52:05, Steffan Westcott wrote:
>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...
aha, sure. Luck that the bit 63 is mostly cleared in my program before shifting
:-)
>
>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 -----
Wow, Steffan, thats absolutely great.
Exactly what i was looking for.
"flood fill" algorithm.
Thanks a lot.
regards,
Gerd
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.