Author: Gerd Isenberg
Date: 12:32:04 09/10/02
Go up one level in this thread
On September 10, 2002 at 03:11:41, Sune Fischer wrote:
>On September 10, 2002 at 03:06:48, Gerd Isenberg wrote:
>
>>Thanks, Tony
>>
>>i have it now. It's a floodfill algorithm.
>>
>>Gerd
>
>I wonder if it is possible to optimize it by running the squares against each
>other to meet at half way?
>Doesn't seem doable though, if we mask the squares onto the same board we can do
>both operations in one go, but then there is no way to check for contact:(
>
>-S.
With Steffans flood filler its possible to "unroll" the loop, and alternately
let sq2 growing along the path. But that only gains performance, if the path is
disconnected near sq2.
Approx. 3-4 times faster than my dumb recursive one!
Nice to debug, looking for the growing sq1 iteration for iteration.
// SquaresAreConnected by Steffan Westcott slightly modified
// due to parameter and "unrolled" loop
//==========================================================
bool isConnected2(BitBoard path, int from, int to)
{
BitBoard sq1, sq2;
sq1 = scBBOfBit[from];
sq2 = scBBOfBit[to];
// 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
// may be skipped here if we assume from!=to in Path
while(1)
{
register 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 & sq2) return true; // Found a good path
if (sq1 == temp) return false; // Fill has stopped
// alternatly fill with sq2
temp = sq2;
sq2 |= ShiftLeft(sq2) | ShiftRight(sq2); // Set all 8 neighbours
sq2 |= ShiftDown(sq2) | ShiftUp(sq2);
sq2 &= path; // Drop bits not in path
if (sq1 & sq2) return true; // Found a good path
if (sq2 == temp) return false; // Fill has stopped
}
}
cheers,
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.