Bejeweled bit board с применением силы тяжести

Question

Я пытаюсь создать каскадный симулятор Bejeweled с долотами. Пока что я смог обнаружить и удалить матчи, но теперь мне нужно, чтобы драгоценности упали. Мое состояние представлено списком досок, по одному для каждого типа драгоценностей. У меня есть маска всех драгоценностей, которые удалены.

Можно ли использовать некоторую побитную магию для этого?

Пример двух начальных бит-досок (давайте предположим, что есть только два типа драгоценностей и что это плата 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 шахматы вика: 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