宝石钻头板

Question

我正在尝试用位板制作一个镶宝石的级联模拟器。到目前为止，我已经能够探测到并移除火柴，但现在我需要让珠宝掉落下来。我的状态由一个位板列表表示，每种类型的宝石都有一个。我有一个面具，上面有所有被移除的珠宝。在

有没有可能使用一些按位的魔法来实现这一点？在

两个初始位板的示例（假设只有两种类型的宝石，并且它是4x4板而不是8x8板）。第一位是左下角，第四位是左上角，最后一位是右上角。在

0 0 1 1    1 1 0 0
1 0 0 0    0 1 1 1
1 1 1 1    0 0 0 0
0 0 1 0    1 1 0 1

删除匹配项后：

^{pr2}$

使用的面罩是：

0 0 0 0
0 1 1 1
1 1 1 1
0 0 0 0

在重力作用下，它应该看起来像：

0 0 0 0    0 0 0 0
0 0 0 0    1 0 0 0
1 0 1 1    0 1 0 0
0 0 1 0    1 1 0 1

这是用整数实现的，步骤如下：

[43814, 21721]       # Initial state
[35076, 4249], 26210 # State after matches have been removed, mask used to remove matches
[8962, 4149]         # State after gravity has been applied

Answer 1

为了减少位，你需要移动你的面具一行与比特移位。使用掩码从上面的行中选择位，然后使用位移位和O型环将选定的位复制一行。简单的算法将掩码循环到顶部，并逐行向下移动。但是优化可以是用位移位扩展掩码，用self扩展oring，然后用一个操作将上面的所有位向下移动。在

棋盘操作的好来源是国际象棋wiki:https://chessprogramming.wikispaces.com/General+Setwise+Operations

Answer 2

让我们把左边的宝石板称为A；右边叫B；板的物理表示AB。
移除后，我们有：

               0 0 1 1      1 1 0 0     1111
AB =  A | B =  1 0 0 0  or  0 0 0 0  =  1000
               0 0 0 0      0 0 0 0     0000
               0 0 1 0      1 1 0 1     1111

算法：

^{pr2}$

示例：

用删除更新最低行上方的第一行：

^{3}$

用removals更新最低行上方的第二行：

# row for A has the same process same as above
r_A = 0 0 1 1, AB_row = 1 0 0 0 // AB_row is the lowest row with removals
  AB_row_copy = 1 0 0 0
  new row for A = (0 0 1 1 | 1 0 0 0) ^ 0 0 0 0 = 1 0 1 1
  r_A = 0 0 1 1 & 1 0 0 0 = 0 0 0 0


# AB_row is the lowest row with removals from the bitboard that combines all
# jewel types; r_B is a copy from the B bitboard of the second row above AB_row
r_B = 1 1 0 0, AB_row = 1 0 1 1

  # make a copy of AB_row
  AB_row_copy = 1 0 1 1

  # calculate the new row for jewel type B
  # new row for jewel_type := (row | AB_row) ^ same_row_for_other_jewel_types
  new row for B = (1 1 0 0 | 1 0 1 1) ^ 1 0 1 1 = 0 1 0 0

  # update the fallen bits from r_B
  # r := r & AB_row_copy
  r_B = 1 1 0 0 & 1 0 1 1 = 1 0 0 0

# since there are still set bits remaining in r_B after removing the fallen 
# bit, we continue with r_B, proceeding to the next row up.

# AB_row now is the next row up from the lowest row with removals, again from
# the bitboard combining all jewel types; r_B is the same variable, now with 
# one set bit less (one "fallen" bit)
r_B = 1 0 0 0, AB_row = 0 0 0 0

  # make a copy of AB_row
  AB_row_copy = 0 0 0 0

  # calculate the new row for jewel type B
  # new row for jewel_type := (row | AB_row) ^ same_row_for_other_jewel_types
  new row for B = (1 0 0 0 | 0 0 0 0) ^ 0 0 0 0 = 1 0 0 0

  # update the fallen bits from r_B
  r_B = 1 0 0 0 & 0 0 0 0 = 0 0 0 0

  #r_B is now zero so the while loop is terminated