I’ve run into an efficiency issue while coding the new version of Phalanx. While it’s not game-breaking, I very much want a game that’s meant to run 24/7 on arcade cabinets to be as easy on the hardware as possible. Thus, I thought I would raise it here, in the hope that someone might have insight.

Phalanx is played in real time on a board.

Although the game is played in real time, it is effectively divided into turns–one turn per frame. In each turn, the movement rules are as follows:

1. A piece can move if the space it is moving into:
   1. is currently empty, or
   2. will be empty this turn (e.g., because the piece in it is leaving).
2. A piece cannot move off the board, or into a space containing water (the blue area in the middle), either of the goals, or another piece that is not going to leave this turn.
3. Pieces move in number order, starting with player 1’s pieces and then proceeding through player 2’s pieces. (This is terrible, and messing with the algorithm is a good time to change it.) In the event of a conflict during movement (e.g., two pieces want to enter the same space), the earlier-moving piece takes priority.
4. If a piece is part of a formation, the entire formation cannot move if any individual member of the formation cannot move.

To implement those rules, the game proceeds as follows:

1. The game loops through all the pieces that want to move.
   1. All those that are moving into an empty space do so.
   2. All those that definitely will not move (e.g., pieces blocked by water) are marked as not moving.
   3. If a piece wants to move and is blocked by something that might get out of the way (e.g., another piece that hasn’t had its turn in the loop yet), that piece is skipped for this loop.
2. The game repeats step (1) until all pieces have moved or been marked as not moving.

This algorithm consistently produces the correct results, but the performance hit is rough. Is there a better way?