Getting occupancy bit masks for bitboards

I'm playing with bitboards to represent a chess board and check for legal moves. The thing that I'm stuck with is calculation of occupancy between the source and destination squares in sliding piece attacks. I don't want to do it by lookup, so I'm trying to figure out if it is possible to get a mask for the squares in between without a lookup. For example, in the following board there is a Rook on c4:

8 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 
6 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
4 0 0 R 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 
  a b c d e f g h

Given a bitboard that represents empty squares (or occupied squares, whatever is easier) and a pseudo-valid move Rf4 (Rook can move from c4 to f4), how to get a mask for squares d4-e4 (excluding source and destination squares)?

I assume, once this is clear than vertical moves will be easy and diagonal moves can be calculated by using rotated bitboards.

EDIT: the bitboard is represented with ulong/unsigned int64, with every pack of 8 bits repres开发者_如何学Centing a rank/row of the actual board.

I'm going to make some assumptions here: The board is stored as a 64 bit number, each 8 byte block represents a row. Each bit in the row represents a column (a..h). You have start and end position as zero-based coordinates. i.e: start = "C4" = [2,3]; end = "F4" = [5,3]

For horizontal moves with increasing columns, you can calculate the distance moved: d = (F4-C4 = 3). Subtract 1 to exclude the destination, then the "trail" t of d-1 bits is t = (1<<(d-1))-1. Shift the trail adjacent to the source piece to get the mask M: M = t<<(start.row*8 + start.column+1).

This is equivalent to M = ((1<<d)-2)<<(start.row*8 + start.column)

For horizontal moves the other way:

 d = (C4-F4 = -3)
 t = (1<<(-d-1))-1
 M = (t<<dest.column+1)
 //-or-
 M = ((1<<-d)-2)<<(dest.row*8 + dest.column)

For vertically increasing moves:

 d = (C7-C4 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (start.row*8 + start.column)

For vertically decreasing moves:

 d = (C4-C7 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (dest.row*8 + start.column)

For the vertical moves, you can replace the loop over d by storing the maximum "vertical trail" VT = 0x0101010101010101 = 72340172838076673. Then mask out the right number of bits for the actual move.

This reduces the caclulation to M = (VT & ((1<<(d*8)) - 2)) << (row*8+column).

You could probably do something similar for the diagonal moves. Start with the max diagonal trail DT = 0x0102040810204080, apply a mask to reduce it to d set bits, and shift to the start or end location, depending on which is closer to the edge. This would need careful testing to make sure there were no edge cases which wrapped around into the wrong row.

Edited to exclude both source and destination, and fix one-off errors

Short of doing some up-front calculation and generating all possible masks for piece moves (a definite possibility), I'd expect that building up the masks at runtime would most likely be as expensive with respect to time as the simple 'lookup each square' approach.

Get the unity vector of direction (dx,dy)/dx

In this case, (1,0)

Then increment current position with that vector repeatedly until you reach destination. Underway increment/assign the corresponding matrix cells.