Author: Gerd Isenberg
Date: 14:47:11 09/10/02
Go up one level in this thread
On September 10, 2002 at 17:39:33, Gerd Isenberg wrote:
>On September 10, 2002 at 15:50:32, Sune Fischer wrote:
>
>>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.
>
>negligible,
oups, only if the squares are connected of course.
otherwise factor two in worst case.
But you can win more than two in other cases,
like factor 28, hmmm...
>but if you fill this one from h2 to h8, it saves 28 iterations :-)
>
>1 1 1 1 1 1 0 1 bf
>1 0 0 0 0 0 0 0 01
>1 1 1 1 1 1 1 1 ff
>0 0 0 0 0 0 0 1 80
>1 1 1 1 1 1 1 1 ff
>1 0 0 0 0 0 0 0 01
>1 0 0 0 0 0 0 1 81
>1 1 1 1 1 1 1 1 ff
>
>Gerd
>
>
>
>>>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.