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

- Re: All shortest paths & other flood-fill based algorithms
**Gerd Isenberg***01:33:22 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Steffan Westcott***05:48:36 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Gerd Isenberg***07:42:55 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Heiner Marxen***08:56:41 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Steffan Westcott***09:47:23 09/14/02*

- Re: All shortest paths & other flood-fill based algorithms

- Re: All shortest paths & other flood-fill based algorithms

- Re: All shortest paths & other flood-fill based algorithms

- Re: All shortest paths & other flood-fill based algorithms
- Re: All shortest paths & other flood-fill based algorithms
**Sune Fischer***01:10:46 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Sune Fischer***01:33:40 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Steffan Westcott***04:27:17 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Alessandro Damiani***09:41:02 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Steffan Westcott***10:17:53 09/14/02*- Re: All shortest paths & other flood-fill based algorithms
**Alessandro Damiani***10:50:03 09/14/02*

- Re: All shortest paths & other flood-fill based algorithms
- Re: All shortest paths & other flood-fill based algorithms
**Gerd Isenberg***10:06:30 09/14/02*

- Re: All shortest paths & other flood-fill based algorithms
- Re: All shortest paths & other flood-fill based algorithms
**Sune Fischer***05:11:46 09/14/02*

- Re: All shortest paths & other flood-fill based algorithms

- Re: All shortest paths & other flood-fill based algorithms

- Re: All shortest paths & other flood-fill based algorithms

This page took 0.19 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.