Author: Steffan Westcott
Date: 17:28:01 09/13/02
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
This page took 0.01 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.