Author: Sune Fischer
Date: 12:50:32 09/10/02
Go up one level in this thread
On September 10, 2002 at 15:32:04, Gerd Isenberg wrote:
>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.
yes, and looks like it loses if the path is disconnected near the middle or
closer to sq1.
-S.
>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.