珠光寶寶位板應用重力

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 

除去比賽後：

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

使用的面膜是：

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

爲了落下位，你需要移動你的掩碼一排移位。使用掩碼從上面的行中選擇位，並使用位移和定位將選定的位複製一行。簡單的算法會循環屏蔽到頂部並逐行移動。但是優化可以通過位移和自我擴展來擴展掩碼，然後通過單個操作移動所有位以上的位。

對位板operatinos良好的來源是國際象棋的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 

算法：

For each row (r, a temporary variable) above the lowest row with removals: 
    For each jewel type: 
    starting with the lowest row where removals occurred (AB_row) 
    While r is not zero 
     make a temporary copy of AB_row (AB_row_copy) 
     new row for jewel_type := (row | AB_row)^same_row_for_other_jewel_types 
     r := r & AB_row_copy 
     ascend to next row of AB 

實施例：

更新所述第一行的最低行上面清除：

# AB_row is the lowest row with removals from the bitboard that combines all 
# jewel types; r_A is a copy from the A bitboard of the first row above AB_row 
r_A = 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 A 
    # new row for jewel_type := (row | AB_row)^same_row_for_other_jewel_types 
    new row for A = (1 0 0 0 | 0 0 0 0)^0 0 0 0 = 1 0 0 0 

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

# r_B at this row is zero, nothing to do. 
r_B = 0 0 0 0 

更新第二排上方的最低行與清除：

# 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