Author: Gerd Isenberg
Date: 01:33:22 09/14/02
Go up one level in this thread
On September 13, 2002 at 20:28:01, Steffan Westcott wrote:
>
>Here is some more material for people interested in flood-fill based algorithms,
>of the ilk I first mentioned in this article :
>http://www.talkchess.com/forums/1/message.html?251180
>
>The following routine determines if a path of set bits in 'path' 8-way connect
>(ie. king move) any set bit in sq1 with any set bit in sq2 (this is the same as
>SquaresAreConnected). Also, it will return an array of bitboards showing all
>possible shortest paths - This is probably best explained by showing an example
>:
>
>Setting sq1 to contain e4, sq2 to have both a1 and h8, and mask to be ~0 yields
>this all shortest paths array of bitboards :
>
>[D]8/8/8/8/4K3/3/3/3 w - - 0 1
>
>[D]8/8/8/4KK2/3K4/3K4/8/8 w - - 0 1
>
>[D]8/8/5KK1/8/8/2K5/2K5/8 w - - 0 1
>
>[D]8/6KK/8/8/8/8/1K6/1K6 w - - 0 1
>
>[D]7K/8/8/8/8/8/8/K7 w - - 0 1
>
>The king needs 4 moves to reach either a1 or h8, so both possibilities are shown
>in the last bitboard. Also, the king has a choice of squares along the way,
>meaning there are many shortest paths.
>
>
>---- 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 length of shortest path of set bits present in 'path' that
>// 8-way connect any set bit in sq1 to any set bit of sq2. 0 is returned
>// if no such path exists. Also fills a sequence of bitboards asp[length]
>// that describes all such shortest paths.
>
>int AllShortestPaths(BitBoard sq1, BitBoard sq2, BitBoard path,
> BitBoard* asp)
>{
> // Do an 8-way flood fill with sq1, masking off bits not in path and
> // storing the fill frontier at every step. Stop when fill reaches
> // any set bit in sq2 or quit if fill cannot progress any further.
> // Then do 8-way flood fill from reached bits in sq2, ANDing the
> // frontiers with those from the first fill in reverse order.
>
> if (!(sq1 &= path) || !(sq2 &= path)) return 0;
> // Drop bits not in path
> // Early exit if sq1 or sq2 not on any path
> int i = 1;
> asp[0] = sq1;
>
> while(1) // Fill from all set bits in sq1, to any set bit in sq2
> {
> if (sq1 & sq2) break; // Found 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 0; // Fill has stopped
> asp[i++] = sq1 & ~temp; // Store fill frontier
> }
>
> int length = i; // Remember path length
> asp[--i] = (sq2 &= sq1); // Drop unreached bits
>
> while(i) // Fill from reached bits in sq2
> {
> BitBoard temp = sq2;
> sq2 |= ShiftLeft(sq2) | ShiftRight(sq2); // Set all 8 neighbours
> sq2 |= ShiftDown(sq2) | ShiftUp(sq2);
> sq2 &= path; // Drop bits not in path
> asp[--i] &= sq2 & ~temp; // Intersect frontiers
> }
>
> return length;
>}
>
>---- CUT HERE ----
>
>
>So far we've just mentioned 8-way flood filling for king/queen moves, and
>diagonal or rank/file 4-way filling for bishop or rook moves. A simple variant
>exists for knight moves too, which is handy for calculating knight mobility, and
>helping solve "Knight's Tour" type puzzles. Its even useful for pawns too, for
>quick determination of outposts outside all enemy pawn "attack cones", for
>example.
>
>A fill iteration need not just go one square in each direction. With appropriate
>bitboard manipulation, it may extend the full ray of a sliding piece, for
>example. Examining the filled bitboard for 1 or 2 iterations will enable design
>of piece mobility terms with some simulated ply.
>
>
>Cheers,
>Steffan
Steffan, this is fascinating stuff, thanks.
I see the point with multiple target squares.
In the first while(true) loop you store all "new" flood bits in an array.
(sq ^ temp is also fine here, because all bits in temp are also member of the
"new" sq1 :-)
After you found a shortest path in "i"-iterations with asp[0]..asp[i-1] as
intermidiate path steps, you do a second flood loop from sq2 to sq1 to drop off
possibible "path step bits" from the first iteration, which are not necessray
for the sq1->sq2 flood - i see.
So if you found a asp-bitboard with only one bit set, you really found a
bottleneck - great.
Regards,
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.