Bijuy board with gravity
I am trying to create a Bejeweled waterfall simulator with a board. So far I've been able to detect and delete matches, but now I need the jewels to drop. My fortune is represented by a list of boards, one for each type of jewelry. I have a mask of all the jewels that have been removed.
Is it possible to use this bitwise magic?
An example of two initial bit boards (let's assume there are only two types of jewels, and that it is a 4x4 board instead of 8x8). The first bit is the bottom left, the fourth bit is the top left, and the last bit is the top right.
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
After removing matches:
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
Mask used:
0 0 0 0
0 1 1 1
1 1 1 1
0 0 0 0
And after the severity, it should look like this:
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
This is implemented with integers and the steps would look like this:
[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
source to share
To drop a bit, you need to move the mask up one line using a bit shift. Select bits from the line above using mask and copy, which selected bits one line down using bit shift and orgov. A simple algorithm masks the loop up and moves down the lines. But optimization can expand the mask with bit shifts and manipulate with itself and then move all of the above bits with a single operation.
A good source for bitmap operating systems is the wiki: https://chessprogramming.wikispaces.com/General+Setwise+Operations
source to share
Call on the left board A
; right B
,; and the physical representation of the board AB
.
After removal, we have:
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
Algorithm:
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
Example:
Update the first line above the bottom line with delete:
# 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
Update the second line above the bottom line with abstractions:
# 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
source to share