Author: Ron Murawski
Date: 19:22:13 09/09/02
Go up one level in this thread
On September 09, 2002 at 19:10:27, Gerd Isenberg wrote:
>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
Flood fill is a very efficient maze-solver. And that is what you are trying to
solve -- a maze that may have zero or more "correct" paths and may contain
loops.
Ron
This page took 0.01 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.