Am am currently coding up a somewhat chess-like game that includes a "pushing" mechanic. Getting an efficient algorithm for this seems to be elusive.
Here are the details. I represent an NxM toroidal board (yes this game can be played on different sized boards, so I need generalization) of tiles with 9 bitboards (3 for the types of tiles, 2 for the two players owning those tiles, and 4 for their orientations). Note that one of the three types of tiles has no owner or rotation. This probably does not matter, but just goes to show that the bitboards won't like up perfectly, so to speak.
In the game, you can take a tile and push it in one of four directions. If there is no tile where you push it, great, it loves there. However, if there is a tile there, then it also gets pushed, and so forth until there is an empty space or we've wrapped around entirely to the beginning (remember the board wraps left-right AND top-bottom.
I'm looking for a solution that is efficient, basically only using lookups and bit operations.
I see a few parts to this (though if someone has a more elegant solution please do tell.
- Calculate the distance between the starting push location and the first empty tile (or max out if we wrap all the way around). This should actually be a lookup table, since this is quite slow. Either way this returns a mask of '111' for the length of this. This would use the first 3 bitboards together (with |) to make sure all tiles can push all tiles. The rest will act upon each individual bitboard.
- For all 9 bitboards, extract this mask. (Mask & bitboard)
- For all extracted "tiles" save the last tile (this is in case we've wrapped around), and delete from the extracted tile set. (Mask _last & extract)
- The part I don't know how to do: rotate the remaining tiles. This is hard because of the toroidal board, I have no idea how to do this.
- Place the saved "last tile" and put it into the first tile's original position. (Saved | shifted_mask)
- Go back and delete this rotated tiles from all 9 bitboards. (Bitboard & ~mask)
- Add in the newly rotated tiles: (rotated | bitboard_with_deletions)
How do I do step 4? Or am I overlooking another more elegant way to so this?