Author: Gerd Isenberg
Date: 14:39:33 09/10/02
Go up one level in this thread
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,
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.